2.4/user/super/com/google/gwt/emul/java/util/AbstractHashMap.java - gwt - Git at Google

 /*
  * Copyright 2008 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  * License for the specific language governing permissions and limitations under
  * the License.
  */
 package java.util;

 import com.google.gwt.core.client.JavaScriptObject;

 /**
  * Implementation of Map interface based on a hash table. <a
  * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun
  * docs]</a>
  *
  * @param <K> key type
  * @param <V> value type
  */
 abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> {
   /*
    * Implementation notes:
    *
    * String keys are stored in a separate map from non-String keys. String keys
    * are mapped to their values via a JS associative map, stringMap. String keys
    * could collide with intrinsic properties (like watch, constructor) so we
    * prepend each key with a ':' inside of stringMap.
    *
    * Integer keys are used to index all non-string keys. A key's hashCode is the
    * index in hashCodeMap which should contain that key. Since several keys may
    * have the same hash, each value in hashCodeMap is actually an array
    * containing all entries whose keys share the same hash.
    */
   private final class EntrySet extends AbstractSet<Entry<K, V>> {

     @Override
     public void clear() {
       AbstractHashMap.this.clear();
     }

     @Override
     public boolean contains(Object o) {
       if (o instanceof Map.Entry) {
         Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
         Object key = entry.getKey();
         if (AbstractHashMap.this.containsKey(key)) {
           Object value = AbstractHashMap.this.get(key);
           return AbstractHashMap.this.equals(entry.getValue(), value);
         }
       }
       return false;
     }

     @Override
     public Iterator<Entry<K, V>> iterator() {
       return new EntrySetIterator();
     }

     @Override
     public boolean remove(Object entry) {
       if (contains(entry)) {
         Object key = ((Map.Entry<?, ?>) entry).getKey();
         AbstractHashMap.this.remove(key);
         return true;
       }
       return false;
     }

     @Override
     public int size() {
       return AbstractHashMap.this.size();
     }
   }

   /**
    * Iterator for <code>EntrySetImpl</code>.
    */
   private final class EntrySetIterator implements Iterator<Entry<K, V>> {
     private final Iterator<Map.Entry<K, V>> iter;
     private Map.Entry<K, V> last = null;

     /**
      * Constructor for <code>EntrySetIterator</code>.
      */
     public EntrySetIterator() {
       List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
       if (nullSlotLive) {
         list.add(new MapEntryNull());
       }
       addAllStringEntries(list);
       addAllHashEntries(list);
       this.iter = list.iterator();
     }

     public boolean hasNext() {
       return iter.hasNext();
     }

     public Map.Entry<K, V> next() {
       return last = iter.next();
     }

     public void remove() {
       if (last == null) {
         throw new IllegalStateException("Must call next() before remove().");
       } else {
         iter.remove();
         AbstractHashMap.this.remove(last.getKey());
         last = null;
       }
     }
   }

   private final class MapEntryNull extends AbstractMapEntry<K, V> {

     public K getKey() {
       return null;
     }

     public V getValue() {
       return nullSlot;
     }

     public V setValue(V object) {
       return putNullSlot(object);
     }
   }

   // Instantiated from JSNI
   @SuppressWarnings("unused")
   private final class MapEntryString extends AbstractMapEntry<K, V> {

     private final String key;

     public MapEntryString(String key) {
       this.key = key;
     }

     @SuppressWarnings("unchecked")
     public K getKey() {
       return (K) key;
     }

     public V getValue() {
       return getStringValue(key);
     }

     public V setValue(V object) {
       return putStringValue(key, object);
     }
   }

   /**
    * A map of integral hashCodes onto entries.
    */
   // Used from JSNI.
   @SuppressWarnings("unused")
   private transient JavaScriptObject hashCodeMap;

   /**
    * This is the slot that holds the value associated with the "null" key.
    */
   private transient V nullSlot;

   private transient boolean nullSlotLive;

   private int size;

   /**
    * A map of Strings onto values.
    */
   // Used from JSNI.
   @SuppressWarnings("unused")
   private transient JavaScriptObject stringMap;

   {
     clearImpl();
   }

   public AbstractHashMap() {
   }

   public AbstractHashMap(int ignored) {
     // This implementation of HashMap has no need of initial capacities.
     this(ignored, 0);
   }

   public AbstractHashMap(int ignored, float alsoIgnored) {
     // This implementation of HashMap has no need of load factors or capacities.
     if (ignored < 0 || alsoIgnored < 0) {
       throw new IllegalArgumentException(
           "initial capacity was negative or load factor was non-positive");
     }
   }

   public AbstractHashMap(Map<? extends K, ? extends V> toBeCopied) {
     this.putAll(toBeCopied);
   }

   @Override
   public void clear() {
     clearImpl();
   }

   public abstract Object clone();

   @Override
   public boolean containsKey(Object key) {
     return (key == null) ? nullSlotLive : (!(key instanceof String)
         ? hasHashValue(key, getHashCode(key)) : hasStringValue((String) key));
   }

   @Override
   public boolean containsValue(Object value) {
     if (nullSlotLive && equals(nullSlot, value)) {
       return true;
     } else if (containsStringValue(value)) {
       return true;
     } else if (containsHashValue(value)) {
       return true;
     }
     return false;
   }

   @Override
   public Set<Map.Entry<K, V>> entrySet() {
     return new EntrySet();
   }

   @Override
   public V get(Object key) {
     return (key == null) ? nullSlot : (!(key instanceof String) ? getHashValue(
         key, getHashCode(key)) : getStringValue((String) key));
   }

   @Override
   public V put(K key, V value) {
     return (key == null) ? putNullSlot(value) : (!(key instanceof String)
         ? putHashValue(key, value, getHashCode(key)) : putStringValue(
             (String) key, value));
   }

   @Override
   public V remove(Object key) {
     return (key == null) ? removeNullSlot() : (!(key instanceof String)
         ? removeHashValue(key, getHashCode(key))
         : removeStringValue((String) key));
   }

   @Override
   public int size() {
     return size;
   }

   /**
    * Subclasses must override to return a whether or not two keys or values are
    * equal.
    */
   protected abstract boolean equals(Object value1, Object value2);

   /**
    * Subclasses must override to return a hash code for a given key. The key is
    * guaranteed to be non-null and not a String.
    */
   protected abstract int getHashCode(Object key);

   private native void addAllHashEntries(Collection<?> dest) /*-{
     var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
     for ( var hashCode in hashCodeMap) {
       // sanity check that it's really an integer
       var hashCodeInt = parseInt(hashCode, 10);
       if (hashCode == hashCodeInt) {
         var array = hashCodeMap[hashCodeInt];
         for ( var i = 0, c = array.length; i < c; ++i) {
           dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]);
         }
       }
     }
   }-*/;

   private native void addAllStringEntries(Collection<?> dest) /*-{
     var stringMap = this.@java.util.AbstractHashMap::stringMap;
     for (var key in stringMap) {
       // only keys that start with a colon ':' count
       if (key.charCodeAt(0) == 58) {
         var entry = @java.util.AbstractHashMap$MapEntryString::new(Ljava/util/AbstractHashMap;Ljava/lang/String;)(this, key.substring(1));
         dest.@java.util.Collection::add(Ljava/lang/Object;)(entry);
       }
     }
   }-*/;

   private void clearImpl() {
     hashCodeMap = JavaScriptObject.createArray();
     stringMap = JavaScriptObject.createObject();
     nullSlotLive = false;
     nullSlot = null;
     size = 0;
   }

   /**
    * Returns true if hashCodeMap contains any Map.Entry whose value is Object
    * equal to <code>value</code>.
    */
   private native boolean containsHashValue(Object value) /*-{
     var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
     for ( var hashCode in hashCodeMap) {
       // sanity check that it's really one of ours
       var hashCodeInt = parseInt(hashCode, 10);
       if (hashCode == hashCodeInt) {
         var array = hashCodeMap[hashCodeInt];
         for ( var i = 0, c = array.length; i < c; ++i) {
           var entry = array[i];
           var entryValue = entry.@java.util.Map$Entry::getValue()();
           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
             return true;
           }
         }
       }
     }
     return false;
   }-*/;

   /**
    * Returns true if stringMap contains any key whose value is Object equal to
    * <code>value</code>.
    */
   private native boolean containsStringValue(Object value) /*-{
     var stringMap = this.@java.util.AbstractHashMap::stringMap;
     for ( var key in stringMap) {
       // only keys that start with a colon ':' count
       if (key.charCodeAt(0) == 58) {
         var entryValue = stringMap[key];
         if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
           return true;
         }
       }
     }
     return false;
   }-*/;

   /**
    * Bridge method from JSNI that keeps us from having to make polymorphic calls
    * in JSNI. By putting the polymorphism in Java code, the compiler can do a
    * better job of optimizing in most cases.
    */
   @SuppressWarnings("unused")
   private boolean equalsBridge(Object value1, Object value2) {
     return equals(value1, value2);
   }

   /**
    * Returns the Map.Entry whose key is Object equal to <code>key</code>,
    * provided that <code>key</code>'s hash code is <code>hashCode</code>;
    * or <code>null</code> if no such Map.Entry exists at the specified
    * hashCode.
    */
   private native V getHashValue(Object key, int hashCode) /*-{
     var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
     if (array) {
       for ( var i = 0, c = array.length; i < c; ++i) {
         var entry = array[i];
         var entryKey = entry.@java.util.Map$Entry::getKey()();
         if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
           return entry.@java.util.Map$Entry::getValue()();
         }
       }
     }
     return null;
   }-*/;

   /**
    * Returns the value for the given key in the stringMap. Returns
    * <code>null</code> if the specified key does not exist.
    */
   private native V getStringValue(String key) /*-{
     return this.@java.util.AbstractHashMap::stringMap[':' + key];
   }-*/;

   /**
    * Returns true if the a key exists in the hashCodeMap that is Object equal to
    * <code>key</code>, provided that <code>key</code>'s hash code is
    * <code>hashCode</code>.
    */
   private native boolean hasHashValue(Object key, int hashCode) /*-{
     var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
     if (array) {
       for ( var i = 0, c = array.length; i < c; ++i) {
         var entry = array[i];
         var entryKey = entry.@java.util.Map$Entry::getKey()();
         if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
           return true;
         }
       }
     }
     return false;
   }-*/;

   /**
    * Returns true if the given key exists in the stringMap.
    */
   private native boolean hasStringValue(String key) /*-{
     return (':' + key) in this.@java.util.AbstractHashMap::stringMap;
   }-*/;

   /**
    * Sets the specified key to the specified value in the hashCodeMap. Returns
    * the value previously at that key. Returns <code>null</code> if the
    * specified key did not exist.
    */
   private native V putHashValue(K key, V value, int hashCode) /*-{
     var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
     if (array) {
       for ( var i = 0, c = array.length; i < c; ++i) {
         var entry = array[i];
         var entryKey = entry.@java.util.Map$Entry::getKey()();
         if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
           // Found an exact match, just update the existing entry
           var previous = entry.@java.util.Map$Entry::getValue()();
           entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value);
           return previous;
         }
       }
     } else {
       array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode] = [];
     }
     var entry = @java.util.MapEntryImpl::new(Ljava/lang/Object;Ljava/lang/Object;)(key, value);
     array.push(entry);
     ++this.@java.util.AbstractHashMap::size;
     return null;
   }-*/;

   private V putNullSlot(V value) {
     V result = nullSlot;
     nullSlot = value;
     if (!nullSlotLive) {
       nullSlotLive = true;
       ++size;
     }
     return result;
   }

   /**
    * Sets the specified key to the specified value in the stringMap. Returns the
    * value previously at that key. Returns <code>null</code> if the specified
    * key did not exist.
    */
   private native V putStringValue(String key, V value) /*-{
     var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
     key = ':' + key;
     if (key in stringMap) {
       result = stringMap[key];
     } else {
       ++this.@java.util.AbstractHashMap::size;
     }
     stringMap[key] = value;
     return result;
   }-*/;

   /**
    * Removes the pair whose key is Object equal to <code>key</code> from
    * <code>hashCodeMap</code>, provided that <code>key</code>'s hash code
    * is <code>hashCode</code>. Returns the value that was associated with the
    * removed key, or null if no such key existed.
    */
   private native V removeHashValue(Object key, int hashCode) /*-{
     var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
     if (array) {
       for ( var i = 0, c = array.length; i < c; ++i) {
         var entry = array[i];
         var entryKey = entry.@java.util.Map$Entry::getKey()();
         if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
           if (array.length == 1) {
             // remove the whole array
             delete this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
           } else {
             // splice out the entry we're removing
             array.splice(i, 1);
           }
           --this.@java.util.AbstractHashMap::size;
           return entry.@java.util.Map$Entry::getValue()();
         }
       }
     }
     return null;
   }-*/;

   private V removeNullSlot() {
     V result = nullSlot;
     nullSlot = null;
     if (nullSlotLive) {
       nullSlotLive = false;
       --size;
     }
     return result;
   }

   /**
    * Removes the specified key from the stringMap and returns the value that was
    * previously there. Returns <code>null</code> if the specified key does not
    * exist.
    */
   private native V removeStringValue(String key) /*-{
     var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
     key = ':' + key;
     if (key in stringMap) {
       result = stringMap[key];
       --this.@java.util.AbstractHashMap::size;
       delete stringMap[key];
     }
     return result;
   }-*/;
 }
	/*
	* Copyright 2008 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not
	* use this file except in compliance with the License. You may obtain a copy of
	* the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	* License for the specific language governing permissions and limitations under
	* the License.
	*/
	package java.util;

	import com.google.gwt.core.client.JavaScriptObject;

	/**
	* Implementation of Map interface based on a hash table. <a
	* href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun
	* docs]</a>
	*
	* @param <K> key type
	* @param <V> value type
	*/
	abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> {
	/*
	* Implementation notes:
	*
	* String keys are stored in a separate map from non-String keys. String keys
	* are mapped to their values via a JS associative map, stringMap. String keys
	* could collide with intrinsic properties (like watch, constructor) so we
	* prepend each key with a ':' inside of stringMap.
	*
	* Integer keys are used to index all non-string keys. A key's hashCode is the
	* index in hashCodeMap which should contain that key. Since several keys may
	* have the same hash, each value in hashCodeMap is actually an array
	* containing all entries whose keys share the same hash.
	*/
	private final class EntrySet extends AbstractSet<Entry<K, V>> {

	@Override
	public void clear() {
	AbstractHashMap.this.clear();
	}

	@Override
	public boolean contains(Object o) {
	if (o instanceof Map.Entry) {
	Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
	Object key = entry.getKey();
	if (AbstractHashMap.this.containsKey(key)) {
	Object value = AbstractHashMap.this.get(key);
	return AbstractHashMap.this.equals(entry.getValue(), value);
	}
	}
	return false;
	}

	@Override
	public Iterator<Entry<K, V>> iterator() {
	return new EntrySetIterator();
	}

	@Override
	public boolean remove(Object entry) {
	if (contains(entry)) {
	Object key = ((Map.Entry<?, ?>) entry).getKey();
	AbstractHashMap.this.remove(key);
	return true;
	}
	return false;
	}

	@Override
	public int size() {
	return AbstractHashMap.this.size();
	}
	}

	/**
	* Iterator for <code>EntrySetImpl</code>.
	*/
	private final class EntrySetIterator implements Iterator<Entry<K, V>> {
	private final Iterator<Map.Entry<K, V>> iter;
	private Map.Entry<K, V> last = null;

	/**
	* Constructor for <code>EntrySetIterator</code>.
	*/
	public EntrySetIterator() {
	List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
	if (nullSlotLive) {
	list.add(new MapEntryNull());
	}
	addAllStringEntries(list);
	addAllHashEntries(list);
	this.iter = list.iterator();
	}

	public boolean hasNext() {
	return iter.hasNext();
	}

	public Map.Entry<K, V> next() {
	return last = iter.next();
	}

	public void remove() {
	if (last == null) {
	throw new IllegalStateException("Must call next() before remove().");
	} else {
	iter.remove();
	AbstractHashMap.this.remove(last.getKey());
	last = null;
	}
	}
	}

	private final class MapEntryNull extends AbstractMapEntry<K, V> {

	public K getKey() {
	return null;
	}

	public V getValue() {
	return nullSlot;
	}

	public V setValue(V object) {
	return putNullSlot(object);
	}
	}

	// Instantiated from JSNI
	@SuppressWarnings("unused")
	private final class MapEntryString extends AbstractMapEntry<K, V> {

	private final String key;

	public MapEntryString(String key) {
	this.key = key;
	}

	@SuppressWarnings("unchecked")
	public K getKey() {
	return (K) key;
	}

	public V getValue() {
	return getStringValue(key);
	}

	public V setValue(V object) {
	return putStringValue(key, object);
	}
	}

	/**
	* A map of integral hashCodes onto entries.
	*/
	// Used from JSNI.
	@SuppressWarnings("unused")
	private transient JavaScriptObject hashCodeMap;

	/**
	* This is the slot that holds the value associated with the "null" key.
	*/
	private transient V nullSlot;

	private transient boolean nullSlotLive;

	private int size;

	/**
	* A map of Strings onto values.
	*/
	// Used from JSNI.
	@SuppressWarnings("unused")
	private transient JavaScriptObject stringMap;

	{
	clearImpl();
	}

	public AbstractHashMap() {
	}

	public AbstractHashMap(int ignored) {
	// This implementation of HashMap has no need of initial capacities.
	this(ignored, 0);
	}

	public AbstractHashMap(int ignored, float alsoIgnored) {
	// This implementation of HashMap has no need of load factors or capacities.
	if (ignored < 0 \|\| alsoIgnored < 0) {
	throw new IllegalArgumentException(
	"initial capacity was negative or load factor was non-positive");
	}
	}

	public AbstractHashMap(Map<? extends K, ? extends V> toBeCopied) {
	this.putAll(toBeCopied);
	}

	@Override
	public void clear() {
	clearImpl();
	}

	public abstract Object clone();

	@Override
	public boolean containsKey(Object key) {
	return (key == null) ? nullSlotLive : (!(key instanceof String)
	? hasHashValue(key, getHashCode(key)) : hasStringValue((String) key));
	}

	@Override
	public boolean containsValue(Object value) {
	if (nullSlotLive && equals(nullSlot, value)) {
	return true;
	} else if (containsStringValue(value)) {
	return true;
	} else if (containsHashValue(value)) {
	return true;
	}
	return false;
	}

	@Override
	public Set<Map.Entry<K, V>> entrySet() {
	return new EntrySet();
	}

	@Override
	public V get(Object key) {
	return (key == null) ? nullSlot : (!(key instanceof String) ? getHashValue(
	key, getHashCode(key)) : getStringValue((String) key));
	}

	@Override
	public V put(K key, V value) {
	return (key == null) ? putNullSlot(value) : (!(key instanceof String)
	? putHashValue(key, value, getHashCode(key)) : putStringValue(
	(String) key, value));
	}

	@Override
	public V remove(Object key) {
	return (key == null) ? removeNullSlot() : (!(key instanceof String)
	? removeHashValue(key, getHashCode(key))
	: removeStringValue((String) key));
	}

	@Override
	public int size() {
	return size;
	}

	/**
	* Subclasses must override to return a whether or not two keys or values are
	* equal.
	*/
	protected abstract boolean equals(Object value1, Object value2);

	/**
	* Subclasses must override to return a hash code for a given key. The key is
	* guaranteed to be non-null and not a String.
	*/
	protected abstract int getHashCode(Object key);

	private native void addAllHashEntries(Collection<?> dest) /*-{
	var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
	for ( var hashCode in hashCodeMap) {
	// sanity check that it's really an integer
	var hashCodeInt = parseInt(hashCode, 10);
	if (hashCode == hashCodeInt) {
	var array = hashCodeMap[hashCodeInt];
	for ( var i = 0, c = array.length; i < c; ++i) {
	dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]);
	}
	}
	}
	}-*/;

	private native void addAllStringEntries(Collection<?> dest) /*-{
	var stringMap = this.@java.util.AbstractHashMap::stringMap;
	for (var key in stringMap) {
	// only keys that start with a colon ':' count
	if (key.charCodeAt(0) == 58) {
	var entry = @java.util.AbstractHashMap$MapEntryString::new(Ljava/util/AbstractHashMap;Ljava/lang/String;)(this, key.substring(1));
	dest.@java.util.Collection::add(Ljava/lang/Object;)(entry);
	}
	}
	}-*/;

	private void clearImpl() {
	hashCodeMap = JavaScriptObject.createArray();
	stringMap = JavaScriptObject.createObject();
	nullSlotLive = false;
	nullSlot = null;
	size = 0;
	}

	/**
	* Returns true if hashCodeMap contains any Map.Entry whose value is Object
	* equal to <code>value</code>.
	*/
	private native boolean containsHashValue(Object value) /*-{
	var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
	for ( var hashCode in hashCodeMap) {
	// sanity check that it's really one of ours
	var hashCodeInt = parseInt(hashCode, 10);
	if (hashCode == hashCodeInt) {
	var array = hashCodeMap[hashCodeInt];
	for ( var i = 0, c = array.length; i < c; ++i) {
	var entry = array[i];
	var entryValue = entry.@java.util.Map$Entry::getValue()();
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
	return true;
	}
	}
	}
	}
	return false;
	}-*/;

	/**
	* Returns true if stringMap contains any key whose value is Object equal to
	* <code>value</code>.
	*/
	private native boolean containsStringValue(Object value) /*-{
	var stringMap = this.@java.util.AbstractHashMap::stringMap;
	for ( var key in stringMap) {
	// only keys that start with a colon ':' count
	if (key.charCodeAt(0) == 58) {
	var entryValue = stringMap[key];
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
	return true;
	}
	}
	}
	return false;
	}-*/;

	/**
	* Bridge method from JSNI that keeps us from having to make polymorphic calls
	* in JSNI. By putting the polymorphism in Java code, the compiler can do a
	* better job of optimizing in most cases.
	*/
	@SuppressWarnings("unused")
	private boolean equalsBridge(Object value1, Object value2) {
	return equals(value1, value2);
	}

	/**
	* Returns the Map.Entry whose key is Object equal to <code>key</code>,
	* provided that <code>key</code>'s hash code is <code>hashCode</code>;
	* or <code>null</code> if no such Map.Entry exists at the specified
	* hashCode.
	*/
	private native V getHashValue(Object key, int hashCode) /*-{
	var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
	if (array) {
	for ( var i = 0, c = array.length; i < c; ++i) {
	var entry = array[i];
	var entryKey = entry.@java.util.Map$Entry::getKey()();
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
	return entry.@java.util.Map$Entry::getValue()();
	}
	}
	}
	return null;
	}-*/;

	/**
	* Returns the value for the given key in the stringMap. Returns
	* <code>null</code> if the specified key does not exist.
	*/
	private native V getStringValue(String key) /*-{
	return this.@java.util.AbstractHashMap::stringMap[':' + key];
	}-*/;

	/**
	* Returns true if the a key exists in the hashCodeMap that is Object equal to
	* <code>key</code>, provided that <code>key</code>'s hash code is
	* <code>hashCode</code>.
	*/
	private native boolean hasHashValue(Object key, int hashCode) /*-{
	var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
	if (array) {
	for ( var i = 0, c = array.length; i < c; ++i) {
	var entry = array[i];
	var entryKey = entry.@java.util.Map$Entry::getKey()();
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
	return true;
	}
	}
	}
	return false;
	}-*/;

	/**
	* Returns true if the given key exists in the stringMap.
	*/
	private native boolean hasStringValue(String key) /*-{
	return (':' + key) in this.@java.util.AbstractHashMap::stringMap;
	}-*/;

	/**
	* Sets the specified key to the specified value in the hashCodeMap. Returns
	* the value previously at that key. Returns <code>null</code> if the
	* specified key did not exist.
	*/
	private native V putHashValue(K key, V value, int hashCode) /*-{
	var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
	if (array) {
	for ( var i = 0, c = array.length; i < c; ++i) {
	var entry = array[i];
	var entryKey = entry.@java.util.Map$Entry::getKey()();
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
	// Found an exact match, just update the existing entry
	var previous = entry.@java.util.Map$Entry::getValue()();
	entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value);
	return previous;
	}
	}
	} else {
	array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode] = [];
	}
	var entry = @java.util.MapEntryImpl::new(Ljava/lang/Object;Ljava/lang/Object;)(key, value);
	array.push(entry);
	++this.@java.util.AbstractHashMap::size;
	return null;
	}-*/;

	private V putNullSlot(V value) {
	V result = nullSlot;
	nullSlot = value;
	if (!nullSlotLive) {
	nullSlotLive = true;
	++size;
	}
	return result;
	}

	/**
	* Sets the specified key to the specified value in the stringMap. Returns the
	* value previously at that key. Returns <code>null</code> if the specified
	* key did not exist.
	*/
	private native V putStringValue(String key, V value) /*-{
	var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
	key = ':' + key;
	if (key in stringMap) {
	result = stringMap[key];
	} else {
	++this.@java.util.AbstractHashMap::size;
	}
	stringMap[key] = value;
	return result;
	}-*/;

	/**
	* Removes the pair whose key is Object equal to <code>key</code> from
	* <code>hashCodeMap</code>, provided that <code>key</code>'s hash code
	* is <code>hashCode</code>. Returns the value that was associated with the
	* removed key, or null if no such key existed.
	*/
	private native V removeHashValue(Object key, int hashCode) /*-{
	var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
	if (array) {
	for ( var i = 0, c = array.length; i < c; ++i) {
	var entry = array[i];
	var entryKey = entry.@java.util.Map$Entry::getKey()();
	if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
	if (array.length == 1) {
	// remove the whole array
	delete this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
	} else {
	// splice out the entry we're removing
	array.splice(i, 1);
	}
	--this.@java.util.AbstractHashMap::size;
	return entry.@java.util.Map$Entry::getValue()();
	}
	}
	}
	return null;
	}-*/;

	private V removeNullSlot() {
	V result = nullSlot;
	nullSlot = null;
	if (nullSlotLive) {
	nullSlotLive = false;
	--size;
	}
	return result;
	}

	/**
	* Removes the specified key from the stringMap and returns the value that was
	* previously there. Returns <code>null</code> if the specified key does not
	* exist.
	*/
	private native V removeStringValue(String key) /*-{
	var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
	key = ':' + key;
	if (key in stringMap) {
	result = stringMap[key];
	--this.@java.util.AbstractHashMap::size;
	delete stringMap[key];
	}
	return result;
	}-*/;
	}