/*
 * 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.collections4.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.collections4.IterableMap;
import org.apache.commons.collections4.KeyValue;
import org.apache.commons.collections4.MapIterator;
import org.apache.commons.collections4.iterators.EmptyIterator;
import org.apache.commons.collections4.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 v5.0.
Type parameters:
<K> – the type of the keys in this map
<V> – the type of the values in this map
Since:
3.0/**
 * 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 v5.0.
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0
 */
public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {

    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 */
    transient float loadFactor;
    
The size of the map /** The size of the map */
    transient int size;
    
Map entries /** Map entries */
    transient HashEntry<K, V>[] data;
    
Size at which to rehash /** Size at which to rehash */
    transient int threshold;
    
Modification count for iterators /** Modification count for iterators */
    transient int modCount;
    
Entry set /** Entry set */
    transient EntrySet<K, V> entrySet;
    
Key set /** Key set */
    transient KeySet<K> keySet;
    
Values /** Values */
    transient Values<V> 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
     */
    @SuppressWarnings("unchecked")
    protected AbstractHashedMap(final int initialCapacity, final float loadFactor, final 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 negative/**
     * 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 negative
     */
    protected AbstractHashedMap(final 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 negative
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 negative
     * @throws IllegalArgumentException if the load factor is less than or equal to zero
     */
    @SuppressWarnings("unchecked")
    protected AbstractHashedMap(int initialCapacity, final float loadFactor) {
        super();
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Initial capacity must be a non negative number");
        }
        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(final Map<? extends K, ? extends V> 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
     */
    @Override
    public V get(Object key) {
        key = convertKey(key);
        final int hashCode = hash(key);
        HashEntry<K, V> 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
     */
    @Override
    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
     */
    @Override
    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
     */
    @Override
    public boolean containsKey(Object key) {
        key = convertKey(key);
        final int hashCode = hash(key);
        HashEntry<K, V> 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
     */
    @Override
    public boolean containsValue(final Object value) {
        if (value == null) {
            for (final HashEntry<K, V> element : data) {
                HashEntry<K, V> entry = element;
                while (entry != null) {
                    if (entry.getValue() == null) {
                        return true;
                    }
                    entry = entry.next;
                }
            }
        } else {
            for (final HashEntry<K, V> element : data) {
                HashEntry<K, V> entry = element;
                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
     */
    @Override
    public V put(final K key, final V value) {
        final Object convertedKey = convertKey(key);
        final int hashCode = hash(convertedKey);
        final int index = hashIndex(hashCode, data.length);
        HashEntry<K, V> entry = data[index];
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) {
                final V 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
     */
    @Override
    public void putAll(final Map<? extends K, ? extends V> map) {
        _putAll(map);
    }

    
Puts all the values from the specified map into this map.
 This implementation iterates around the specified map and uses put(Object, Object). 

It is private to allow the constructor to still call it
even when putAll is overriden.
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)}.
     * <p>
     * It is private to allow the constructor to still call it
     * even when putAll is overriden.
     *
     * @param map  the map to add
     * @throws NullPointerException if the map is null
     */
    private void _putAll(final Map<? extends K, ? extends V> map) {
        final int mapSize = map.size();
        if (mapSize == 0) {
            return;
        }
        final int newSize = (int) ((size + mapSize) / loadFactor + 1);
        ensureCapacity(calculateNewCapacity(newSize));
        for (final Map.Entry<? extends K, ? extends V> entry: map.entrySet()) {
            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
     */
    @Override
    public V remove(Object key) {
        key = convertKey(key);
        final int hashCode = hash(key);
        final int index = hashIndex(hashCode, data.length);
        HashEntry<K, V> entry = data[index];
        HashEntry<K, V> previous = null;
        while (entry != null) {
            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
                final V 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.
     */
    @Override
    public void clear() {
        modCount++;
        final HashEntry<K, V>[] 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(final 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(final 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(final Object key1, final 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(final Object value1, final 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(final int hashCode, final 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<K, V> getEntry(Object key) {
        key = convertKey(key);
        final int hashCode = hash(key);
        HashEntry<K, V> 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(final HashEntry<K, V> entry, final V 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(final HashEntry<K, V> entry, final int hashIndex, final int hashCode,
                              final K key, final V 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(final int hashIndex, final int hashCode, final K key, final V value) {
        modCount++;
        final HashEntry<K, V> 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<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
        return new HashEntry<>(next, hashCode, convertKey(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(final HashEntry<K, V> entry, final 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(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> 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(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> 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(final HashEntry<K, V> 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) {
            final 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)
     */
    @SuppressWarnings("unchecked")
    protected void ensureCapacity(final int newCapacity) {
        final int oldCapacity = data.length;
        if (newCapacity <= oldCapacity) {
            return;
        }
        if (size == 0) {
            threshold = calculateThreshold(newCapacity, loadFactor);
            data = new HashEntry[newCapacity];
        } else {
            final HashEntry<K, V> oldEntries[] = data;
            final HashEntry<K, V> newEntries[] = new HashEntry[newCapacity];

            modCount++;
            for (int i = oldCapacity - 1; i >= 0; i--) {
                HashEntry<K, V> entry = oldEntries[i];
                if (entry != null) {
                    oldEntries[i] = null;  // gc
                    do {
                        final HashEntry<K, V> next = entry.next;
                        final 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(final 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(final int newCapacity, final 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:
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 3.1
     */
    protected HashEntry<K, V> entryNext(final HashEntry<K, V> 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:
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 3.1
     */
    protected int entryHashCode(final HashEntry<K, V> 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:
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 3.1
     */
    protected K entryKey(final HashEntry<K, V> entry) {
        return entry.getKey();
    }

    
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:
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 3.1
     */
    protected V entryValue(final HashEntry<K, V> entry) {
        return entry.getValue();
    }

    //-----------------------------------------------------------------------
    
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
     */
    @Override
    public MapIterator<K, V> mapIterator() {
        if (size == 0) {
            return EmptyMapIterator.<K, V>emptyMapIterator();
        }
        return new HashMapIterator<>(this);
    }

    
MapIterator implementation.
/**
     * MapIterator implementation.
     */
    protected static class HashMapIterator<K, V> extends HashIterator<K, V> implements MapIterator<K, V> {

        protected HashMapIterator(final AbstractHashedMap<K, V> parent) {
            super(parent);
        }

        @Override
        public K next() {
            return super.nextEntry().getKey();
        }

        @Override
        public K getKey() {
            final HashEntry<K, V> current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
            }
            return current.getKey();
        }

        @Override
        public V getValue() {
            final HashEntry<K, V> current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
            }
            return current.getValue();
        }

        @Override
        public V setValue(final V value) {
            final HashEntry<K, V> 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
     */
    @Override
    public Set<Map.Entry<K, V>> 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<Map.Entry<K, V>> createEntrySetIterator() {
        if (size() == 0) {
            return EmptyIterator.<Map.Entry<K, V>>emptyIterator();
        }
        return new EntrySetIterator<>(this);
    }

    
EntrySet implementation.
/**
     * EntrySet implementation.
     */
    protected static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
        
The parent map /** The parent map */
        private final AbstractHashedMap<K, V> parent;

        protected EntrySet(final AbstractHashedMap<K, V> parent) {
            super();
            this.parent = parent;
        }

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

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

        @Override
        public boolean contains(final Object entry) {
            if (entry instanceof Map.Entry) {
                final Map.Entry<?, ?> e = (Map.Entry<?, ?>) entry;
                final Entry<K, V> match = parent.getEntry(e.getKey());
                return match != null && match.equals(e);
            }
            return false;
        }

        @Override
        public boolean remove(final Object obj) {
            if (obj instanceof Map.Entry == false) {
                return false;
            }
            if (contains(obj) == false) {
                return false;
            }
            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
            parent.remove(entry.getKey());
            return true;
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return parent.createEntrySetIterator();
        }
    }

    
EntrySet iterator.
/**
     * EntrySet iterator.
     */
    protected static class EntrySetIterator<K, V> extends HashIterator<K, V> implements Iterator<Map.Entry<K, V>> {

        protected EntrySetIterator(final AbstractHashedMap<K, V> parent) {
            super(parent);
        }

        @Override
        public Map.Entry<K, V> 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
     */
    @Override
    public Set<K> 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<K> createKeySetIterator() {
        if (size() == 0) {
            return EmptyIterator.<K>emptyIterator();
        }
        return new KeySetIterator<>(this);
    }

    
KeySet implementation.
/**
     * KeySet implementation.
     */
    protected static class KeySet<K> extends AbstractSet<K> {
        
The parent map /** The parent map */
        private final AbstractHashedMap<K, ?> parent;

        protected KeySet(final AbstractHashedMap<K, ?> parent) {
            super();
            this.parent = parent;
        }

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

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

        @Override
        public boolean contains(final Object key) {
            return parent.containsKey(key);
        }

        @Override
        public boolean remove(final Object key) {
            final boolean result = parent.containsKey(key);
            parent.remove(key);
            return result;
        }

        @Override
        public Iterator<K> iterator() {
            return parent.createKeySetIterator();
        }
    }

    
KeySet iterator.
/**
     * KeySet iterator.
     */
    protected static class KeySetIterator<K> extends HashIterator<K, Object> implements Iterator<K> {

        @SuppressWarnings("unchecked")
        protected KeySetIterator(final AbstractHashedMap<K, ?> parent) {
            super((AbstractHashedMap<K, Object>) parent);
        }

        @Override
        public K 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
     */
    @Override
    public Collection<V> 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<V> createValuesIterator() {
        if (size() == 0) {
            return EmptyIterator.<V>emptyIterator();
        }
        return new ValuesIterator<>(this);
    }

    
Values implementation.
/**
     * Values implementation.
     */
    protected static class Values<V> extends AbstractCollection<V> {
        
The parent map /** The parent map */
        private final AbstractHashedMap<?, V> parent;

        protected Values(final AbstractHashedMap<?, V> parent) {
            super();
            this.parent = parent;
        }

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

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

        @Override
        public boolean contains(final Object value) {
            return parent.containsValue(value);
        }

        @Override
        public Iterator<V> iterator() {
            return parent.createValuesIterator();
        }
    }

    
Values iterator.
/**
     * Values iterator.
     */
    protected static class ValuesIterator<V> extends HashIterator<Object, V> implements Iterator<V> {

        @SuppressWarnings("unchecked")
        protected ValuesIterator(final AbstractHashedMap<?, V> parent) {
            super((AbstractHashedMap<Object, V>) parent);
        }

        @Override
        public V 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<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
        
The next entry in the hash chain /** The next entry in the hash chain */
        protected HashEntry<K, V> 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(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
            super();
            this.next = next;
            this.hashCode = hashCode;
            this.key = key;
            this.value = value;
        }

        @Override
        @SuppressWarnings("unchecked")
        public K getKey() {
            if (key == NULL) {
                return null;
            }
            return (K) key;
        }

        @Override
        @SuppressWarnings("unchecked")
        public V getValue() {
            return (V) value;
        }

        @Override
        @SuppressWarnings("unchecked")
        public V setValue(final V value) {
            final Object old = this.value;
            this.value = value;
            return (V) old;
        }

        @Override
        public boolean equals(final Object obj) {
            if (obj == this) {
                return true;
            }
            if (obj instanceof Map.Entry == false) {
                return false;
            }
            final 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()));
        }

        @Override
        public int hashCode() {
            return (getKey() == null ? 0 : getKey().hashCode()) ^
                   (getValue() == null ? 0 : getValue().hashCode());
        }

        @Override
        public String toString() {
            return new StringBuilder().append(getKey()).append('=').append(getValue()).toString();
        }
    }

    
Base Iterator
/**
     * Base Iterator
     */
    protected static abstract class HashIterator<K, V> {

        
The parent map /** The parent map */
        private final AbstractHashedMap<K, V> parent;
        
The current index into the array of buckets /** The current index into the array of buckets */
        private int hashIndex;
        
The last returned entry /** The last returned entry */
        private HashEntry<K, V> last;
        
The next entry /** The next entry */
        private HashEntry<K, V> next;
        
The modification count expected /** The modification count expected */
        private int expectedModCount;

        protected HashIterator(final AbstractHashedMap<K, V> parent) {
            super();
            this.parent = parent;
            final HashEntry<K, V>[] data = parent.data;
            int i = data.length;
            HashEntry<K, V> 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<K, V> nextEntry() {
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            final HashEntry<K, V> newCurrent = next;
            if (newCurrent == null)  {
                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
            }
            final HashEntry<K, V>[] data = parent.data;
            int i = hashIndex;
            HashEntry<K, V> n = newCurrent.next;
            while (n == null && i > 0) {
                n = data[--i];
            }
            next = n;
            hashIndex = i;
            last = newCurrent;
            return newCurrent;
        }

        protected HashEntry<K, V> 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;
        }

        @Override
        public String toString() {
            if (last != null) {
                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
            }
            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
Throws:
IOException – if an error occurs while writing tothe 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
     * @throws IOException if an error occurs while writing tothe stream
     */
    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
        out.writeFloat(loadFactor);
        out.writeInt(data.length);
        out.writeInt(size);
        for (final MapIterator<K, V> 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
Throws:
IOException – if an error occurs while reading from the stream
ClassNotFoundException – if an object read from the stream can not be loaded/**
     * 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
     * @throws IOException if an error occurs while reading from the stream
     * @throws ClassNotFoundException if an object read from the stream can not be loaded
     */
    @SuppressWarnings("unchecked")
    protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        loadFactor = in.readFloat();
        final int capacity = in.readInt();
        final int size = in.readInt();
        init();
        threshold = calculateThreshold(capacity, loadFactor);
        data = new HashEntry[capacity];
        for (int i = 0; i < size; i++) {
            final K key = (K) in.readObject();
            final V value = (V) 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.
Throws:
InternalError – if AbstractMap.clone() failed
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
     * @throws InternalError if {@link AbstractMap#clone()} failed
     */
    @Override
    @SuppressWarnings("unchecked")
    protected AbstractHashedMap<K, V> clone() {
        try {
            final AbstractHashedMap<K, V> cloned = (AbstractHashedMap<K, V>) 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 (final CloneNotSupportedException ex) {
            throw new InternalError();
        }
    }

    
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
     */
    @Override
    public boolean equals(final Object obj) {
        if (obj == this) {
            return true;
        }
        if (obj instanceof Map == false) {
            return false;
        }
        final Map<?,?> map = (Map<?,?>) obj;
        if (map.size() != size()) {
            return false;
        }
        final MapIterator<?,?> it = mapIterator();
        try {
            while (it.hasNext()) {
                final Object key = it.next();
                final 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 (final ClassCastException ignored)   {
            return false;
        } catch (final 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
     */
    @Override
    public int hashCode() {
        int total = 0;
        final Iterator<Map.Entry<K, V>> 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
     */
    @Override
    public String toString() {
        if (size() == 0) {
            return "{}";
        }
        final StringBuilder buf = new StringBuilder(32 * size());
        buf.append('{');

        final MapIterator<K, V> it = mapIterator();
        boolean hasNext = it.hasNext();
        while (hasNext) {
            final K key = it.next();
            final V 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();
    }
}