2.4/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java - gwt - Git at Google

 /*
  * Copyright 2009 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 com.google.gwt.dev.util.collect;

 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.AbstractCollection;
 import java.util.AbstractSet;
 import java.util.Collection;
 import java.util.ConcurrentModificationException;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;

 /**
  * A memory-efficient hash map.
  *
  * @param <K> the key type
  * @param <V> the value type
  */
 public class HashMap<K, V> implements Map<K, V>, Serializable {

   /**
    * In the interest of memory-savings, we start with the smallest feasible
    * power-of-two table size that can hold three items without rehashing. If we
    * started with a size of 2, we'd have to expand as soon as the second item
    * was added.
    */
   private static final int INITIAL_TABLE_SIZE = 4;

   private abstract class BaseIterator<E> implements Iterator<E> {
     private Object[] coModCheckKeys = keys;
     private int index = 0;
     private int last = -1;

     public boolean hasNext() {
       if (coModCheckKeys != keys) {
         throw new ConcurrentModificationException();
       }
       advanceToItem();
       return index < keys.length;
     }

     public E next() {
       if (!hasNext()) {
         throw new NoSuchElementException();
       }
       last = index;
       return iteratorItem(index++);
     }

     public void remove() {
       if (last < 0) {
         throw new IllegalStateException();
       }
       if (coModCheckKeys != keys) {
         throw new ConcurrentModificationException();
       }
       internalRemove(last);
       if (keys[last] != null) {
         // Hole was plugged.
         index = last;
       }
       last = -1;
     }

     protected abstract E iteratorItem(int index);

     private void advanceToItem() {
       for (; index < keys.length; ++index) {
         if (keys[index] != null) {
           return;
         }
       }
     }
   }

   private class EntryIterator extends BaseIterator<Entry<K, V>> {
     @Override
     protected Entry<K, V> iteratorItem(int index) {
       return new HashEntry(index);
     }
   }

   private class EntrySet extends AbstractSet<Entry<K, V>> {
     @Override
     public boolean add(Entry<K, V> entry) {
       boolean result = !HashMap.this.containsKey(entry.getKey());
       HashMap.this.put(entry.getKey(), entry.getValue());
       return result;
     }

     @Override
     public boolean addAll(Collection<? extends Entry<K, V>> c) {
       HashMap.this.resizeForJoin(c.size());
       return super.addAll(c);
     }

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

     @Override
     @SuppressWarnings("unchecked")
     public boolean contains(Object o) {
       if (!(o instanceof Entry)) {
         return false;
       }
       Entry<K, V> entry = (Entry<K, V>) o;
       V value = HashMap.this.get(entry.getKey());
       return HashMap.this.valueEquals(value, entry.getValue());
     }

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

     @Override
     public Iterator<java.util.Map.Entry<K, V>> iterator() {
       return new EntryIterator();
     }

     @Override
     @SuppressWarnings("unchecked")
     public boolean remove(Object o) {
       if (!(o instanceof Entry)) {
         return false;
       }
       Entry<K, V> entry = (Entry<K, V>) o;
       int index = findKey(entry.getKey());
       if (index >= 0 && valueEquals(values[index], entry.getValue())) {
         internalRemove(index);
         return true;
       }
       return false;
     }

     @Override
     public boolean removeAll(Collection<?> c) {
       boolean didRemove = false;
       for (Object o : c) {
         didRemove |= remove(o);
       }
       return didRemove;
     }

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

   private class HashEntry implements Entry<K, V> {
     private final int index;

     public HashEntry(int index) {
       this.index = index;
     }

     @Override
     @SuppressWarnings("unchecked")
     public boolean equals(Object o) {
       if (!(o instanceof Entry)) {
         return false;
       }
       Entry<K, V> entry = (Entry<K, V>) o;
       return keyEquals(getKey(), entry.getKey())
           && valueEquals(getValue(), entry.getValue());
     }

     @SuppressWarnings("unchecked")
     public K getKey() {
       return (K) unmaskNullKey(keys[index]);
     }

     @SuppressWarnings("unchecked")
     public V getValue() {
       return (V) values[index];
     }

     @Override
     public int hashCode() {
       return keyHashCode(getKey()) ^ valueHashCode(getValue());
     }

     @SuppressWarnings("unchecked")
     public V setValue(V value) {
       V previous = (V) values[index];
       values[index] = value;
       return previous;
     }

     @Override
     public String toString() {
       return getKey() + "=" + getValue();
     }
   }

   private class KeyIterator extends BaseIterator<K> {
     @SuppressWarnings("unchecked")
     @Override
     protected K iteratorItem(int index) {
       return (K) unmaskNullKey(keys[index]);
     }
   }

   private class KeySet extends AbstractSet<K> {
     @Override
     public void clear() {
       HashMap.this.clear();
     }

     @Override
     public boolean contains(Object o) {
       return HashMap.this.containsKey(o);
     }

     @Override
     public int hashCode() {
       int result = 0;
       for (int i = 0; i < keys.length; ++i) {
         Object key = keys[i];
         if (key != null) {
           result += keyHashCode(unmaskNullKey(key));
         }
       }
       return result;
     }

     @Override
     public Iterator<K> iterator() {
       return new KeyIterator();
     }

     @Override
     public boolean remove(Object o) {
       int index = findKey(o);
       if (index >= 0) {
         internalRemove(index);
         return true;
       }
       return false;
     }

     @Override
     public boolean removeAll(Collection<?> c) {
       boolean didRemove = false;
       for (Object o : c) {
         didRemove |= remove(o);
       }
       return didRemove;
     }

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

   private class ValueIterator extends BaseIterator<V> {
     @SuppressWarnings("unchecked")
     @Override
     protected V iteratorItem(int index) {
       return (V) values[index];
     }
   }

   private class Values extends AbstractCollection<V> {
     @Override
     public void clear() {
       HashMap.this.clear();
     }

     @Override
     public boolean contains(Object o) {
       return HashMap.this.containsValue(o);
     }

     @Override
     public int hashCode() {
       int result = 0;
       for (int i = 0; i < keys.length; ++i) {
         if (keys[i] != null) {
           result += valueHashCode(values[i]);
         }
       }
       return result;
     }

     @Override
     public Iterator<V> iterator() {
       return new ValueIterator();
     }

     @Override
     public boolean remove(Object o) {
       if (o == null) {
         for (int i = 0; i < keys.length; ++i) {
           if (keys[i] != null && values[i] == null) {
             internalRemove(i);
             return true;
           }
         }
       } else {
         for (int i = 0; i < keys.length; ++i) {
           if (valueEquals(values[i], o)) {
             internalRemove(i);
             return true;
           }
         }
       }
       return false;
     }

     @Override
     public boolean removeAll(Collection<?> c) {
       boolean didRemove = false;
       for (Object o : c) {
         didRemove |= remove(o);
       }
       return didRemove;
     }

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

   private static final Object NULL_KEY = new Serializable() {
     Object readResolve() {
       return NULL_KEY;
     }
   };

   static Object maskNullKey(Object k) {
     return (k == null) ? NULL_KEY : k;
   }

   static Object unmaskNullKey(Object k) {
     return (k == NULL_KEY) ? null : k;
   }

   /**
    * Backing store for all the keys; transient due to custom serialization.
    * Default access to avoid synthetic accessors from inner classes.
    */
   transient Object[] keys;

   /**
    * Number of pairs in this set; transient due to custom serialization. Default
    * access to avoid synthetic accessors from inner classes.
    */
   transient int size = 0;

   /**
    * Backing store for all the values; transient due to custom serialization.
    * Default access to avoid synthetic accessors from inner classes.
    */
   transient Object[] values;

   public HashMap() {
     initTable(INITIAL_TABLE_SIZE);
   }

   public HashMap(Map<? extends K, ? extends V> m) {
     int newCapacity = INITIAL_TABLE_SIZE;
     int expectedSize = m.size();
     while (newCapacity * 3 < expectedSize * 4) {
       newCapacity <<= 1;
     }

     initTable(newCapacity);
     putAll(m);
   }

   public void clear() {
     initTable(INITIAL_TABLE_SIZE);
     size = 0;
   }

   public boolean containsKey(Object key) {
     return findKey(key) >= 0;
   }

   public boolean containsValue(Object value) {
     if (value == null) {
       for (int i = 0; i < keys.length; ++i) {
         if (keys[i] != null && values[i] == null) {
           return true;
         }
       }
     } else {
       for (Object existing : values) {
         if (valueEquals(existing, value)) {
           return true;
         }
       }
     }
     return false;
   }

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

   @Override
   @SuppressWarnings("unchecked")
   public boolean equals(Object o) {
     if (!(o instanceof Map)) {
       return false;
     }
     Map<K, V> other = (Map<K, V>) o;
     return entrySet().equals(other.entrySet());
   }

   @SuppressWarnings("unchecked")
   public V get(Object key) {
     int index = findKey(key);
     return (index < 0) ? null : (V) values[index];
   }

   @Override
   public int hashCode() {
     int result = 0;
     for (int i = 0; i < keys.length; ++i) {
       Object key = keys[i];
       if (key != null) {
         result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
       }
     }
     return result;
   }

   public boolean isEmpty() {
     return size == 0;
   }

   public Set<K> keySet() {
     return new KeySet();
   }

   @SuppressWarnings("unchecked")
   public V put(K key, V value) {
     int index = findKeyOrEmpty(key);
     if (keys[index] == null) {
       // Not in the map, may need to grow.
       if (ensureSizeFor(++size)) {
         // If we had to grow the table, must recompute the index.
         index = findKeyOrEmpty(key);
       }
       keys[index] = maskNullKey(key);
       values[index] = value;
       return null;
     } else {
       // In the map, set a new value;
       Object previousValue = values[index];
       values[index] = value;
       return (V) previousValue;
     }
   }

   public void putAll(Map<? extends K, ? extends V> m) {
     resizeForJoin(m.size());
     for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
       put(entry.getKey(), entry.getValue());
     }
   }

   @SuppressWarnings("unchecked")
   public V remove(Object key) {
     int index = findKey(key);
     if (index < 0) {
       return null;
     }
     Object previousValue = values[index];
     internalRemove(index);
     return (V) previousValue;
   }

   public int size() {
     return size;
   }

   @Override
   public String toString() {
     if (size == 0) {
       return "{}";
     }
     StringBuilder buf = new StringBuilder(32 * size());
     buf.append('{');

     boolean needComma = false;
     for (int i = 0; i < keys.length; ++i) {
       Object key = keys[i];
       if (key != null) {
         if (needComma) {
           buf.append(',').append(' ');
         }
         key = unmaskNullKey(key);
         Object value = values[i];
         buf.append(key == this ? "(this Map)" : key).append('=').append(
             value == this ? "(this Map)" : value);
         needComma = true;
       }
     }
     buf.append('}');
     return buf.toString();
   }

   public Collection<V> values() {
     return new Values();
   }

   /**
    * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
    */
   @SuppressWarnings("unchecked")
   protected void doReadObject(ObjectInputStream in) throws IOException,
       ClassNotFoundException {
     int capacity = in.readInt();
     initTable(capacity);
     int items = in.readInt();
     for (int i = 0; i < items; i++) {
       Object key = in.readObject();
       Object value = in.readObject();
       put((K) key, (V) value);
     }
   }

   /**
    * Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
    */
   protected void doWriteObject(ObjectOutputStream out) throws IOException {
     out.writeInt(keys.length);
     out.writeInt(size);
     for (int i = 0; i < keys.length; ++i) {
       Object key = keys[i];
       if (key != null) {
         out.writeObject(unmaskNullKey(key));
         out.writeObject(values[i]);
       }
     }
   }

   /**
    * Returns whether two keys are equal for the purposes of this set.
    */
   protected boolean keyEquals(Object a, Object b) {
     return (a == null) ? (b == null) : a.equals(b);
   }

   /**
    * Returns the hashCode for a key.
    */
   protected int keyHashCode(Object k) {
     return (k == null) ? 0 : k.hashCode();
   }

   /**
    * Returns whether two values are equal for the purposes of this set.
    */
   protected boolean valueEquals(Object a, Object b) {
     return (a == null) ? (b == null) : a.equals(b);
   }

   /**
    * Returns the hashCode for a value.
    */
   protected int valueHashCode(Object v) {
     return (v == null) ? 0 : v.hashCode();
   }

   /**
    * Ensures the map is large enough to contain the specified number of entries.
    * Default access to avoid synthetic accessors from inner classes.
    */
   boolean ensureSizeFor(int expectedSize) {
     if (keys.length * 3 >= expectedSize * 4) {
       return false;
     }

     int newCapacity = keys.length << 1;
     while (newCapacity * 3 < expectedSize * 4) {
       newCapacity <<= 1;
     }

     Object[] oldKeys = keys;
     Object[] oldValues = values;
     initTable(newCapacity);
     for (int i = 0; i < oldKeys.length; ++i) {
       Object k = oldKeys[i];
       if (k != null) {
         int newIndex = getKeyIndex(unmaskNullKey(k));
         while (keys[newIndex] != null) {
           if (++newIndex == keys.length) {
             newIndex = 0;
           }
         }
         keys[newIndex] = k;
         values[newIndex] = oldValues[i];
       }
     }
     return true;
   }

   /**
    * Returns the index in the key table at which a particular key resides, or -1
    * if the key is not in the table. Default access to avoid synthetic accessors
    * from inner classes.
    */
   int findKey(Object k) {
     int index = getKeyIndex(k);
     while (true) {
       Object existing = keys[index];
       if (existing == null) {
         return -1;
       }
       if (keyEquals(k, unmaskNullKey(existing))) {
         return index;
       }
       if (++index == keys.length) {
         index = 0;
       }
     }
   }

   /**
    * Returns the index in the key table at which a particular key resides, or
    * the index of an empty slot in the table where this key should be inserted
    * if it is not already in the table. Default access to avoid synthetic
    * accessors from inner classes.
    */
   int findKeyOrEmpty(Object k) {
     int index = getKeyIndex(k);
     while (true) {
       Object existing = keys[index];
       if (existing == null) {
         return index;
       }
       if (keyEquals(k, unmaskNullKey(existing))) {
         return index;
       }
       if (++index == keys.length) {
         index = 0;
       }
     }
   }

   /**
    * Removes the entry at the specified index, and performs internal management
    * to make sure we don't wind up with a hole in the table. Default access to
    * avoid synthetic accessors from inner classes.
    */
   void internalRemove(int index) {
     keys[index] = null;
     values[index] = null;
     --size;
     plugHole(index);
   }

   /**
    * Resizes this map to accommodate the minimum size required to join this map
    * with another map. This is an optimization to prevent multiple resizes
    * during the join operation. Naively, it would seem like we should resize to
    * hold {@code (size + otherSize)}. However, the incoming map might have
    * duplicates with this map; it might even be all duplicates. The correct
    * behavior when the incoming map is all duplicates is NOT to resize, and
    * therefore not to invalidate any iterators.
    * <p>
    * In practice, this strategy results in a worst-case of two resizes. In the
    * worst case, where {@code size} and {@code otherSize} are roughly equal and
    * the sets are completely disjoint, we might do 1 initial rehash and then 1
    * additional rehash down the road. But this is an edge case that requires
    * getting unlucky on both boundaries. Most of the time, we do either 1
    * initial rehash or 1 down the road, because doubling the capacity generally
    * allows this map to absorb an equally-sized disjoint map.
    */
   boolean resizeForJoin(int sizeOther) {
     return ensureSizeFor(Math.max(size, sizeOther));
   }

   private int getKeyIndex(Object k) {
     int h = keyHashCode(k);
     // Copied from Apache's AbstractHashedMap; prevents power-of-two collisions.
     h += ~(h << 9);
     h ^= (h >>> 14);
     h += (h << 4);
     h ^= (h >>> 10);
     // Power of two trick.
     return h & (keys.length - 1);
   }

   private void initTable(int capacity) {
     keys = new Object[capacity];
     values = new Object[capacity];
   }

   /**
    * Tricky, we left a hole in the map, which we have to fill. The only way to
    * do this is to search forwards through the map shuffling back values that
    * match this index until we hit a null.
    */
   private void plugHole(int hole) {
     int index = hole + 1;
     if (index == keys.length) {
       index = 0;
     }
     while (keys[index] != null) {
       int targetIndex = getKeyIndex(unmaskNullKey(keys[index]));
       if (hole < index) {
         /*
          * "Normal" case, the index is past the hole and the "bad range" is from
          * hole (exclusive) to index (inclusive).
          */
         if (!(hole < targetIndex && targetIndex <= index)) {
           // Plug it!
           keys[hole] = keys[index];
           values[hole] = values[index];
           keys[index] = null;
           values[index] = null;
           hole = index;
         }
       } else {
         /*
          * "Wrapped" case, the index is before the hole (we've wrapped) and the
          * "good range" is from index (exclusive) to hole (inclusive).
          */
         if (index < targetIndex && targetIndex <= hole) {
           // Plug it!
           keys[hole] = keys[index];
           values[hole] = values[index];
           keys[index] = null;
           values[index] = null;
           hole = index;
         }
       }
       if (++index == keys.length) {
         index = 0;
       }
     }
   }

   private void readObject(ObjectInputStream in) throws IOException,
       ClassNotFoundException {
     in.defaultReadObject();
     doReadObject(in);
   }

   private void writeObject(ObjectOutputStream out) throws IOException {
     out.defaultWriteObject();
     doWriteObject(out);
   }
 }
	/*
	* Copyright 2009 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 com.google.gwt.dev.util.collect;

	import java.io.IOException;
	import java.io.ObjectInputStream;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;
	import java.util.AbstractCollection;
	import java.util.AbstractSet;
	import java.util.Collection;
	import java.util.ConcurrentModificationException;
	import java.util.Iterator;
	import java.util.Map;
	import java.util.NoSuchElementException;
	import java.util.Set;

	/**
	* A memory-efficient hash map.
	*
	* @param <K> the key type
	* @param <V> the value type
	*/
	public class HashMap<K, V> implements Map<K, V>, Serializable {

	/**
	* In the interest of memory-savings, we start with the smallest feasible
	* power-of-two table size that can hold three items without rehashing. If we
	* started with a size of 2, we'd have to expand as soon as the second item
	* was added.
	*/
	private static final int INITIAL_TABLE_SIZE = 4;

	private abstract class BaseIterator<E> implements Iterator<E> {
	private Object[] coModCheckKeys = keys;
	private int index = 0;
	private int last = -1;

	public boolean hasNext() {
	if (coModCheckKeys != keys) {
	throw new ConcurrentModificationException();
	}
	advanceToItem();
	return index < keys.length;
	}

	public E next() {
	if (!hasNext()) {
	throw new NoSuchElementException();
	}
	last = index;
	return iteratorItem(index++);
	}

	public void remove() {
	if (last < 0) {
	throw new IllegalStateException();
	}
	if (coModCheckKeys != keys) {
	throw new ConcurrentModificationException();
	}
	internalRemove(last);
	if (keys[last] != null) {
	// Hole was plugged.
	index = last;
	}
	last = -1;
	}

	protected abstract E iteratorItem(int index);

	private void advanceToItem() {
	for (; index < keys.length; ++index) {
	if (keys[index] != null) {
	return;
	}
	}
	}
	}

	private class EntryIterator extends BaseIterator<Entry<K, V>> {
	@Override
	protected Entry<K, V> iteratorItem(int index) {
	return new HashEntry(index);
	}
	}

	private class EntrySet extends AbstractSet<Entry<K, V>> {
	@Override
	public boolean add(Entry<K, V> entry) {
	boolean result = !HashMap.this.containsKey(entry.getKey());
	HashMap.this.put(entry.getKey(), entry.getValue());
	return result;
	}

	@Override
	public boolean addAll(Collection<? extends Entry<K, V>> c) {
	HashMap.this.resizeForJoin(c.size());
	return super.addAll(c);
	}

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

	@Override
	@SuppressWarnings("unchecked")
	public boolean contains(Object o) {
	if (!(o instanceof Entry)) {
	return false;
	}
	Entry<K, V> entry = (Entry<K, V>) o;
	V value = HashMap.this.get(entry.getKey());
	return HashMap.this.valueEquals(value, entry.getValue());
	}

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

	@Override
	public Iterator<java.util.Map.Entry<K, V>> iterator() {
	return new EntryIterator();
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean remove(Object o) {
	if (!(o instanceof Entry)) {
	return false;
	}
	Entry<K, V> entry = (Entry<K, V>) o;
	int index = findKey(entry.getKey());
	if (index >= 0 && valueEquals(values[index], entry.getValue())) {
	internalRemove(index);
	return true;
	}
	return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
	boolean didRemove = false;
	for (Object o : c) {
	didRemove \|= remove(o);
	}
	return didRemove;
	}

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

	private class HashEntry implements Entry<K, V> {
	private final int index;

	public HashEntry(int index) {
	this.index = index;
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean equals(Object o) {
	if (!(o instanceof Entry)) {
	return false;
	}
	Entry<K, V> entry = (Entry<K, V>) o;
	return keyEquals(getKey(), entry.getKey())
	&& valueEquals(getValue(), entry.getValue());
	}

	@SuppressWarnings("unchecked")
	public K getKey() {
	return (K) unmaskNullKey(keys[index]);
	}

	@SuppressWarnings("unchecked")
	public V getValue() {
	return (V) values[index];
	}

	@Override
	public int hashCode() {
	return keyHashCode(getKey()) ^ valueHashCode(getValue());
	}

	@SuppressWarnings("unchecked")
	public V setValue(V value) {
	V previous = (V) values[index];
	values[index] = value;
	return previous;
	}

	@Override
	public String toString() {
	return getKey() + "=" + getValue();
	}
	}

	private class KeyIterator extends BaseIterator<K> {
	@SuppressWarnings("unchecked")
	@Override
	protected K iteratorItem(int index) {
	return (K) unmaskNullKey(keys[index]);
	}
	}

	private class KeySet extends AbstractSet<K> {
	@Override
	public void clear() {
	HashMap.this.clear();
	}

	@Override
	public boolean contains(Object o) {
	return HashMap.this.containsKey(o);
	}

	@Override
	public int hashCode() {
	int result = 0;
	for (int i = 0; i < keys.length; ++i) {
	Object key = keys[i];
	if (key != null) {
	result += keyHashCode(unmaskNullKey(key));
	}
	}
	return result;
	}

	@Override
	public Iterator<K> iterator() {
	return new KeyIterator();
	}

	@Override
	public boolean remove(Object o) {
	int index = findKey(o);
	if (index >= 0) {
	internalRemove(index);
	return true;
	}
	return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
	boolean didRemove = false;
	for (Object o : c) {
	didRemove \|= remove(o);
	}
	return didRemove;
	}

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

	private class ValueIterator extends BaseIterator<V> {
	@SuppressWarnings("unchecked")
	@Override
	protected V iteratorItem(int index) {
	return (V) values[index];
	}
	}

	private class Values extends AbstractCollection<V> {
	@Override
	public void clear() {
	HashMap.this.clear();
	}

	@Override
	public boolean contains(Object o) {
	return HashMap.this.containsValue(o);
	}

	@Override
	public int hashCode() {
	int result = 0;
	for (int i = 0; i < keys.length; ++i) {
	if (keys[i] != null) {
	result += valueHashCode(values[i]);
	}
	}
	return result;
	}

	@Override
	public Iterator<V> iterator() {
	return new ValueIterator();
	}

	@Override
	public boolean remove(Object o) {
	if (o == null) {
	for (int i = 0; i < keys.length; ++i) {
	if (keys[i] != null && values[i] == null) {
	internalRemove(i);
	return true;
	}
	}
	} else {
	for (int i = 0; i < keys.length; ++i) {
	if (valueEquals(values[i], o)) {
	internalRemove(i);
	return true;
	}
	}
	}
	return false;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
	boolean didRemove = false;
	for (Object o : c) {
	didRemove \|= remove(o);
	}
	return didRemove;
	}

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

	private static final Object NULL_KEY = new Serializable() {
	Object readResolve() {
	return NULL_KEY;
	}
	};

	static Object maskNullKey(Object k) {
	return (k == null) ? NULL_KEY : k;
	}

	static Object unmaskNullKey(Object k) {
	return (k == NULL_KEY) ? null : k;
	}

	/**
	* Backing store for all the keys; transient due to custom serialization.
	* Default access to avoid synthetic accessors from inner classes.
	*/
	transient Object[] keys;

	/**
	* Number of pairs in this set; transient due to custom serialization. Default
	* access to avoid synthetic accessors from inner classes.
	*/
	transient int size = 0;

	/**
	* Backing store for all the values; transient due to custom serialization.
	* Default access to avoid synthetic accessors from inner classes.
	*/
	transient Object[] values;

	public HashMap() {
	initTable(INITIAL_TABLE_SIZE);
	}

	public HashMap(Map<? extends K, ? extends V> m) {
	int newCapacity = INITIAL_TABLE_SIZE;
	int expectedSize = m.size();
	while (newCapacity * 3 < expectedSize * 4) {
	newCapacity <<= 1;
	}

	initTable(newCapacity);
	putAll(m);
	}

	public void clear() {
	initTable(INITIAL_TABLE_SIZE);
	size = 0;
	}

	public boolean containsKey(Object key) {
	return findKey(key) >= 0;
	}

	public boolean containsValue(Object value) {
	if (value == null) {
	for (int i = 0; i < keys.length; ++i) {
	if (keys[i] != null && values[i] == null) {
	return true;
	}
	}
	} else {
	for (Object existing : values) {
	if (valueEquals(existing, value)) {
	return true;
	}
	}
	}
	return false;
	}

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

	@Override
	@SuppressWarnings("unchecked")
	public boolean equals(Object o) {
	if (!(o instanceof Map)) {
	return false;
	}
	Map<K, V> other = (Map<K, V>) o;
	return entrySet().equals(other.entrySet());
	}

	@SuppressWarnings("unchecked")
	public V get(Object key) {
	int index = findKey(key);
	return (index < 0) ? null : (V) values[index];
	}

	@Override
	public int hashCode() {
	int result = 0;
	for (int i = 0; i < keys.length; ++i) {
	Object key = keys[i];
	if (key != null) {
	result += keyHashCode(unmaskNullKey(key)) ^ valueHashCode(values[i]);
	}
	}
	return result;
	}

	public boolean isEmpty() {
	return size == 0;
	}

	public Set<K> keySet() {
	return new KeySet();
	}

	@SuppressWarnings("unchecked")
	public V put(K key, V value) {
	int index = findKeyOrEmpty(key);
	if (keys[index] == null) {
	// Not in the map, may need to grow.
	if (ensureSizeFor(++size)) {
	// If we had to grow the table, must recompute the index.
	index = findKeyOrEmpty(key);
	}
	keys[index] = maskNullKey(key);
	values[index] = value;
	return null;
	} else {
	// In the map, set a new value;
	Object previousValue = values[index];
	values[index] = value;
	return (V) previousValue;
	}
	}

	public void putAll(Map<? extends K, ? extends V> m) {
	resizeForJoin(m.size());
	for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
	put(entry.getKey(), entry.getValue());
	}
	}

	@SuppressWarnings("unchecked")
	public V remove(Object key) {
	int index = findKey(key);
	if (index < 0) {
	return null;
	}
	Object previousValue = values[index];
	internalRemove(index);
	return (V) previousValue;
	}

	public int size() {
	return size;
	}

	@Override
	public String toString() {
	if (size == 0) {
	return "{}";
	}
	StringBuilder buf = new StringBuilder(32 * size());
	buf.append('{');

	boolean needComma = false;
	for (int i = 0; i < keys.length; ++i) {
	Object key = keys[i];
	if (key != null) {
	if (needComma) {
	buf.append(',').append(' ');
	}
	key = unmaskNullKey(key);
	Object value = values[i];
	buf.append(key == this ? "(this Map)" : key).append('=').append(
	value == this ? "(this Map)" : value);
	needComma = true;
	}
	}
	buf.append('}');
	return buf.toString();
	}

	public Collection<V> values() {
	return new Values();
	}

	/**
	* Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
	*/
	@SuppressWarnings("unchecked")
	protected void doReadObject(ObjectInputStream in) throws IOException,
	ClassNotFoundException {
	int capacity = in.readInt();
	initTable(capacity);
	int items = in.readInt();
	for (int i = 0; i < items; i++) {
	Object key = in.readObject();
	Object value = in.readObject();
	put((K) key, (V) value);
	}
	}

	/**
	* Adapted from {@link org.apache.commons.collections.map.AbstractHashedMap}.
	*/
	protected void doWriteObject(ObjectOutputStream out) throws IOException {
	out.writeInt(keys.length);
	out.writeInt(size);
	for (int i = 0; i < keys.length; ++i) {
	Object key = keys[i];
	if (key != null) {
	out.writeObject(unmaskNullKey(key));
	out.writeObject(values[i]);
	}
	}
	}

	/**
	* Returns whether two keys are equal for the purposes of this set.
	*/
	protected boolean keyEquals(Object a, Object b) {
	return (a == null) ? (b == null) : a.equals(b);
	}

	/**
	* Returns the hashCode for a key.
	*/
	protected int keyHashCode(Object k) {
	return (k == null) ? 0 : k.hashCode();
	}

	/**
	* Returns whether two values are equal for the purposes of this set.
	*/
	protected boolean valueEquals(Object a, Object b) {
	return (a == null) ? (b == null) : a.equals(b);
	}

	/**
	* Returns the hashCode for a value.
	*/
	protected int valueHashCode(Object v) {
	return (v == null) ? 0 : v.hashCode();
	}

	/**
	* Ensures the map is large enough to contain the specified number of entries.
	* Default access to avoid synthetic accessors from inner classes.
	*/
	boolean ensureSizeFor(int expectedSize) {
	if (keys.length * 3 >= expectedSize * 4) {
	return false;
	}

	int newCapacity = keys.length << 1;
	while (newCapacity * 3 < expectedSize * 4) {
	newCapacity <<= 1;
	}

	Object[] oldKeys = keys;
	Object[] oldValues = values;
	initTable(newCapacity);
	for (int i = 0; i < oldKeys.length; ++i) {
	Object k = oldKeys[i];
	if (k != null) {
	int newIndex = getKeyIndex(unmaskNullKey(k));
	while (keys[newIndex] != null) {
	if (++newIndex == keys.length) {
	newIndex = 0;
	}
	}
	keys[newIndex] = k;
	values[newIndex] = oldValues[i];
	}
	}
	return true;
	}

	/**
	* Returns the index in the key table at which a particular key resides, or -1
	* if the key is not in the table. Default access to avoid synthetic accessors
	* from inner classes.
	*/
	int findKey(Object k) {
	int index = getKeyIndex(k);
	while (true) {
	Object existing = keys[index];
	if (existing == null) {
	return -1;
	}
	if (keyEquals(k, unmaskNullKey(existing))) {
	return index;
	}
	if (++index == keys.length) {
	index = 0;
	}
	}
	}

	/**
	* Returns the index in the key table at which a particular key resides, or
	* the index of an empty slot in the table where this key should be inserted
	* if it is not already in the table. Default access to avoid synthetic
	* accessors from inner classes.
	*/
	int findKeyOrEmpty(Object k) {
	int index = getKeyIndex(k);
	while (true) {
	Object existing = keys[index];
	if (existing == null) {
	return index;
	}
	if (keyEquals(k, unmaskNullKey(existing))) {
	return index;
	}
	if (++index == keys.length) {
	index = 0;
	}
	}
	}

	/**
	* Removes the entry at the specified index, and performs internal management
	* to make sure we don't wind up with a hole in the table. Default access to
	* avoid synthetic accessors from inner classes.
	*/
	void internalRemove(int index) {
	keys[index] = null;
	values[index] = null;
	--size;
	plugHole(index);
	}

	/**
	* Resizes this map to accommodate the minimum size required to join this map
	* with another map. This is an optimization to prevent multiple resizes
	* during the join operation. Naively, it would seem like we should resize to
	* hold {@code (size + otherSize)}. However, the incoming map might have
	* duplicates with this map; it might even be all duplicates. The correct
	* behavior when the incoming map is all duplicates is NOT to resize, and
	* therefore not to invalidate any iterators.
	* <p>
	* In practice, this strategy results in a worst-case of two resizes. In the
	* worst case, where {@code size} and {@code otherSize} are roughly equal and
	* the sets are completely disjoint, we might do 1 initial rehash and then 1
	* additional rehash down the road. But this is an edge case that requires
	* getting unlucky on both boundaries. Most of the time, we do either 1
	* initial rehash or 1 down the road, because doubling the capacity generally
	* allows this map to absorb an equally-sized disjoint map.
	*/
	boolean resizeForJoin(int sizeOther) {
	return ensureSizeFor(Math.max(size, sizeOther));
	}

	private int getKeyIndex(Object k) {
	int h = keyHashCode(k);
	// Copied from Apache's AbstractHashedMap; prevents power-of-two collisions.
	h += ~(h << 9);
	h ^= (h >>> 14);
	h += (h << 4);
	h ^= (h >>> 10);
	// Power of two trick.
	return h & (keys.length - 1);
	}

	private void initTable(int capacity) {
	keys = new Object[capacity];
	values = new Object[capacity];
	}

	/**
	* Tricky, we left a hole in the map, which we have to fill. The only way to
	* do this is to search forwards through the map shuffling back values that
	* match this index until we hit a null.
	*/
	private void plugHole(int hole) {
	int index = hole + 1;
	if (index == keys.length) {
	index = 0;
	}
	while (keys[index] != null) {
	int targetIndex = getKeyIndex(unmaskNullKey(keys[index]));
	if (hole < index) {
	/*
	* "Normal" case, the index is past the hole and the "bad range" is from
	* hole (exclusive) to index (inclusive).
	*/
	if (!(hole < targetIndex && targetIndex <= index)) {
	// Plug it!
	keys[hole] = keys[index];
	values[hole] = values[index];
	keys[index] = null;
	values[index] = null;
	hole = index;
	}
	} else {
	/*
	* "Wrapped" case, the index is before the hole (we've wrapped) and the
	* "good range" is from index (exclusive) to hole (inclusive).
	*/
	if (index < targetIndex && targetIndex <= hole) {
	// Plug it!
	keys[hole] = keys[index];
	values[hole] = values[index];
	keys[index] = null;
	values[index] = null;
	hole = index;
	}
	}
	if (++index == keys.length) {
	index = 0;
	}
	}
	}

	private void readObject(ObjectInputStream in) throws IOException,
	ClassNotFoundException {
	in.defaultReadObject();
	doReadObject(in);
	}

	private void writeObject(ObjectOutputStream out) throws IOException {
	out.defaultWriteObject();
	doWriteObject(out);
	}
	}