/*
 *  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 org.apache.commons.collections.map;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractCollection;
import java.util.AbstractMap;
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;

import org.apache.commons.collections.IterableMap;
import org.apache.commons.collections.KeyValue;
import org.apache.commons.collections.MapIterator;
import org.apache.commons.collections.iterators.EmptyIterator;
import org.apache.commons.collections.iterators.EmptyMapIterator;

An abstract implementation of a hash-based map which provides numerous points for
subclasses to override.

This class implements all the features necessary for a subclass hash-based map.
Key-value entries are stored in instances of the HashEntry class,
which can be overridden and replaced. The iterators can similarly be replaced,
without the need to replace the KeySet, EntrySet and Values view classes.

Overridable methods are provided to change the default hashing behaviour, and
to change how entries are added to and removed from the map. Hopefully, all you
need for unusual subclasses is here.

NOTE: From Commons Collections 3.1 this class extends AbstractMap.
This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
This extends clause will be removed in v4.0.
Author:
java util HashMap, Stephen Colebourne, Christian Siefkes
Since:
Commons Collections 3.0
Version:
$Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $/**
 * An abstract implementation of a hash-based map which provides numerous points for
 * subclasses to override.
 * <p>
 * This class implements all the features necessary for a subclass hash-based map.
 * Key-value entries are stored in instances of the <code>HashEntry</code> class,
 * which can be overridden and replaced. The iterators can similarly be replaced,
 * without the need to replace the KeySet, EntrySet and Values view classes.
 * <p>
 * Overridable methods are provided to change the default hashing behaviour, and
 * to change how entries are added to and removed from the map. Hopefully, all you
 * need for unusual subclasses is here.
 * <p>
 * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
 * This extends clause will be removed in v4.0.
 * 
 * @since Commons Collections 3.0
 * @version $Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
 *
 * @author java util HashMap
 * @author Stephen Colebourne
 * @author Christian Siefkes
 */
public class AbstractHashedMap extends AbstractMap implements IterableMap {
    
    protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
    protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
    protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
    protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
    protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
    protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
    
    
The default capacity to use /** The default capacity to use */
    protected static final int DEFAULT_CAPACITY = 16;
    
The default threshold to use /** The default threshold to use */
    protected static final int DEFAULT_THRESHOLD = 12;
    
The default load factor to use /** The default load factor to use */
    protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
The maximum capacity allowed /** The maximum capacity allowed */
    protected static final int MAXIMUM_CAPACITY = 1 << 30;
    
An object for masking null /** An object for masking null */
    protected static final Object NULL = new Object();
    
    
Load factor, normally 0.75 /** Load factor, normally 0.75 */
    protected transient float loadFactor;
    
The size of the map /** The size of the map */
    protected transient int size;
    
Map entries /** Map entries */
    protected transient HashEntry[] data;
    
Size at which to rehash /** Size at which to rehash */
    protected transient int threshold;
    
Modification count for iterators /** Modification count for iterators */
    protected transient int modCount;
    
Entry set /** Entry set */
    protected transient EntrySet entrySet;
    
Key set /** Key set */
    protected transient KeySet keySet;
    
Values /** Values */
    protected transient Values values;

    
Constructor only used in deserialization, do not use otherwise.
/**
     * Constructor only used in deserialization, do not use otherwise.
     */
    protected AbstractHashedMap() {
        super();
    }

    
Constructor which performs no validation on the passed in parameters.
Params:
initialCapacity –  the initial capacity, must be a power of two
loadFactor –  the load factor, must be > 0.0f and generally < 1.0f
threshold –  the threshold, must be sensible/**
     * Constructor which performs no validation on the passed in parameters.
     * 
     * @param initialCapacity  the initial capacity, must be a power of two
     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
     * @param threshold  the threshold, must be sensible
     */
    protected AbstractHashedMap(int initialCapacity, float loadFactor, int threshold) {
        super();
        this.loadFactor = loadFactor;
        this.data = new HashEntry[initialCapacity];
        this.threshold = threshold;
        init();
    }

    
Constructs a new, empty map with the specified initial capacity and
default load factor. 
Params:
initialCapacity –  the initial capacity
Throws:
IllegalArgumentException – if the initial capacity is less than one/**
     * Constructs a new, empty map with the specified initial capacity and
     * default load factor. 
     *
     * @param initialCapacity  the initial capacity
     * @throws IllegalArgumentException if the initial capacity is less than one
     */
    protected AbstractHashedMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    
Constructs a new, empty map with the specified initial capacity and
load factor. 
Params:
initialCapacity –  the initial capacity
loadFactor –  the load factor
Throws:
IllegalArgumentException – if the initial capacity is less than one
IllegalArgumentException – if the load factor is less than or equal to zero/**
     * Constructs a new, empty map with the specified initial capacity and
     * load factor. 
     *
     * @param initialCapacity  the initial capacity
     * @param loadFactor  the load factor
     * @throws IllegalArgumentException if the initial capacity is less than one
     * @throws IllegalArgumentException if the load factor is less than or equal to zero
     */
    protected AbstractHashedMap(int initialCapacity, float loadFactor) {
        super();
        if (initialCapacity < 1) {
            throw new IllegalArgumentException("Initial capacity must be greater than 0");
        }
        if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Load factor must be greater than 0");
        }
        this.loadFactor = loadFactor;
        initialCapacity = calculateNewCapacity(initialCapacity);
        this.threshold = calculateThreshold(initialCapacity, loadFactor);
        this.data = new HashEntry[initialCapacity];
        init();
    }

    
Constructor copying elements from another map.
Params:
map –  the map to copy
Throws:
NullPointerException – if the map is null/**
     * Constructor copying elements from another map.
     *
     * @param map  the map to copy
     * @throws NullPointerException if the map is null
     */
    protected AbstractHashedMap(Map map) {
        this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAll(map);
    }

    
Initialise subclasses during construction, cloning or deserialization.
/**
     * Initialise subclasses during construction, cloning or deserialization.
     */
    protected void init() {
    }

    //-----------------------------------------------------------------------
    
Gets the value mapped to the key specified.
Params:
key –  the key
Returns:
the mapped value, null if no match/**
     * Gets the value mapped to the key specified.
     * 
     * @param key  the key
     * @return the mapped value, null if no match
     */
    public Object get(Object key) {
        key = convertKey(key);
        int hashCode = hash(key);
        HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return entry.getValue();
            }
            entry = entry.next;
        }
        return null;
    }

    
Gets the size of the map.
Returns:
the size/**
     * Gets the size of the map.
     * 
     * @return the size
     */
    public int size() {
        return size;
    }

    
Checks whether the map is currently empty.
Returns:
true if the map is currently size zero/**
     * Checks whether the map is currently empty.
     * 
     * @return true if the map is currently size zero
     */
    public boolean isEmpty() {
        return (size == 0);
    }

    //-----------------------------------------------------------------------
    
Checks whether the map contains the specified key.
Params:
key –  the key to search for
Returns:
true if the map contains the key/**
     * Checks whether the map contains the specified key.
     * 
     * @param key  the key to search for
     * @return true if the map contains the key
     */
    public boolean containsKey(Object key) {
        key = convertKey(key);
        int hashCode = hash(key);
        HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return true;
            }
            entry = entry.next;
        }
        return false;
    }

    
Checks whether the map contains the specified value.
Params:
value –  the value to search for
Returns:
true if the map contains the value/**
     * Checks whether the map contains the specified value.
     * 
     * @param value  the value to search for
     * @return true if the map contains the value
     */
    public boolean containsValue(Object value) {
        if (value == null) {
            for (int i = 0, isize = data.length; i < isize; i++) {
                HashEntry entry = data[i];
                while (entry != null) {
                    if (entry.getValue() == null) {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        } else {
            for (int i = 0, isize = data.length; i < isize; i++) {
                HashEntry entry = data[i];
                while (entry != null) {
                    if (isEqualValue(value, entry.getValue())) {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        }
        return false;
    }

    //-----------------------------------------------------------------------
    
Puts a key-value mapping into this map.
Params:
key –  the key to add
value –  the value to add
Returns:
the value previously mapped to this key, null if none/**
     * Puts a key-value mapping into this map.
     * 
     * @param key  the key to add
     * @param value  the value to add
     * @return the value previously mapped to this key, null if none
     */
    public Object put(Object key, Object value) {
        key = convertKey(key);
        int hashCode = hash(key);
        int index = hashIndex(hashCode, data.length);
        HashEntry entry = data[index];
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                Object oldValue = entry.getValue();
                updateEntry(entry, value);
                return oldValue;
            }
            entry = entry.next;
        }
        
        addMapping(index, hashCode, key, value);
        return null;
    }

    
Puts all the values from the specified map into this map.
 This implementation iterates around the specified map and uses put(Object, Object). 
Params:
map –  the map to add
Throws:
NullPointerException – if the map is null/**
     * Puts all the values from the specified map into this map.
     * <p>
     * This implementation iterates around the specified map and
     * uses {@link #put(Object, Object)}.
     * 
     * @param map  the map to add
     * @throws NullPointerException if the map is null
     */
    public void putAll(Map map) {
        int mapSize = map.size();
        if (mapSize == 0) {
            return;
        }
        int newSize = (int) ((size + mapSize) / loadFactor + 1);
        ensureCapacity(calculateNewCapacity(newSize));
        for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry) it.next();
            put(entry.getKey(), entry.getValue());
        }
    }

    
Removes the specified mapping from this map.
Params:
key –  the mapping to remove
Returns:
the value mapped to the removed key, null if key not in map/**
     * Removes the specified mapping from this map.
     * 
     * @param key  the mapping to remove
     * @return the value mapped to the removed key, null if key not in map
     */
    public Object remove(Object key) {
        key = convertKey(key);
        int hashCode = hash(key);
        int index = hashIndex(hashCode, data.length);
        HashEntry entry = data[index];
        HashEntry previous = null;
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                Object oldValue = entry.getValue();
                removeMapping(entry, index, previous);
                return oldValue;
            }
            previous = entry;
            entry = entry.next;
        }
        return null;
    }

    
Clears the map, resetting the size to zero and nullifying references
to avoid garbage collection issues.
/**
     * Clears the map, resetting the size to zero and nullifying references
     * to avoid garbage collection issues.
     */
    public void clear() {
        modCount++;
        HashEntry[] data = this.data;
        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = null;
        }
        size = 0;
    }

    //-----------------------------------------------------------------------
    
Converts input keys to another object for storage in the map.
This implementation masks nulls.
Subclasses can override this to perform alternate key conversions.

The reverse conversion can be changed, if required, by overriding the
getKey() method in the hash entry.
Params:
key –  the key convert
Returns:
the converted key/**
     * Converts input keys to another object for storage in the map.
     * This implementation masks nulls.
     * Subclasses can override this to perform alternate key conversions.
     * <p>
     * The reverse conversion can be changed, if required, by overriding the
     * getKey() method in the hash entry.
     * 
     * @param key  the key convert
     * @return the converted key
     */
    protected Object convertKey(Object key) {
        return (key == null ? NULL : key);
    }
    
    
Gets the hash code for the key specified.
This implementation uses the additional hashing routine from JDK1.4.
Subclasses can override this to return alternate hash codes.
Params:
key –  the key to get a hash code for
Returns:
the hash code/**
     * Gets the hash code for the key specified.
     * This implementation uses the additional hashing routine from JDK1.4.
     * Subclasses can override this to return alternate hash codes.
     * 
     * @param key  the key to get a hash code for
     * @return the hash code
     */
    protected int hash(Object key) {
        // same as JDK 1.4
        int h = key.hashCode();
        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }
    
    
Compares two keys, in internal converted form, to see if they are equal.
This implementation uses the equals method and assumes neither key is null.
Subclasses can override this to match differently.
Params:
key1 –  the first key to compare passed in from outside
key2 –  the second key extracted from the entry via entry.key
Returns:
true if equal/**
     * Compares two keys, in internal converted form, to see if they are equal.
     * This implementation uses the equals method and assumes neither key is null.
     * Subclasses can override this to match differently.
     * 
     * @param key1  the first key to compare passed in from outside
     * @param key2  the second key extracted from the entry via <code>entry.key</code>
     * @return true if equal
     */
    protected boolean isEqualKey(Object key1, Object key2) {
        return (key1 == key2 || key1.equals(key2));
    }
    
    
Compares two values, in external form, to see if they are equal.
This implementation uses the equals method and assumes neither value is null.
Subclasses can override this to match differently.
Params:
value1 –  the first value to compare passed in from outside
value2 –  the second value extracted from the entry via getValue()
Returns:
true if equal/**
     * Compares two values, in external form, to see if they are equal.
     * This implementation uses the equals method and assumes neither value is null.
     * Subclasses can override this to match differently.
     * 
     * @param value1  the first value to compare passed in from outside
     * @param value2  the second value extracted from the entry via <code>getValue()</code>
     * @return true if equal
     */
    protected boolean isEqualValue(Object value1, Object value2) {
        return (value1 == value2 || value1.equals(value2));
    }
    
    
Gets the index into the data storage for the hashCode specified.
This implementation uses the least significant bits of the hashCode.
Subclasses can override this to return alternate bucketing.
Params:
hashCode –  the hash code to use
dataSize –  the size of the data to pick a bucket from
Returns:
the bucket index/**
     * Gets the index into the data storage for the hashCode specified.
     * This implementation uses the least significant bits of the hashCode.
     * Subclasses can override this to return alternate bucketing.
     * 
     * @param hashCode  the hash code to use
     * @param dataSize  the size of the data to pick a bucket from
     * @return the bucket index
     */
    protected int hashIndex(int hashCode, int dataSize) {
        return hashCode & (dataSize - 1);
    }
    
    //-----------------------------------------------------------------------
    
Gets the entry mapped to the key specified.

This method exists for subclasses that may need to perform a multi-step
process accessing the entry. The public methods in this class don't use this
method to gain a small performance boost.
Params:
key –  the key
Returns:
the entry, null if no match/**
     * Gets the entry mapped to the key specified.
     * <p>
     * This method exists for subclasses that may need to perform a multi-step
     * process accessing the entry. The public methods in this class don't use this
     * method to gain a small performance boost.
     * 
     * @param key  the key
     * @return the entry, null if no match
     */
    protected HashEntry getEntry(Object key) {
        key = convertKey(key);
        int hashCode = hash(key);
        HashEntry entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                return entry;
            }
            entry = entry.next;
        }
        return null;
    }

    //-----------------------------------------------------------------------
    
Updates an existing key-value mapping to change the value.

This implementation calls setValue() on the entry.
Subclasses could override to handle changes to the map.
Params:
entry –  the entry to update
newValue –  the new value to store/**
     * Updates an existing key-value mapping to change the value.
     * <p>
     * This implementation calls <code>setValue()</code> on the entry.
     * Subclasses could override to handle changes to the map.
     * 
     * @param entry  the entry to update
     * @param newValue  the new value to store
     */
    protected void updateEntry(HashEntry entry, Object newValue) {
        entry.setValue(newValue);
    }
    
    
Reuses an existing key-value mapping, storing completely new data.

This implementation sets all the data fields on the entry.
Subclasses could populate additional entry fields.
Params:
entry –  the entry to update, not null
hashIndex –  the index in the data array
hashCode –  the hash code of the key to add
key –  the key to add
value –  the value to add/**
     * Reuses an existing key-value mapping, storing completely new data.
     * <p>
     * This implementation sets all the data fields on the entry.
     * Subclasses could populate additional entry fields.
     * 
     * @param entry  the entry to update, not null
     * @param hashIndex  the index in the data array
     * @param hashCode  the hash code of the key to add
     * @param key  the key to add
     * @param value  the value to add
     */
    protected void reuseEntry(HashEntry entry, int hashIndex, int hashCode, Object key, Object value) {
        entry.next = data[hashIndex];
        entry.hashCode = hashCode;
        entry.key = key;
        entry.value = value;
    }
    
    //-----------------------------------------------------------------------
    
Adds a new key-value mapping into this map.

This implementation calls createEntry(), addEntry()
and checkCapacity().
It also handles changes to modCount and size.
Subclasses could override to fully control adds to the map.
Params:
hashIndex –  the index into the data array to store at
hashCode –  the hash code of the key to add
key –  the key to add
value –  the value to add/**
     * Adds a new key-value mapping into this map.
     * <p>
     * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
     * and <code>checkCapacity()</code>.
     * It also handles changes to <code>modCount</code> and <code>size</code>.
     * Subclasses could override to fully control adds to the map.
     * 
     * @param hashIndex  the index into the data array to store at
     * @param hashCode  the hash code of the key to add
     * @param key  the key to add
     * @param value  the value to add
     */
    protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
        modCount++;
        HashEntry entry = createEntry(data[hashIndex], hashCode, key, value);
        addEntry(entry, hashIndex);
        size++;
        checkCapacity();
    }
    
    
Creates an entry to store the key-value data.

This implementation creates a new HashEntry instance.
Subclasses can override this to return a different storage class,
or implement caching.
Params:
next –  the next entry in sequence
hashCode –  the hash code to use
key –  the key to store
value –  the value to store
Returns:
the newly created entry/**
     * Creates an entry to store the key-value data.
     * <p>
     * This implementation creates a new HashEntry instance.
     * Subclasses can override this to return a different storage class,
     * or implement caching.
     * 
     * @param next  the next entry in sequence
     * @param hashCode  the hash code to use
     * @param key  the key to store
     * @param value  the value to store
     * @return the newly created entry
     */
    protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value) {
        return new HashEntry(next, hashCode, key, value);
    }
    
    
Adds an entry into this map.

This implementation adds the entry to the data storage table.
Subclasses could override to handle changes to the map.
Params:
entry –  the entry to add
hashIndex –  the index into the data array to store at/**
     * Adds an entry into this map.
     * <p>
     * This implementation adds the entry to the data storage table.
     * Subclasses could override to handle changes to the map.
     *
     * @param entry  the entry to add
     * @param hashIndex  the index into the data array to store at
     */
    protected void addEntry(HashEntry entry, int hashIndex) {
        data[hashIndex] = entry;
    }
    
    //-----------------------------------------------------------------------
    
Removes a mapping from the map.

This implementation calls removeEntry() and destroyEntry().
It also handles changes to modCount and size.
Subclasses could override to fully control removals from the map.
Params:
entry –  the entry to remove
hashIndex –  the index into the data structure
previous –  the previous entry in the chain/**
     * Removes a mapping from the map.
     * <p>
     * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
     * It also handles changes to <code>modCount</code> and <code>size</code>.
     * Subclasses could override to fully control removals from the map.
     * 
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    protected void removeMapping(HashEntry entry, int hashIndex, HashEntry previous) {
        modCount++;
        removeEntry(entry, hashIndex, previous);
        size--;
        destroyEntry(entry);
    }
    
    
Removes an entry from the chain stored in a particular index.

This implementation removes the entry from the data storage table.
The size is not updated.
Subclasses could override to handle changes to the map.
Params:
entry –  the entry to remove
hashIndex –  the index into the data structure
previous –  the previous entry in the chain/**
     * Removes an entry from the chain stored in a particular index.
     * <p>
     * This implementation removes the entry from the data storage table.
     * The size is not updated.
     * Subclasses could override to handle changes to the map.
     * 
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    protected void removeEntry(HashEntry entry, int hashIndex, HashEntry previous) {
        if (previous == null) {
            data[hashIndex] = entry.next;
        } else {
            previous.next = entry.next;
        }
    }
    
    
Kills an entry ready for the garbage collector.

This implementation prepares the HashEntry for garbage collection.
Subclasses can override this to implement caching (override clear as well).
Params:
entry –  the entry to destroy/**
     * Kills an entry ready for the garbage collector.
     * <p>
     * This implementation prepares the HashEntry for garbage collection.
     * Subclasses can override this to implement caching (override clear as well).
     * 
     * @param entry  the entry to destroy
     */
    protected void destroyEntry(HashEntry entry) {
        entry.next = null;
        entry.key = null;
        entry.value = null;
    }
    
    //-----------------------------------------------------------------------
    
Checks the capacity of the map and enlarges it if necessary.

This implementation uses the threshold to check if the map needs enlarging
/**
     * Checks the capacity of the map and enlarges it if necessary.
     * <p>
     * This implementation uses the threshold to check if the map needs enlarging
     */
    protected void checkCapacity() {
        if (size >= threshold) {
            int newCapacity = data.length * 2;
            if (newCapacity <= MAXIMUM_CAPACITY) {
                ensureCapacity(newCapacity);
            }
        }
    }
    
    
Changes the size of the data structure to the capacity proposed.
Params:
newCapacity –  the new capacity of the array (a power of two, less or equal to max)/**
     * Changes the size of the data structure to the capacity proposed.
     * 
     * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
     */
    protected void ensureCapacity(int newCapacity) {
        int oldCapacity = data.length;
        if (newCapacity <= oldCapacity) {
            return;
        }
        if (size == 0) {
            threshold = calculateThreshold(newCapacity, loadFactor);
            data = new HashEntry[newCapacity];
        } else {
            HashEntry oldEntries[] = data;
            HashEntry newEntries[] = new HashEntry[newCapacity];

            modCount++;
            for (int i = oldCapacity - 1; i >= 0; i--) {
                HashEntry entry = oldEntries[i];
                if (entry != null) {
                    oldEntries[i] = null;  // gc
                    do {
                        HashEntry next = entry.next;
                        int index = hashIndex(entry.hashCode, newCapacity);  
                        entry.next = newEntries[index];
                        newEntries[index] = entry;
                        entry = next;
                    } while (entry != null);
                }
            }
            threshold = calculateThreshold(newCapacity, loadFactor);
            data = newEntries;
        }
    }

    
Calculates the new capacity of the map.
This implementation normalizes the capacity to a power of two.
Params:
proposedCapacity –  the proposed capacity
Returns:
the normalized new capacity/**
     * Calculates the new capacity of the map.
     * This implementation normalizes the capacity to a power of two.
     * 
     * @param proposedCapacity  the proposed capacity
     * @return the normalized new capacity
     */
    protected int calculateNewCapacity(int proposedCapacity) {
        int newCapacity = 1;
        if (proposedCapacity > MAXIMUM_CAPACITY) {
            newCapacity = MAXIMUM_CAPACITY;
        } else {
            while (newCapacity < proposedCapacity) {
                newCapacity <<= 1;  // multiply by two
            }
            if (newCapacity > MAXIMUM_CAPACITY) {
                newCapacity = MAXIMUM_CAPACITY;
            }
        }
        return newCapacity;
    }
    
    
Calculates the new threshold of the map, where it will be resized.
This implementation uses the load factor.
Params:
newCapacity –  the new capacity
factor –  the load factor
Returns:
the new resize threshold/**
     * Calculates the new threshold of the map, where it will be resized.
     * This implementation uses the load factor.
     * 
     * @param newCapacity  the new capacity
     * @param factor  the load factor
     * @return the new resize threshold
     */
    protected int calculateThreshold(int newCapacity, float factor) {
        return (int) (newCapacity * factor);
    }
    
    //-----------------------------------------------------------------------
    
Gets the next field from a HashEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the next field of the entry
Since:
Commons Collections 3.1/**
     * Gets the <code>next</code> field from a <code>HashEntry</code>.
     * Used in subclasses that have no visibility of the field.
     * 
     * @param entry  the entry to query, must not be null
     * @return the <code>next</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since Commons Collections 3.1
     */
    protected HashEntry entryNext(HashEntry entry) {
        return entry.next;
    }
    
    
Gets the hashCode field from a HashEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the hashCode field of the entry
Since:
Commons Collections 3.1/**
     * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
     * Used in subclasses that have no visibility of the field.
     * 
     * @param entry  the entry to query, must not be null
     * @return the <code>hashCode</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since Commons Collections 3.1
     */
    protected int entryHashCode(HashEntry entry) {
        return entry.hashCode;
    }
    
    
Gets the key field from a HashEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the key field of the entry
Since:
Commons Collections 3.1/**
     * Gets the <code>key</code> field from a <code>HashEntry</code>.
     * Used in subclasses that have no visibility of the field.
     * 
     * @param entry  the entry to query, must not be null
     * @return the <code>key</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since Commons Collections 3.1
     */
    protected Object entryKey(HashEntry entry) {
        return entry.key;
    }
    
    
Gets the value field from a HashEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the value field of the entry
Since:
Commons Collections 3.1/**
     * Gets the <code>value</code> field from a <code>HashEntry</code>.
     * Used in subclasses that have no visibility of the field.
     * 
     * @param entry  the entry to query, must not be null
     * @return the <code>value</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since Commons Collections 3.1
     */
    protected Object entryValue(HashEntry entry) {
        return entry.value;
    }
    
    //-----------------------------------------------------------------------
    
Gets an iterator over the map.
Changes made to the iterator affect this map.

A MapIterator returns the keys in the map. It also provides convenient
methods to get the key and value, and set the value.
It avoids the need to create an entrySet/keySet/values object.
It also avoids creating the Map.Entry object.
Returns:
the map iterator/**
     * Gets an iterator over the map.
     * Changes made to the iterator affect this map.
     * <p>
     * A MapIterator returns the keys in the map. It also provides convenient
     * methods to get the key and value, and set the value.
     * It avoids the need to create an entrySet/keySet/values object.
     * It also avoids creating the Map.Entry object.
     * 
     * @return the map iterator
     */
    public MapIterator mapIterator() {
        if (size == 0) {
            return EmptyMapIterator.INSTANCE;
        }
        return new HashMapIterator(this);
    }

    
MapIterator implementation.
/**
     * MapIterator implementation.
     */
    protected static class HashMapIterator extends HashIterator implements MapIterator {
        
        protected HashMapIterator(AbstractHashedMap parent) {
            super(parent);
        }

        public Object next() {
            return super.nextEntry().getKey();
        }

        public Object getKey() {
            HashEntry current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
            }
            return current.getKey();
        }

        public Object getValue() {
            HashEntry current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
            }
            return current.getValue();
        }

        public Object setValue(Object value) {
            HashEntry current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
            }
            return current.setValue(value);
        }
    }
    
    //-----------------------------------------------------------------------    
    
Gets the entrySet view of the map. Changes made to the view affect this map. To simply iterate through the entries, use mapIterator(). 
Returns:
the entrySet view/**
     * Gets the entrySet view of the map.
     * Changes made to the view affect this map.
     * To simply iterate through the entries, use {@link #mapIterator()}.
     * 
     * @return the entrySet view
     */
    public Set entrySet() {
        if (entrySet == null) {
            entrySet = new EntrySet(this);
        }
        return entrySet;
    }
    
    
Creates an entry set iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the entrySet iterator/**
     * Creates an entry set iterator.
     * Subclasses can override this to return iterators with different properties.
     * 
     * @return the entrySet iterator
     */
    protected Iterator createEntrySetIterator() {
        if (size() == 0) {
            return EmptyIterator.INSTANCE;
        }
        return new EntrySetIterator(this);
    }

    
EntrySet implementation.
/**
     * EntrySet implementation.
     */
    protected static class EntrySet extends AbstractSet {
        
The parent map /** The parent map */
        protected final AbstractHashedMap parent;
        
        protected EntrySet(AbstractHashedMap parent) {
            super();
            this.parent = parent;
        }

        public int size() {
            return parent.size();
        }
        
        public void clear() {
            parent.clear();
        }
        
        public boolean contains(Object entry) {
            if (entry instanceof Map.Entry) {
                Map.Entry e = (Map.Entry) entry;
                Entry match = parent.getEntry(e.getKey());
                return (match != null && match.equals(e));
            }
            return false;
        }
        
        public boolean remove(Object obj) {
            if (obj instanceof Map.Entry == false) {
                return false;
            }
            if (contains(obj) == false) {
                return false;
            }
            Map.Entry entry = (Map.Entry) obj;
            Object key = entry.getKey();
            parent.remove(key);
            return true;
        }

        public Iterator iterator() {
            return parent.createEntrySetIterator();
        }
    }

    
EntrySet iterator.
/**
     * EntrySet iterator.
     */
    protected static class EntrySetIterator extends HashIterator {
        
        protected EntrySetIterator(AbstractHashedMap parent) {
            super(parent);
        }

        public Object next() {
            return super.nextEntry();
        }
    }

    //-----------------------------------------------------------------------    
    
Gets the keySet view of the map. Changes made to the view affect this map. To simply iterate through the keys, use mapIterator(). 
Returns:
the keySet view/**
     * Gets the keySet view of the map.
     * Changes made to the view affect this map.
     * To simply iterate through the keys, use {@link #mapIterator()}.
     * 
     * @return the keySet view
     */
    public Set keySet() {
        if (keySet == null) {
            keySet = new KeySet(this);
        }
        return keySet;
    }

    
Creates a key set iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the keySet iterator/**
     * Creates a key set iterator.
     * Subclasses can override this to return iterators with different properties.
     * 
     * @return the keySet iterator
     */
    protected Iterator createKeySetIterator() {
        if (size() == 0) {
            return EmptyIterator.INSTANCE;
        }
        return new KeySetIterator(this);
    }

    
KeySet implementation.
/**
     * KeySet implementation.
     */
    protected static class KeySet extends AbstractSet {
        
The parent map /** The parent map */
        protected final AbstractHashedMap parent;
        
        protected KeySet(AbstractHashedMap parent) {
            super();
            this.parent = parent;
        }

        public int size() {
            return parent.size();
        }
        
        public void clear() {
            parent.clear();
        }
        
        public boolean contains(Object key) {
            return parent.containsKey(key);
        }
        
        public boolean remove(Object key) {
            boolean result = parent.containsKey(key);
            parent.remove(key);
            return result;
        }

        public Iterator iterator() {
            return parent.createKeySetIterator();
        }
    }

    
KeySet iterator.
/**
     * KeySet iterator.
     */
    protected static class KeySetIterator extends EntrySetIterator {
        
        protected KeySetIterator(AbstractHashedMap parent) {
            super(parent);
        }

        public Object next() {
            return super.nextEntry().getKey();
        }
    }
    
    //-----------------------------------------------------------------------    
    
Gets the values view of the map. Changes made to the view affect this map. To simply iterate through the values, use mapIterator(). 
Returns:
the values view/**
     * Gets the values view of the map.
     * Changes made to the view affect this map.
     * To simply iterate through the values, use {@link #mapIterator()}.
     * 
     * @return the values view
     */
    public Collection values() {
        if (values == null) {
            values = new Values(this);
        }
        return values;
    }

    
Creates a values iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the values iterator/**
     * Creates a values iterator.
     * Subclasses can override this to return iterators with different properties.
     * 
     * @return the values iterator
     */
    protected Iterator createValuesIterator() {
        if (size() == 0) {
            return EmptyIterator.INSTANCE;
        }
        return new ValuesIterator(this);
    }

    
Values implementation.
/**
     * Values implementation.
     */
    protected static class Values extends AbstractCollection {
        
The parent map /** The parent map */
        protected final AbstractHashedMap parent;
        
        protected Values(AbstractHashedMap parent) {
            super();
            this.parent = parent;
        }

        public int size() {
            return parent.size();
        }
        
        public void clear() {
            parent.clear();
        }
        
        public boolean contains(Object value) {
            return parent.containsValue(value);
        }
        
        public Iterator iterator() {
            return parent.createValuesIterator();
        }
    }

    
Values iterator.
/**
     * Values iterator.
     */
    protected static class ValuesIterator extends HashIterator {
        
        protected ValuesIterator(AbstractHashedMap parent) {
            super(parent);
        }

        public Object next() {
            return super.nextEntry().getValue();
        }
    }
    
    //-----------------------------------------------------------------------
    
HashEntry used to store the data.

If you subclass AbstractHashedMap but not HashEntry
then you will not be able to access the protected fields.
The entryXxx() methods on AbstractHashedMap exist
to provide the necessary access.
/**
     * HashEntry used to store the data.
     * <p>
     * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
     * then you will not be able to access the protected fields.
     * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
     * to provide the necessary access.
     */
    protected static class HashEntry implements Map.Entry, KeyValue {
        
The next entry in the hash chain /** The next entry in the hash chain */
        protected HashEntry next;
        
The hash code of the key /** The hash code of the key */
        protected int hashCode;
        
The key /** The key */
        protected Object key;
        
The value /** The value */
        protected Object value;
        
        protected HashEntry(HashEntry next, int hashCode, Object key, Object value) {
            super();
            this.next = next;
            this.hashCode = hashCode;
            this.key = key;
            this.value = value;
        }
        
        public Object getKey() {
            return (key == NULL ? null : key);
        }
        
        public Object getValue() {
            return value;
        }
        
        public Object setValue(Object value) {
            Object old = this.value;
            this.value = value;
            return old;
        }
        
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (obj instanceof Map.Entry == false) {
                return false;
            }
            Map.Entry other = (Map.Entry) obj;
            return
                (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
                (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
        }
        
        public int hashCode() {
            return (getKey() == null ? 0 : getKey().hashCode()) ^
                   (getValue() == null ? 0 : getValue().hashCode()); 
        }
        
        public String toString() {
            return new StringBuffer().append(getKey()).append('=').append(getValue()).toString();
        }
    }
    
    
Base Iterator
/**
     * Base Iterator
     */
    protected static abstract class HashIterator implements Iterator {
        
        
The parent map /** The parent map */
        protected final AbstractHashedMap parent;
        
The current index into the array of buckets /** The current index into the array of buckets */
        protected int hashIndex;
        
The last returned entry /** The last returned entry */
        protected HashEntry last;
        
The next entry /** The next entry */
        protected HashEntry next;
        
The modification count expected /** The modification count expected */
        protected int expectedModCount;
        
        protected HashIterator(AbstractHashedMap parent) {
            super();
            this.parent = parent;
            HashEntry[] data = parent.data;
            int i = data.length;
            HashEntry next = null;
            while (i > 0 && next == null) {
                next = data[--i];
            }
            this.next = next;
            this.hashIndex = i;
            this.expectedModCount = parent.modCount;
        }

        public boolean hasNext() {
            return (next != null);
        }

        protected HashEntry nextEntry() { 
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            HashEntry newCurrent = next;
            if (newCurrent == null)  {
                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
            }
            HashEntry[] data = parent.data;
            int i = hashIndex;
            HashEntry n = newCurrent.next;
            while (n == null && i > 0) {
                n = data[--i];
            }
            next = n;
            hashIndex = i;
            last = newCurrent;
            return newCurrent;
        }

        protected HashEntry currentEntry() {
            return last;
        }
        
        public void remove() {
            if (last == null) {
                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
            }
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            parent.remove(last.getKey());
            last = null;
            expectedModCount = parent.modCount;
        }

        public String toString() {
            if (last != null) {
                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
            } else {
                return "Iterator[]";
            }
        }
    }
    
    //-----------------------------------------------------------------------
    
Writes the map data to the stream. This method must be overridden if a
subclass must be setup before put() is used.

Serialization is not one of the JDK's nicest topics. Normal serialization will
initialise the superclass before the subclass. Sometimes however, this isn't
what you want, as in this case the put() method on read can be
affected by subclass state.

The solution adopted here is to serialize the state data of this class in
this protected method. This method must be called by the
writeObject() of the first serializable subclass.

Subclasses may override if they have a specific field that must be present
on read before this implementation will work. Generally, the read determines
what must be serialized here, if anything.
Params:
out –  the output stream/**
     * Writes the map data to the stream. This method must be overridden if a
     * subclass must be setup before <code>put()</code> is used.
     * <p>
     * Serialization is not one of the JDK's nicest topics. Normal serialization will
     * initialise the superclass before the subclass. Sometimes however, this isn't
     * what you want, as in this case the <code>put()</code> method on read can be
     * affected by subclass state.
     * <p>
     * The solution adopted here is to serialize the state data of this class in
     * this protected method. This method must be called by the
     * <code>writeObject()</code> of the first serializable subclass.
     * <p>
     * Subclasses may override if they have a specific field that must be present
     * on read before this implementation will work. Generally, the read determines
     * what must be serialized here, if anything.
     * 
     * @param out  the output stream
     */
    protected void doWriteObject(ObjectOutputStream out) throws IOException {
        out.writeFloat(loadFactor);
        out.writeInt(data.length);
        out.writeInt(size);
        for (MapIterator it = mapIterator(); it.hasNext();) {
            out.writeObject(it.next());
            out.writeObject(it.getValue());
        }
    }

    
Reads the map data from the stream. This method must be overridden if a
subclass must be setup before put() is used.

Serialization is not one of the JDK's nicest topics. Normal serialization will
initialise the superclass before the subclass. Sometimes however, this isn't
what you want, as in this case the put() method on read can be
affected by subclass state.

The solution adopted here is to deserialize the state data of this class in
this protected method. This method must be called by the
readObject() of the first serializable subclass.

Subclasses may override if the subclass has a specific field that must be present
before put() or calculateThreshold() will work correctly.
Params:
in –  the input stream/**
     * Reads the map data from the stream. This method must be overridden if a
     * subclass must be setup before <code>put()</code> is used.
     * <p>
     * Serialization is not one of the JDK's nicest topics. Normal serialization will
     * initialise the superclass before the subclass. Sometimes however, this isn't
     * what you want, as in this case the <code>put()</code> method on read can be
     * affected by subclass state.
     * <p>
     * The solution adopted here is to deserialize the state data of this class in
     * this protected method. This method must be called by the
     * <code>readObject()</code> of the first serializable subclass.
     * <p>
     * Subclasses may override if the subclass has a specific field that must be present
     * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
     * 
     * @param in  the input stream
     */
    protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        loadFactor = in.readFloat();
        int capacity = in.readInt();
        int size = in.readInt();
        init();
        threshold = calculateThreshold(capacity, loadFactor);
        data = new HashEntry[capacity];
        for (int i = 0; i < size; i++) {
            Object key = in.readObject();
            Object value = in.readObject();
            put(key, value);
        }
    }
    
    //-----------------------------------------------------------------------
    
Clones the map without cloning the keys or values.

To implement clone(), a subclass must implement the
Cloneable interface and make this method public.
Returns:
a shallow clone/**
     * Clones the map without cloning the keys or values.
     * <p>
     * To implement <code>clone()</code>, a subclass must implement the
     * <code>Cloneable</code> interface and make this method public.
     *
     * @return a shallow clone
     */
    protected Object clone() {
        try {
            AbstractHashedMap cloned = (AbstractHashedMap) super.clone();
            cloned.data = new HashEntry[data.length];
            cloned.entrySet = null;
            cloned.keySet = null;
            cloned.values = null;
            cloned.modCount = 0;
            cloned.size = 0;
            cloned.init();
            cloned.putAll(this);
            return cloned;
            
        } catch (CloneNotSupportedException ex) {
            return null;  // should never happen
        }
    }
    
    
Compares this map with another.
Params:
obj –  the object to compare to
Returns:
true if equal/**
     * Compares this map with another.
     * 
     * @param obj  the object to compare to
     * @return true if equal
     */
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Map == false) {
            return false;
        }
        Map map = (Map) obj;
        if (map.size() != size()) {
            return false;
        }
        MapIterator it = mapIterator();
        try {
            while (it.hasNext()) {
                Object key = it.next();
                Object value = it.getValue();
                if (value == null) {
                    if (map.get(key) != null || map.containsKey(key) == false) {
                        return false;
                    }
                } else {
                    if (value.equals(map.get(key)) == false) {
                        return false;
                    }
                }
            }
        } catch (ClassCastException ignored)   {
            return false;
        } catch (NullPointerException ignored) {
            return false;
        }
        return true;
    }

    
Gets the standard Map hashCode.
Returns:
the hash code defined in the Map interface/**
     * Gets the standard Map hashCode.
     * 
     * @return the hash code defined in the Map interface
     */
    public int hashCode() {
        int total = 0;
        Iterator it = createEntrySetIterator();
        while (it.hasNext()) {
            total += it.next().hashCode();
        }
        return total;
    }

    
Gets the map as a String.
Returns:
a string version of the map/**
     * Gets the map as a String.
     * 
     * @return a string version of the map
     */
    public String toString() {
        if (size() == 0) {
            return "{}";
        }
        StringBuffer buf = new StringBuffer(32 * size());
        buf.append('{');

        MapIterator it = mapIterator();
        boolean hasNext = it.hasNext();
        while (hasNext) {
            Object key = it.next();
            Object value = it.getValue();
            buf.append(key == this ? "(this Map)" : key)
               .append('=')
               .append(value == this ? "(this Map)" : value);

            hasNext = it.hasNext();
            if (hasNext) {
                buf.append(',').append(' ');
            }
        }

        buf.append('}');
        return buf.toString();
    }
}