libcore/luni/src/main/java/java/util/HashMap.java - platform/dalvik.git - Git at Google

 /*
  *  Licensed to the Apache Software Foundation (ASF) under one or more
  *  contributor license agreements.  See the NOTICE file distributed with
  *  this work for additional information regarding copyright ownership.
  *  The ASF licenses this file to You 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 java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;

 /**
  * HashMap is an implementation of Map. All optional operations (adding and
  * removing) are supported. Keys and values can be any objects.
  *
  * @since Android 1.0
  */
 public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
         Cloneable, Serializable {
     private static final long serialVersionUID = 362498820763181265L;

     transient int elementCount;

     transient Entry<K, V>[] elementData;

     final float loadFactor;

     int threshold;

     transient int modCount = 0;

     private static final int DEFAULT_SIZE = 16;

     static class Entry<K, V> extends MapEntry<K, V> {
         final int origKeyHash;

         Entry<K, V> next;

         Entry(K theKey, int hash) {
             super(theKey, null);
             this.origKeyHash = hash;
         }

         Entry(K theKey, V theValue) {
             super(theKey, theValue);
             origKeyHash = (theKey == null ? 0 : theKey.hashCode());
         }

         @Override
         @SuppressWarnings("unchecked")
         public Object clone() {
             Entry<K, V> entry = (Entry<K, V>) super.clone();
             if (next != null) {
                 entry.next = (Entry<K, V>) next.clone();
             }
             return entry;
         }
     }

     static class HashMapIterator<E, KT, VT> implements Iterator<E> {
         private int position = 0;

         int expectedModCount;

         final MapEntry.Type<E, KT, VT> type;

         boolean canRemove = false;

         Entry<KT, VT> entry;

         Entry<KT, VT> lastEntry;

         final HashMap<KT, VT> associatedMap;

         HashMapIterator(MapEntry.Type<E, KT, VT> value, HashMap<KT, VT> hm) {
             associatedMap = hm;
             type = value;
             expectedModCount = hm.modCount;
         }

         public boolean hasNext() {
             if (entry != null) {
                 return true;
             }
             // BEGIN android-changed
             Entry<KT, VT>[] elementData = associatedMap.elementData;
             int length = elementData.length;
             int newPosition = position;
             boolean result = false;

             while (newPosition < length) {
                 if (elementData[newPosition] == null) {
                     newPosition++;
                 } else {
                     result = true;
                     break;
                 }
             }

             position = newPosition;
             return result;
             // END android-changed
         }

         void checkConcurrentMod() throws ConcurrentModificationException {
             if (expectedModCount != associatedMap.modCount) {
                 throw new ConcurrentModificationException();
             }
         }

         public E next() {
             // BEGIN android-changed
             // inline checkConcurrentMod()
             if (expectedModCount != associatedMap.modCount) {
                 throw new ConcurrentModificationException();
             }
             if (!hasNext()) {
                 throw new NoSuchElementException();
             }

             MapEntry<KT, VT> result;
             Entry<KT, VT> _entry  = entry;
             if (_entry == null) {
                 result = lastEntry = associatedMap.elementData[position++];
                 entry = lastEntry.next;
             } else {
                 if (lastEntry.next != _entry) {
                     lastEntry = lastEntry.next;
                 }
                 result = _entry;
                 entry = _entry.next;
             }
             canRemove = true;
             return type.get(result);
             // END android-changed
         }

         public void remove() {
             checkConcurrentMod();
             if (!canRemove) {
                 throw new IllegalStateException();
             }

             canRemove = false;
             associatedMap.modCount++;
             if (lastEntry.next == entry) {
                 while (associatedMap.elementData[--position] == null) {
                     // Do nothing
                 }
                 associatedMap.elementData[position] = associatedMap.elementData[position].next;
                 entry = null;
             } else {
                 lastEntry.next = entry;
             }
             associatedMap.elementCount--;
             expectedModCount++;
         }
     }

     static class HashMapEntrySet<KT, VT> extends AbstractSet<Map.Entry<KT, VT>> {
         private final HashMap<KT, VT> associatedMap;

         public HashMapEntrySet(HashMap<KT, VT> hm) {
             associatedMap = hm;
         }

         HashMap<KT, VT> hashMap() {
             return associatedMap;
         }

         @Override
         public int size() {
             return associatedMap.elementCount;
         }

         @Override
         public void clear() {
             associatedMap.clear();
         }

         @Override
         public boolean remove(Object object) {
             if (contains(object)) {
                 associatedMap.remove(((Map.Entry<?, ?>) object).getKey());
                 return true;
             }
             return false;
         }

         @Override
         public boolean contains(Object object) {
             if (object instanceof Map.Entry) {
                 Object key = ((Map.Entry<?, ?>) object).getKey();
                 Entry entry;
                 if (key == null) {
                     entry = associatedMap.findNullKeyEntry();
                 } else {
                     int hash = key.hashCode();
                     int index = (hash & 0x7FFFFFFF) % associatedMap.elementData.length;
                     entry = associatedMap.findNonNullKeyEntry(key, index, hash);
                 }
                 return object.equals(entry);
             }
             return false;
         }

         @Override
         public Iterator<Map.Entry<KT, VT>> iterator() {
             return new HashMapIterator<Map.Entry<KT, VT>, KT, VT>(
                     new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
                         public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) {
                             return entry;
                         }
                     }, associatedMap);
         }
     }

     @SuppressWarnings("unchecked")
     Entry<K, V>[] newElementArray(int s) {
         return new Entry[s];
     }

     /**
      * Constructs a new empty {@code HashMap} instance.
      *
      * @since Android 1.0
      */
     public HashMap() {
         this(DEFAULT_SIZE);
     }

     /**
      * Constructs a new {@code HashMap} instance with the specified capacity.
      *
      * @param capacity
      *            the initial capacity of this hash map.
      * @throws IllegalArgumentException
      *                when the capacity is less than zero.
      * @since Android 1.0
      */
     public HashMap(int capacity) {
         if (capacity >= 0) {
             elementCount = 0;
             elementData = newElementArray(capacity == 0 ? 1 : capacity);
             loadFactor = 0.75f; // Default load factor of 0.75
             computeMaxSize();
         } else {
             throw new IllegalArgumentException();
         }
     }

     /**
      * Constructs a new {@code HashMap} instance with the specified capacity and
      * load factor.
      *
      * @param capacity
      *            the initial capacity of this hash map.
      * @param loadFactor
      *            the initial load factor.
      * @throws IllegalArgumentException
      *                when the capacity is less than zero or the load factor is
      *                less or equal to zero.
      * @since Android 1.0
      */
     public HashMap(int capacity, float loadFactor) {
         if (capacity >= 0 && loadFactor > 0) {
             elementCount = 0;
             elementData = newElementArray(capacity == 0 ? 1 : capacity);
             this.loadFactor = loadFactor;
             computeMaxSize();
         } else {
             throw new IllegalArgumentException();
         }
     }

     /**
      * Constructs a new {@code HashMap} instance containing the mappings from
      * the specified map.
      *
      * @param map
      *            the mappings to add.
      * @since Android 1.0
      */
     public HashMap(Map<? extends K, ? extends V> map) {
         this(map.size() < 6 ? 11 : map.size() * 2);
         putAllImpl(map);
     }

     // BEGIN android-changed
     /**
      * Removes all mappings from this hash map, leaving it empty.
      *
      * @see #isEmpty
      * @see #size
      * @since Android 1.0
      */
     @Override
     public void clear() {
         internalClear();
     }

     void internalClear() {
         if (elementCount > 0) {
             elementCount = 0;
             Arrays.fill(elementData, null);
             modCount++;
         }
     }
     // END android-changed

     /**
      * Returns a shallow copy of this map.
      *
      * @return a shallow copy of this map.
      * @since Android 1.0
      */
     @Override
     @SuppressWarnings("unchecked")
     public Object clone() {
         try {
             // BEGIN android-changed
             // copied from newer version of harmony
             HashMap<K, V> map = (HashMap<K, V>) super.clone();
             map.elementData = newElementArray(elementData.length);
             map.internalClear();
             Entry<K, V> entry;
             for (int i = 0; i < elementData.length; i++) {
                 if ((entry = elementData[i]) != null){
                     map.putImpl(entry.getKey(), entry.getValue());
                     while (entry.next != null){
                         entry = entry.next;
                         map.putImpl(entry.getKey(), entry.getValue());
                     }
                 }
             // END android-changed
             }
             return map;
         } catch (CloneNotSupportedException e) {
             return null;
         }
     }

     private void computeMaxSize() {
         threshold = (int) (elementData.length * loadFactor);
     }

     /**
      * Returns whether this map contains the specified key.
      *
      * @param key
      *            the key to search for.
      * @return {@code true} if this map contains the specified key,
      *         {@code false} otherwise.
      * @since Android 1.0
      */
     @Override
     public boolean containsKey(Object key) {
         Entry<K, V> m;
         if (key == null) {
             m = findNullKeyEntry();
         } else {
             int hash = key.hashCode();
             int index = (hash & 0x7FFFFFFF) % elementData.length;
             m = findNonNullKeyEntry(key, index, hash);
         }
         return m != null;
     }

     /**
      * Returns whether this map contains the specified value.
      *
      * @param value
      *            the value to search for.
      * @return {@code true} if this map contains the specified value,
      *         {@code false} otherwise.
      * @since Android 1.0
      */
     @Override
     public boolean containsValue(Object value) {
         if (value != null) {
             for (int i = elementData.length; --i >= 0;) {
                 Entry<K, V> entry = elementData[i];
                 while (entry != null) {
                     if (value.equals(entry.value)) {
                         return true;
                     }
                     entry = entry.next;
                 }
             }
         } else {
             for (int i = elementData.length; --i >= 0;) {
                 Entry<K, V> entry = elementData[i];
                 while (entry != null) {
                     if (entry.value == null) {
                         return true;
                     }
                     entry = entry.next;
                 }
             }
         }
         return false;
     }

     /**
      * Returns a set containing all of the mappings in this map. Each mapping is
      * an instance of {@link Map.Entry}. As the set is backed by this map,
      * changes in one will be reflected in the other.
      *
      * @return a set of the mappings.
      * @since Android 1.0
      */
     @Override
     public Set<Map.Entry<K, V>> entrySet() {
         return new HashMapEntrySet<K, V>(this);
     }

     /**
      * Returns the value of the mapping with the specified key.
      *
      * @param key
      *            the key.
      * @return the value of the mapping with the specified key, or {@code null}
      *         if no mapping for the specified key is found.
      * @since Android 1.0
      */
     @Override
     public V get(Object key) {
         Entry<K, V> m;
         if (key == null) {
             m = findNullKeyEntry();
         } else {
             int hash = key.hashCode();
             int index = (hash & 0x7FFFFFFF) % elementData.length;
             m = findNonNullKeyEntry(key, index, hash);
         }
         if (m != null) {
             return m.value;
         }
         return null;
     }

     final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) {
         Entry<K,V> m = elementData[index];
         // BEGIN android-changed
         // The VM can optimize String.equals but not Object.equals
         if (key instanceof String) {
             String keyString = (String) key;
             while (m != null) {
                 if (m.origKeyHash == keyHash) {
                     if (keyString.equals(m.key)) {
                         return m;
                     }
                 }
                 m = m.next;
             }
         } else {
             while (m != null) {
                 if (m.origKeyHash == keyHash) {
                     if (key.equals(m.key)) {
                         return m;
                     }
                 }
                 m = m.next;
             }
         }
         return null;
         // END android-changed
     }

     final Entry<K,V> findNullKeyEntry() {
         Entry<K,V> m = elementData[0];
         while (m != null && m.key != null)
             m = m.next;
         return m;
     }

     /**
      * Returns whether this map is empty.
      *
      * @return {@code true} if this map has no elements, {@code false}
      *         otherwise.
      * @see #size()
      * @since Android 1.0
      */
     @Override
     public boolean isEmpty() {
         return elementCount == 0;
     }

     /**
      * Returns a set of the keys contained in this map. The set is backed by
      * this map so changes to one are reflected by the other. The set does not
      * support adding.
      *
      * @return a set of the keys.
      * @since Android 1.0
      */
     @Override
     public Set<K> keySet() {
         if (keySet == null) {
             keySet = new AbstractSet<K>() {
                 @Override
                 public boolean contains(Object object) {
                     return containsKey(object);
                 }

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

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

                 @Override
                 public boolean remove(Object key) {
                     Entry<K, V> entry = HashMap.this.removeEntry(key);
                     return entry != null;
                 }

                 @Override
                 public Iterator<K> iterator() {
                     return new HashMapIterator<K, K, V>(
                             new MapEntry.Type<K, K, V>() {
                                 public K get(MapEntry<K, V> entry) {
                                     return entry.key;
                                 }
                             }, HashMap.this);
                 }
             };
         }
         return keySet;
     }

     /**
      * Maps the specified key to the specified value.
      *
      * @param key
      *            the key.
      * @param value
      *            the value.
      * @return the value of any previous mapping with the specified key or
      *         {@code null} if there was no such mapping.
      * @since Android 1.0
      */
     @Override
     public V put(K key, V value) {
         return putImpl(key, value);
     }

     private V putImpl(K key, V value) {
         Entry<K,V> entry;
         if(key == null) {
             entry = findNullKeyEntry();
             if (entry == null) {
                 modCount++;
                 if (++elementCount > threshold) {
                     rehash();
                 }
                 entry = createHashedEntry(key, 0, 0);
             }
         } else {
             int hash = key.hashCode();
             int index = (hash & 0x7FFFFFFF) % elementData.length;
             entry = findNonNullKeyEntry(key, index, hash);
             if (entry == null) {
                 modCount++;
                 if (++elementCount > threshold) {
                     rehash();
                     index = (hash & 0x7FFFFFFF) % elementData.length;
                 }
                 entry = createHashedEntry(key, index, hash);
             }
         }

         V result = entry.value;
         entry.value = value;
         return result;
     }

     Entry<K, V> createEntry(K key, int index, V value) {
         Entry<K, V> entry = new Entry<K, V>(key, value);
         entry.next = elementData[index];
         elementData[index] = entry;
         return entry;
     }

     Entry<K,V> createHashedEntry(K key, int index, int hash) {
         Entry<K,V> entry = new Entry<K,V>(key,hash);
         entry.next = elementData[index];
         elementData[index] = entry;
         return entry;
     }

     /**
      * Copies all the mappings in the specified map to this map. These mappings
      * will replace all mappings that this map had for any of the keys currently
      * in the given map.
      *
      * @param map
      *            the map to copy mappings from.
      * @since Android 1.0
      */
     @Override
     public void putAll(Map<? extends K, ? extends V> map) {
         if (!map.isEmpty()) {
             putAllImpl(map);
         }
     }

     private void putAllImpl(Map<? extends K, ? extends V> map) {
         int capacity = elementCount + map.size();
         if (capacity > threshold) {
             rehash(capacity);
         }
         for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
             putImpl(entry.getKey(), entry.getValue());
         }
     }

     void rehash(int capacity) {
         int length = (capacity == 0 ? 1 : capacity << 1);

         Entry<K, V>[] newData = newElementArray(length);
         for (int i = 0; i < elementData.length; i++) {
             Entry<K, V> entry = elementData[i];
             while (entry != null) {
                 int index = (entry.origKeyHash & 0x7FFFFFFF) % length;
                 Entry<K, V> next = entry.next;
                 entry.next = newData[index];
                 newData[index] = entry;
                 entry = next;
             }
         }
         elementData = newData;
         computeMaxSize();
     }

     void rehash() {
         rehash(elementData.length);
     }

     /**
      * Removes the mapping with the specified key from this map.
      *
      * @param key
      *            the key of the mapping to remove.
      * @return the value of the removed mapping or {@code null} if no mapping
      *         for the specified key was found.
      * @since Android 1.0
      */
     @Override
     public V remove(Object key) {
         Entry<K, V> entry = removeEntry(key);
         if (entry != null) {
             return entry.value;
         }
         return null;
     }

     Entry<K, V> removeEntry(Object key) {
         int index = 0;
         Entry<K, V> entry;
         Entry<K, V> last = null;
         if (key != null) {
             int hash = key.hashCode();
             index = (hash & 0x7FFFFFFF) % elementData.length;
             entry = elementData[index];
             while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key))) {
                 last = entry;
                 entry = entry.next;
             }
         } else {
             entry = elementData[0];
             while (entry != null && entry.key != null) {
                 last = entry;
                 entry = entry.next;
             }
         }
         if (entry == null) {
             return null;
         }
         if (last == null) {
             elementData[index] = entry.next;
         } else {
             last.next = entry.next;
         }
         modCount++;
         elementCount--;
         return entry;
     }

     /**
      * Returns the number of elements in this map.
      *
      * @return the number of elements in this map.
      * @since Android 1.0
      */
     @Override
     public int size() {
         return elementCount;
     }

     /**
      * Returns a collection of the values contained in this map. The collection
      * is backed by this map so changes to one are reflected by the other. The
      * collection supports remove, removeAll, retainAll and clear operations,
      * and it does not support add or addAll operations.
      * <p>
      * This method returns a collection which is the subclass of
      * AbstractCollection. The iterator method of this subclass returns a
      * "wrapper object" over the iterator of map's entrySet(). The {@code size}
      * method wraps the map's size method and the {@code contains} method wraps
      * the map's containsValue method.
      * </p>
      * <p>
      * The collection is created when this method is called for the first time
      * and returned in response to all subsequent calls. This method may return
      * different collections when multiple concurrent calls occur, since no
      * synchronization is performed.
      * </p>
      *
      * @return a collection of the values contained in this map.
      * @since Android 1.0
      */
     @Override
     public Collection<V> values() {
         if (valuesCollection == null) {
             valuesCollection = new AbstractCollection<V>() {
                 @Override
                 public boolean contains(Object object) {
                     return containsValue(object);
                 }

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

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

                 @Override
                 public Iterator<V> iterator() {
                     return new HashMapIterator<V, K, V>(
                             new MapEntry.Type<V, K, V>() {
                                 public V get(MapEntry<K, V> entry) {
                                     return entry.value;
                                 }
                             }, HashMap.this);
                 }
             };
         }
         return valuesCollection;
     }

     private void writeObject(ObjectOutputStream stream) throws IOException {
         stream.defaultWriteObject();
         stream.writeInt(elementData.length);
         stream.writeInt(elementCount);
         Iterator<?> iterator = entrySet().iterator();
         while (iterator.hasNext()) {
             Entry<?, ?> entry = (Entry<?, ?>) iterator.next();
             stream.writeObject(entry.key);
             stream.writeObject(entry.value);
             entry = entry.next;
         }
     }

     @SuppressWarnings("unchecked")
     private void readObject(ObjectInputStream stream) throws IOException,
             ClassNotFoundException {
         stream.defaultReadObject();
         int length = stream.readInt();
         elementData = newElementArray(length);
         elementCount = stream.readInt();
         for (int i = elementCount; --i >= 0;) {
             K key = (K) stream.readObject();
             int index = (null == key) ? 0 : (key.hashCode() & 0x7FFFFFFF)
                     % length;
             createEntry(key, index, (V) stream.readObject());
         }
     }

 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You 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 java.io.IOException;
	import java.io.ObjectInputStream;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;

	/**
	* HashMap is an implementation of Map. All optional operations (adding and
	* removing) are supported. Keys and values can be any objects.
	*
	* @since Android 1.0
	*/
	public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
	Cloneable, Serializable {
	private static final long serialVersionUID = 362498820763181265L;

	transient int elementCount;

	transient Entry<K, V>[] elementData;

	final float loadFactor;

	int threshold;

	transient int modCount = 0;

	private static final int DEFAULT_SIZE = 16;

	static class Entry<K, V> extends MapEntry<K, V> {
	final int origKeyHash;

	Entry<K, V> next;

	Entry(K theKey, int hash) {
	super(theKey, null);
	this.origKeyHash = hash;
	}

	Entry(K theKey, V theValue) {
	super(theKey, theValue);
	origKeyHash = (theKey == null ? 0 : theKey.hashCode());
	}

	@Override
	@SuppressWarnings("unchecked")
	public Object clone() {
	Entry<K, V> entry = (Entry<K, V>) super.clone();
	if (next != null) {
	entry.next = (Entry<K, V>) next.clone();
	}
	return entry;
	}
	}

	static class HashMapIterator<E, KT, VT> implements Iterator<E> {
	private int position = 0;

	int expectedModCount;

	final MapEntry.Type<E, KT, VT> type;

	boolean canRemove = false;

	Entry<KT, VT> entry;

	Entry<KT, VT> lastEntry;

	final HashMap<KT, VT> associatedMap;

	HashMapIterator(MapEntry.Type<E, KT, VT> value, HashMap<KT, VT> hm) {
	associatedMap = hm;
	type = value;
	expectedModCount = hm.modCount;
	}

	public boolean hasNext() {
	if (entry != null) {
	return true;
	}
	// BEGIN android-changed
	Entry<KT, VT>[] elementData = associatedMap.elementData;
	int length = elementData.length;
	int newPosition = position;
	boolean result = false;

	while (newPosition < length) {
	if (elementData[newPosition] == null) {
	newPosition++;
	} else {
	result = true;
	break;
	}
	}

	position = newPosition;
	return result;
	// END android-changed
	}

	void checkConcurrentMod() throws ConcurrentModificationException {
	if (expectedModCount != associatedMap.modCount) {
	throw new ConcurrentModificationException();
	}
	}

	public E next() {
	// BEGIN android-changed
	// inline checkConcurrentMod()
	if (expectedModCount != associatedMap.modCount) {
	throw new ConcurrentModificationException();
	}
	if (!hasNext()) {
	throw new NoSuchElementException();
	}

	MapEntry<KT, VT> result;
	Entry<KT, VT> _entry = entry;
	if (_entry == null) {
	result = lastEntry = associatedMap.elementData[position++];
	entry = lastEntry.next;
	} else {
	if (lastEntry.next != _entry) {
	lastEntry = lastEntry.next;
	}
	result = _entry;
	entry = _entry.next;
	}
	canRemove = true;
	return type.get(result);
	// END android-changed
	}

	public void remove() {
	checkConcurrentMod();
	if (!canRemove) {
	throw new IllegalStateException();
	}

	canRemove = false;
	associatedMap.modCount++;
	if (lastEntry.next == entry) {
	while (associatedMap.elementData[--position] == null) {
	// Do nothing
	}
	associatedMap.elementData[position] = associatedMap.elementData[position].next;
	entry = null;
	} else {
	lastEntry.next = entry;
	}
	associatedMap.elementCount--;
	expectedModCount++;
	}
	}

	static class HashMapEntrySet<KT, VT> extends AbstractSet<Map.Entry<KT, VT>> {
	private final HashMap<KT, VT> associatedMap;

	public HashMapEntrySet(HashMap<KT, VT> hm) {
	associatedMap = hm;
	}

	HashMap<KT, VT> hashMap() {
	return associatedMap;
	}

	@Override
	public int size() {
	return associatedMap.elementCount;
	}

	@Override
	public void clear() {
	associatedMap.clear();
	}

	@Override
	public boolean remove(Object object) {
	if (contains(object)) {
	associatedMap.remove(((Map.Entry<?, ?>) object).getKey());
	return true;
	}
	return false;
	}

	@Override
	public boolean contains(Object object) {
	if (object instanceof Map.Entry) {
	Object key = ((Map.Entry<?, ?>) object).getKey();
	Entry entry;
	if (key == null) {
	entry = associatedMap.findNullKeyEntry();
	} else {
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % associatedMap.elementData.length;
	entry = associatedMap.findNonNullKeyEntry(key, index, hash);
	}
	return object.equals(entry);
	}
	return false;
	}

	@Override
	public Iterator<Map.Entry<KT, VT>> iterator() {
	return new HashMapIterator<Map.Entry<KT, VT>, KT, VT>(
	new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
	public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) {
	return entry;
	}
	}, associatedMap);
	}
	}

	@SuppressWarnings("unchecked")
	Entry<K, V>[] newElementArray(int s) {
	return new Entry[s];
	}

	/**
	* Constructs a new empty {@code HashMap} instance.
	*
	* @since Android 1.0
	*/
	public HashMap() {
	this(DEFAULT_SIZE);
	}

	/**
	* Constructs a new {@code HashMap} instance with the specified capacity.
	*
	* @param capacity
	* the initial capacity of this hash map.
	* @throws IllegalArgumentException
	* when the capacity is less than zero.
	* @since Android 1.0
	*/
	public HashMap(int capacity) {
	if (capacity >= 0) {
	elementCount = 0;
	elementData = newElementArray(capacity == 0 ? 1 : capacity);
	loadFactor = 0.75f; // Default load factor of 0.75
	computeMaxSize();
	} else {
	throw new IllegalArgumentException();
	}
	}

	/**
	* Constructs a new {@code HashMap} instance with the specified capacity and
	* load factor.
	*
	* @param capacity
	* the initial capacity of this hash map.
	* @param loadFactor
	* the initial load factor.
	* @throws IllegalArgumentException
	* when the capacity is less than zero or the load factor is
	* less or equal to zero.
	* @since Android 1.0
	*/
	public HashMap(int capacity, float loadFactor) {
	if (capacity >= 0 && loadFactor > 0) {
	elementCount = 0;
	elementData = newElementArray(capacity == 0 ? 1 : capacity);
	this.loadFactor = loadFactor;
	computeMaxSize();
	} else {
	throw new IllegalArgumentException();
	}
	}

	/**
	* Constructs a new {@code HashMap} instance containing the mappings from
	* the specified map.
	*
	* @param map
	* the mappings to add.
	* @since Android 1.0
	*/
	public HashMap(Map<? extends K, ? extends V> map) {
	this(map.size() < 6 ? 11 : map.size() * 2);
	putAllImpl(map);
	}

	// BEGIN android-changed
	/**
	* Removes all mappings from this hash map, leaving it empty.
	*
	* @see #isEmpty
	* @see #size
	* @since Android 1.0
	*/
	@Override
	public void clear() {
	internalClear();
	}

	void internalClear() {
	if (elementCount > 0) {
	elementCount = 0;
	Arrays.fill(elementData, null);
	modCount++;
	}
	}
	// END android-changed

	/**
	* Returns a shallow copy of this map.
	*
	* @return a shallow copy of this map.
	* @since Android 1.0
	*/
	@Override
	@SuppressWarnings("unchecked")
	public Object clone() {
	try {
	// BEGIN android-changed
	// copied from newer version of harmony
	HashMap<K, V> map = (HashMap<K, V>) super.clone();
	map.elementData = newElementArray(elementData.length);
	map.internalClear();
	Entry<K, V> entry;
	for (int i = 0; i < elementData.length; i++) {
	if ((entry = elementData[i]) != null){
	map.putImpl(entry.getKey(), entry.getValue());
	while (entry.next != null){
	entry = entry.next;
	map.putImpl(entry.getKey(), entry.getValue());
	}
	}
	// END android-changed
	}
	return map;
	} catch (CloneNotSupportedException e) {
	return null;
	}
	}

	private void computeMaxSize() {
	threshold = (int) (elementData.length * loadFactor);
	}

	/**
	* Returns whether this map contains the specified key.
	*
	* @param key
	* the key to search for.
	* @return {@code true} if this map contains the specified key,
	* {@code false} otherwise.
	* @since Android 1.0
	*/
	@Override
	public boolean containsKey(Object key) {
	Entry<K, V> m;
	if (key == null) {
	m = findNullKeyEntry();
	} else {
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	m = findNonNullKeyEntry(key, index, hash);
	}
	return m != null;
	}

	/**
	* Returns whether this map contains the specified value.
	*
	* @param value
	* the value to search for.
	* @return {@code true} if this map contains the specified value,
	* {@code false} otherwise.
	* @since Android 1.0
	*/
	@Override
	public boolean containsValue(Object value) {
	if (value != null) {
	for (int i = elementData.length; --i >= 0;) {
	Entry<K, V> entry = elementData[i];
	while (entry != null) {
	if (value.equals(entry.value)) {
	return true;
	}
	entry = entry.next;
	}
	}
	} else {
	for (int i = elementData.length; --i >= 0;) {
	Entry<K, V> entry = elementData[i];
	while (entry != null) {
	if (entry.value == null) {
	return true;
	}
	entry = entry.next;
	}
	}
	}
	return false;
	}

	/**
	* Returns a set containing all of the mappings in this map. Each mapping is
	* an instance of {@link Map.Entry}. As the set is backed by this map,
	* changes in one will be reflected in the other.
	*
	* @return a set of the mappings.
	* @since Android 1.0
	*/
	@Override
	public Set<Map.Entry<K, V>> entrySet() {
	return new HashMapEntrySet<K, V>(this);
	}

	/**
	* Returns the value of the mapping with the specified key.
	*
	* @param key
	* the key.
	* @return the value of the mapping with the specified key, or {@code null}
	* if no mapping for the specified key is found.
	* @since Android 1.0
	*/
	@Override
	public V get(Object key) {
	Entry<K, V> m;
	if (key == null) {
	m = findNullKeyEntry();
	} else {
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	m = findNonNullKeyEntry(key, index, hash);
	}
	if (m != null) {
	return m.value;
	}
	return null;
	}

	final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) {
	Entry<K,V> m = elementData[index];
	// BEGIN android-changed
	// The VM can optimize String.equals but not Object.equals
	if (key instanceof String) {
	String keyString = (String) key;
	while (m != null) {
	if (m.origKeyHash == keyHash) {
	if (keyString.equals(m.key)) {
	return m;
	}
	}
	m = m.next;
	}
	} else {
	while (m != null) {
	if (m.origKeyHash == keyHash) {
	if (key.equals(m.key)) {
	return m;
	}
	}
	m = m.next;
	}
	}
	return null;
	// END android-changed
	}

	final Entry<K,V> findNullKeyEntry() {
	Entry<K,V> m = elementData[0];
	while (m != null && m.key != null)
	m = m.next;
	return m;
	}

	/**
	* Returns whether this map is empty.
	*
	* @return {@code true} if this map has no elements, {@code false}
	* otherwise.
	* @see #size()
	* @since Android 1.0
	*/
	@Override
	public boolean isEmpty() {
	return elementCount == 0;
	}

	/**
	* Returns a set of the keys contained in this map. The set is backed by
	* this map so changes to one are reflected by the other. The set does not
	* support adding.
	*
	* @return a set of the keys.
	* @since Android 1.0
	*/
	@Override
	public Set<K> keySet() {
	if (keySet == null) {
	keySet = new AbstractSet<K>() {
	@Override
	public boolean contains(Object object) {
	return containsKey(object);
	}

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

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

	@Override
	public boolean remove(Object key) {
	Entry<K, V> entry = HashMap.this.removeEntry(key);
	return entry != null;
	}

	@Override
	public Iterator<K> iterator() {
	return new HashMapIterator<K, K, V>(
	new MapEntry.Type<K, K, V>() {
	public K get(MapEntry<K, V> entry) {
	return entry.key;
	}
	}, HashMap.this);
	}
	};
	}
	return keySet;
	}

	/**
	* Maps the specified key to the specified value.
	*
	* @param key
	* the key.
	* @param value
	* the value.
	* @return the value of any previous mapping with the specified key or
	* {@code null} if there was no such mapping.
	* @since Android 1.0
	*/
	@Override
	public V put(K key, V value) {
	return putImpl(key, value);
	}

	private V putImpl(K key, V value) {
	Entry<K,V> entry;
	if(key == null) {
	entry = findNullKeyEntry();
	if (entry == null) {
	modCount++;
	if (++elementCount > threshold) {
	rehash();
	}
	entry = createHashedEntry(key, 0, 0);
	}
	} else {
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % elementData.length;
	entry = findNonNullKeyEntry(key, index, hash);
	if (entry == null) {
	modCount++;
	if (++elementCount > threshold) {
	rehash();
	index = (hash & 0x7FFFFFFF) % elementData.length;
	}
	entry = createHashedEntry(key, index, hash);
	}
	}

	V result = entry.value;
	entry.value = value;
	return result;
	}

	Entry<K, V> createEntry(K key, int index, V value) {
	Entry<K, V> entry = new Entry<K, V>(key, value);
	entry.next = elementData[index];
	elementData[index] = entry;
	return entry;
	}

	Entry<K,V> createHashedEntry(K key, int index, int hash) {
	Entry<K,V> entry = new Entry<K,V>(key,hash);
	entry.next = elementData[index];
	elementData[index] = entry;
	return entry;
	}

	/**
	* Copies all the mappings in the specified map to this map. These mappings
	* will replace all mappings that this map had for any of the keys currently
	* in the given map.
	*
	* @param map
	* the map to copy mappings from.
	* @since Android 1.0
	*/
	@Override
	public void putAll(Map<? extends K, ? extends V> map) {
	if (!map.isEmpty()) {
	putAllImpl(map);
	}
	}

	private void putAllImpl(Map<? extends K, ? extends V> map) {
	int capacity = elementCount + map.size();
	if (capacity > threshold) {
	rehash(capacity);
	}
	for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
	putImpl(entry.getKey(), entry.getValue());
	}
	}

	void rehash(int capacity) {
	int length = (capacity == 0 ? 1 : capacity << 1);

	Entry<K, V>[] newData = newElementArray(length);
	for (int i = 0; i < elementData.length; i++) {
	Entry<K, V> entry = elementData[i];
	while (entry != null) {
	int index = (entry.origKeyHash & 0x7FFFFFFF) % length;
	Entry<K, V> next = entry.next;
	entry.next = newData[index];
	newData[index] = entry;
	entry = next;
	}
	}
	elementData = newData;
	computeMaxSize();
	}

	void rehash() {
	rehash(elementData.length);
	}

	/**
	* Removes the mapping with the specified key from this map.
	*
	* @param key
	* the key of the mapping to remove.
	* @return the value of the removed mapping or {@code null} if no mapping
	* for the specified key was found.
	* @since Android 1.0
	*/
	@Override
	public V remove(Object key) {
	Entry<K, V> entry = removeEntry(key);
	if (entry != null) {
	return entry.value;
	}
	return null;
	}

	Entry<K, V> removeEntry(Object key) {
	int index = 0;
	Entry<K, V> entry;
	Entry<K, V> last = null;
	if (key != null) {
	int hash = key.hashCode();
	index = (hash & 0x7FFFFFFF) % elementData.length;
	entry = elementData[index];
	while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key))) {
	last = entry;
	entry = entry.next;
	}
	} else {
	entry = elementData[0];
	while (entry != null && entry.key != null) {
	last = entry;
	entry = entry.next;
	}
	}
	if (entry == null) {
	return null;
	}
	if (last == null) {
	elementData[index] = entry.next;
	} else {
	last.next = entry.next;
	}
	modCount++;
	elementCount--;
	return entry;
	}

	/**
	* Returns the number of elements in this map.
	*
	* @return the number of elements in this map.
	* @since Android 1.0
	*/
	@Override
	public int size() {
	return elementCount;
	}

	/**
	* Returns a collection of the values contained in this map. The collection
	* is backed by this map so changes to one are reflected by the other. The
	* collection supports remove, removeAll, retainAll and clear operations,
	* and it does not support add or addAll operations.
	* <p>
	* This method returns a collection which is the subclass of
	* AbstractCollection. The iterator method of this subclass returns a
	* "wrapper object" over the iterator of map's entrySet(). The {@code size}
	* method wraps the map's size method and the {@code contains} method wraps
	* the map's containsValue method.
	* </p>
	* <p>
	* The collection is created when this method is called for the first time
	* and returned in response to all subsequent calls. This method may return
	* different collections when multiple concurrent calls occur, since no
	* synchronization is performed.
	* </p>
	*
	* @return a collection of the values contained in this map.
	* @since Android 1.0
	*/
	@Override
	public Collection<V> values() {
	if (valuesCollection == null) {
	valuesCollection = new AbstractCollection<V>() {
	@Override
	public boolean contains(Object object) {
	return containsValue(object);
	}

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

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

	@Override
	public Iterator<V> iterator() {
	return new HashMapIterator<V, K, V>(
	new MapEntry.Type<V, K, V>() {
	public V get(MapEntry<K, V> entry) {
	return entry.value;
	}
	}, HashMap.this);
	}
	};
	}
	return valuesCollection;
	}

	private void writeObject(ObjectOutputStream stream) throws IOException {
	stream.defaultWriteObject();
	stream.writeInt(elementData.length);
	stream.writeInt(elementCount);
	Iterator<?> iterator = entrySet().iterator();
	while (iterator.hasNext()) {
	Entry<?, ?> entry = (Entry<?, ?>) iterator.next();
	stream.writeObject(entry.key);
	stream.writeObject(entry.value);
	entry = entry.next;
	}
	}

	@SuppressWarnings("unchecked")
	private void readObject(ObjectInputStream stream) throws IOException,
	ClassNotFoundException {
	stream.defaultReadObject();
	int length = stream.readInt();
	elementData = newElementArray(length);
	elementCount = stream.readInt();
	for (int i = elementCount; --i >= 0;) {
	K key = (K) stream.readObject();
	int index = (null == key) ? 0 : (key.hashCode() & 0x7FFFFFFF)
	% length;
	createEntry(key, index, (V) stream.readObject());
	}
	}

	}