001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.map;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.util.AbstractCollection;
023import java.util.AbstractMap;
024import java.util.AbstractSet;
025import java.util.Collection;
026import java.util.ConcurrentModificationException;
027import java.util.Iterator;
028import java.util.Map;
029import java.util.NoSuchElementException;
030import java.util.Set;
031
032import org.apache.commons.collections4.IterableMap;
033import org.apache.commons.collections4.KeyValue;
034import org.apache.commons.collections4.MapIterator;
035import org.apache.commons.collections4.iterators.EmptyIterator;
036import org.apache.commons.collections4.iterators.EmptyMapIterator;
037
038/**
039 * An abstract implementation of a hash-based map which provides numerous points for
040 * subclasses to override.
041 * <p>
042 * This class implements all the features necessary for a subclass hash-based map.
043 * Key-value entries are stored in instances of the <code>HashEntry</code> class,
044 * which can be overridden and replaced. The iterators can similarly be replaced,
045 * without the need to replace the KeySet, EntrySet and Values view classes.
046 * <p>
047 * Overridable methods are provided to change the default hashing behaviour, and
048 * to change how entries are added to and removed from the map. Hopefully, all you
049 * need for unusual subclasses is here.
050 * <p>
051 * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
052 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
053 * This extends clause will be removed in v4.0.
054 *
055 * @since 3.0
056 * @version $Id: AbstractHashedMap.HashIterator.html 887892 2013-11-24 13:43:45Z tn $
057 */
058public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {
059
060    protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
061    protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
062    protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
063    protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
064    protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
065    protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
066
067    /** The default capacity to use */
068    protected static final int DEFAULT_CAPACITY = 16;
069    /** The default threshold to use */
070    protected static final int DEFAULT_THRESHOLD = 12;
071    /** The default load factor to use */
072    protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
073    /** The maximum capacity allowed */
074    protected static final int MAXIMUM_CAPACITY = 1 << 30;
075    /** An object for masking null */
076    protected static final Object NULL = new Object();
077
078    /** Load factor, normally 0.75 */
079    transient float loadFactor;
080    /** The size of the map */
081    transient int size;
082    /** Map entries */
083    transient HashEntry<K, V>[] data;
084    /** Size at which to rehash */
085    transient int threshold;
086    /** Modification count for iterators */
087    transient int modCount;
088    /** Entry set */
089    transient EntrySet<K, V> entrySet;
090    /** Key set */
091    transient KeySet<K> keySet;
092    /** Values */
093    transient Values<V> values;
094
095    /**
096     * Constructor only used in deserialization, do not use otherwise.
097     */
098    protected AbstractHashedMap() {
099        super();
100    }
101
102    /**
103     * Constructor which performs no validation on the passed in parameters.
104     *
105     * @param initialCapacity  the initial capacity, must be a power of two
106     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
107     * @param threshold  the threshold, must be sensible
108     */
109    @SuppressWarnings("unchecked")
110    protected AbstractHashedMap(final int initialCapacity, final float loadFactor, final int threshold) {
111        super();
112        this.loadFactor = loadFactor;
113        this.data = new HashEntry[initialCapacity];
114        this.threshold = threshold;
115        init();
116    }
117
118    /**
119     * Constructs a new, empty map with the specified initial capacity and
120     * default load factor.
121     *
122     * @param initialCapacity  the initial capacity
123     * @throws IllegalArgumentException if the initial capacity is negative
124     */
125    protected AbstractHashedMap(final int initialCapacity) {
126        this(initialCapacity, DEFAULT_LOAD_FACTOR);
127    }
128
129    /**
130     * Constructs a new, empty map with the specified initial capacity and
131     * load factor.
132     *
133     * @param initialCapacity  the initial capacity
134     * @param loadFactor  the load factor
135     * @throws IllegalArgumentException if the initial capacity is negative
136     * @throws IllegalArgumentException if the load factor is less than or equal to zero
137     */
138    @SuppressWarnings("unchecked")
139    protected AbstractHashedMap(int initialCapacity, final float loadFactor) {
140        super();
141        if (initialCapacity < 0) {
142            throw new IllegalArgumentException("Initial capacity must be a non negative number");
143        }
144        if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
145            throw new IllegalArgumentException("Load factor must be greater than 0");
146        }
147        this.loadFactor = loadFactor;
148        initialCapacity = calculateNewCapacity(initialCapacity);
149        this.threshold = calculateThreshold(initialCapacity, loadFactor);
150        this.data = new HashEntry[initialCapacity];
151        init();
152    }
153
154    /**
155     * Constructor copying elements from another map.
156     *
157     * @param map  the map to copy
158     * @throws NullPointerException if the map is null
159     */
160    protected AbstractHashedMap(final Map<? extends K, ? extends V> map) {
161        this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
162        _putAll(map);
163    }
164
165    /**
166     * Initialise subclasses during construction, cloning or deserialization.
167     */
168    protected void init() {
169    }
170
171    //-----------------------------------------------------------------------
172    /**
173     * Gets the value mapped to the key specified.
174     *
175     * @param key  the key
176     * @return the mapped value, null if no match
177     */
178    @Override
179    public V get(Object key) {
180        key = convertKey(key);
181        final int hashCode = hash(key);
182        HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
183        while (entry != null) {
184            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
185                return entry.getValue();
186            }
187            entry = entry.next;
188        }
189        return null;
190    }
191
192    /**
193     * Gets the size of the map.
194     *
195     * @return the size
196     */
197    @Override
198    public int size() {
199        return size;
200    }
201
202    /**
203     * Checks whether the map is currently empty.
204     *
205     * @return true if the map is currently size zero
206     */
207    @Override
208    public boolean isEmpty() {
209        return size == 0;
210    }
211
212    //-----------------------------------------------------------------------
213    /**
214     * Checks whether the map contains the specified key.
215     *
216     * @param key  the key to search for
217     * @return true if the map contains the key
218     */
219    @Override
220    public boolean containsKey(Object key) {
221        key = convertKey(key);
222        final int hashCode = hash(key);
223        HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
224        while (entry != null) {
225            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
226                return true;
227            }
228            entry = entry.next;
229        }
230        return false;
231    }
232
233    /**
234     * Checks whether the map contains the specified value.
235     *
236     * @param value  the value to search for
237     * @return true if the map contains the value
238     */
239    @Override
240    public boolean containsValue(final Object value) {
241        if (value == null) {
242            for (final HashEntry<K, V> element : data) {
243                HashEntry<K, V> entry = element;
244                while (entry != null) {
245                    if (entry.getValue() == null) {
246                        return true;
247                    }
248                    entry = entry.next;
249                }
250            }
251        } else {
252            for (final HashEntry<K, V> element : data) {
253                HashEntry<K, V> entry = element;
254                while (entry != null) {
255                    if (isEqualValue(value, entry.getValue())) {
256                        return true;
257                    }
258                    entry = entry.next;
259                }
260            }
261        }
262        return false;
263    }
264
265    //-----------------------------------------------------------------------
266    /**
267     * Puts a key-value mapping into this map.
268     *
269     * @param key  the key to add
270     * @param value  the value to add
271     * @return the value previously mapped to this key, null if none
272     */
273    @Override
274    public V put(final K key, final V value) {
275        final Object convertedKey = convertKey(key);
276        final int hashCode = hash(convertedKey);
277        final int index = hashIndex(hashCode, data.length);
278        HashEntry<K, V> entry = data[index];
279        while (entry != null) {
280            if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) {
281                final V oldValue = entry.getValue();
282                updateEntry(entry, value);
283                return oldValue;
284            }
285            entry = entry.next;
286        }
287
288        addMapping(index, hashCode, key, value);
289        return null;
290    }
291
292    /**
293     * Puts all the values from the specified map into this map.
294     * <p>
295     * This implementation iterates around the specified map and
296     * uses {@link #put(Object, Object)}.
297     *
298     * @param map  the map to add
299     * @throws NullPointerException if the map is null
300     */
301    @Override
302    public void putAll(final Map<? extends K, ? extends V> map) {
303        _putAll(map);
304    }
305
306    /**
307     * Puts all the values from the specified map into this map.
308     * <p>
309     * This implementation iterates around the specified map and
310     * uses {@link #put(Object, Object)}.
311     * <p>
312     * It is private to allow the constructor to still call it
313     * even when putAll is overriden.
314     *
315     * @param map  the map to add
316     * @throws NullPointerException if the map is null
317     */
318    private void _putAll(final Map<? extends K, ? extends V> map) {
319        final int mapSize = map.size();
320        if (mapSize == 0) {
321            return;
322        }
323        final int newSize = (int) ((size + mapSize) / loadFactor + 1);
324        ensureCapacity(calculateNewCapacity(newSize));
325        for (final Map.Entry<? extends K, ? extends V> entry: map.entrySet()) {
326            put(entry.getKey(), entry.getValue());
327        }
328    }
329
330    /**
331     * Removes the specified mapping from this map.
332     *
333     * @param key  the mapping to remove
334     * @return the value mapped to the removed key, null if key not in map
335     */
336    @Override
337    public V remove(Object key) {
338        key = convertKey(key);
339        final int hashCode = hash(key);
340        final int index = hashIndex(hashCode, data.length);
341        HashEntry<K, V> entry = data[index];
342        HashEntry<K, V> previous = null;
343        while (entry != null) {
344            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
345                final V oldValue = entry.getValue();
346                removeMapping(entry, index, previous);
347                return oldValue;
348            }
349            previous = entry;
350            entry = entry.next;
351        }
352        return null;
353    }
354
355    /**
356     * Clears the map, resetting the size to zero and nullifying references
357     * to avoid garbage collection issues.
358     */
359    @Override
360    public void clear() {
361        modCount++;
362        final HashEntry<K, V>[] data = this.data;
363        for (int i = data.length - 1; i >= 0; i--) {
364            data[i] = null;
365        }
366        size = 0;
367    }
368
369    //-----------------------------------------------------------------------
370    /**
371     * Converts input keys to another object for storage in the map.
372     * This implementation masks nulls.
373     * Subclasses can override this to perform alternate key conversions.
374     * <p>
375     * The reverse conversion can be changed, if required, by overriding the
376     * getKey() method in the hash entry.
377     *
378     * @param key  the key convert
379     * @return the converted key
380     */
381    protected Object convertKey(final Object key) {
382        return key == null ? NULL : key;
383    }
384
385    /**
386     * Gets the hash code for the key specified.
387     * This implementation uses the additional hashing routine from JDK1.4.
388     * Subclasses can override this to return alternate hash codes.
389     *
390     * @param key  the key to get a hash code for
391     * @return the hash code
392     */
393    protected int hash(final Object key) {
394        // same as JDK 1.4
395        int h = key.hashCode();
396        h += ~(h << 9);
397        h ^=  h >>> 14;
398        h +=  h << 4;
399        h ^=  h >>> 10;
400        return h;
401    }
402
403    /**
404     * Compares two keys, in internal converted form, to see if they are equal.
405     * This implementation uses the equals method and assumes neither key is null.
406     * Subclasses can override this to match differently.
407     *
408     * @param key1  the first key to compare passed in from outside
409     * @param key2  the second key extracted from the entry via <code>entry.key</code>
410     * @return true if equal
411     */
412    protected boolean isEqualKey(final Object key1, final Object key2) {
413        return key1 == key2 || key1.equals(key2);
414    }
415
416    /**
417     * Compares two values, in external form, to see if they are equal.
418     * This implementation uses the equals method and assumes neither value is null.
419     * Subclasses can override this to match differently.
420     *
421     * @param value1  the first value to compare passed in from outside
422     * @param value2  the second value extracted from the entry via <code>getValue()</code>
423     * @return true if equal
424     */
425    protected boolean isEqualValue(final Object value1, final Object value2) {
426        return value1 == value2 || value1.equals(value2);
427    }
428
429    /**
430     * Gets the index into the data storage for the hashCode specified.
431     * This implementation uses the least significant bits of the hashCode.
432     * Subclasses can override this to return alternate bucketing.
433     *
434     * @param hashCode  the hash code to use
435     * @param dataSize  the size of the data to pick a bucket from
436     * @return the bucket index
437     */
438    protected int hashIndex(final int hashCode, final int dataSize) {
439        return hashCode & dataSize - 1;
440    }
441
442    //-----------------------------------------------------------------------
443    /**
444     * Gets the entry mapped to the key specified.
445     * <p>
446     * This method exists for subclasses that may need to perform a multi-step
447     * process accessing the entry. The public methods in this class don't use this
448     * method to gain a small performance boost.
449     *
450     * @param key  the key
451     * @return the entry, null if no match
452     */
453    protected HashEntry<K, V> getEntry(Object key) {
454        key = convertKey(key);
455        final int hashCode = hash(key);
456        HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)]; // no local for hash index
457        while (entry != null) {
458            if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
459                return entry;
460            }
461            entry = entry.next;
462        }
463        return null;
464    }
465
466    //-----------------------------------------------------------------------
467    /**
468     * Updates an existing key-value mapping to change the value.
469     * <p>
470     * This implementation calls <code>setValue()</code> on the entry.
471     * Subclasses could override to handle changes to the map.
472     *
473     * @param entry  the entry to update
474     * @param newValue  the new value to store
475     */
476    protected void updateEntry(final HashEntry<K, V> entry, final V newValue) {
477        entry.setValue(newValue);
478    }
479
480    /**
481     * Reuses an existing key-value mapping, storing completely new data.
482     * <p>
483     * This implementation sets all the data fields on the entry.
484     * Subclasses could populate additional entry fields.
485     *
486     * @param entry  the entry to update, not null
487     * @param hashIndex  the index in the data array
488     * @param hashCode  the hash code of the key to add
489     * @param key  the key to add
490     * @param value  the value to add
491     */
492    protected void reuseEntry(final HashEntry<K, V> entry, final int hashIndex, final int hashCode,
493                              final K key, final V value) {
494        entry.next = data[hashIndex];
495        entry.hashCode = hashCode;
496        entry.key = key;
497        entry.value = value;
498    }
499
500    //-----------------------------------------------------------------------
501    /**
502     * Adds a new key-value mapping into this map.
503     * <p>
504     * This implementation calls <code>createEntry()</code>, <code>addEntry()</code>
505     * and <code>checkCapacity()</code>.
506     * It also handles changes to <code>modCount</code> and <code>size</code>.
507     * Subclasses could override to fully control adds to the map.
508     *
509     * @param hashIndex  the index into the data array to store at
510     * @param hashCode  the hash code of the key to add
511     * @param key  the key to add
512     * @param value  the value to add
513     */
514    protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) {
515        modCount++;
516        final HashEntry<K, V> entry = createEntry(data[hashIndex], hashCode, key, value);
517        addEntry(entry, hashIndex);
518        size++;
519        checkCapacity();
520    }
521
522    /**
523     * Creates an entry to store the key-value data.
524     * <p>
525     * This implementation creates a new HashEntry instance.
526     * Subclasses can override this to return a different storage class,
527     * or implement caching.
528     *
529     * @param next  the next entry in sequence
530     * @param hashCode  the hash code to use
531     * @param key  the key to store
532     * @param value  the value to store
533     * @return the newly created entry
534     */
535    protected HashEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
536        return new HashEntry<K, V>(next, hashCode, convertKey(key), value);
537    }
538
539    /**
540     * Adds an entry into this map.
541     * <p>
542     * This implementation adds the entry to the data storage table.
543     * Subclasses could override to handle changes to the map.
544     *
545     * @param entry  the entry to add
546     * @param hashIndex  the index into the data array to store at
547     */
548    protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
549        data[hashIndex] = entry;
550    }
551
552    //-----------------------------------------------------------------------
553    /**
554     * Removes a mapping from the map.
555     * <p>
556     * This implementation calls <code>removeEntry()</code> and <code>destroyEntry()</code>.
557     * It also handles changes to <code>modCount</code> and <code>size</code>.
558     * Subclasses could override to fully control removals from the map.
559     *
560     * @param entry  the entry to remove
561     * @param hashIndex  the index into the data structure
562     * @param previous  the previous entry in the chain
563     */
564    protected void removeMapping(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
565        modCount++;
566        removeEntry(entry, hashIndex, previous);
567        size--;
568        destroyEntry(entry);
569    }
570
571    /**
572     * Removes an entry from the chain stored in a particular index.
573     * <p>
574     * This implementation removes the entry from the data storage table.
575     * The size is not updated.
576     * Subclasses could override to handle changes to the map.
577     *
578     * @param entry  the entry to remove
579     * @param hashIndex  the index into the data structure
580     * @param previous  the previous entry in the chain
581     */
582    protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
583        if (previous == null) {
584            data[hashIndex] = entry.next;
585        } else {
586            previous.next = entry.next;
587        }
588    }
589
590    /**
591     * Kills an entry ready for the garbage collector.
592     * <p>
593     * This implementation prepares the HashEntry for garbage collection.
594     * Subclasses can override this to implement caching (override clear as well).
595     *
596     * @param entry  the entry to destroy
597     */
598    protected void destroyEntry(final HashEntry<K, V> entry) {
599        entry.next = null;
600        entry.key = null;
601        entry.value = null;
602    }
603
604    //-----------------------------------------------------------------------
605    /**
606     * Checks the capacity of the map and enlarges it if necessary.
607     * <p>
608     * This implementation uses the threshold to check if the map needs enlarging
609     */
610    protected void checkCapacity() {
611        if (size >= threshold) {
612            final int newCapacity = data.length * 2;
613            if (newCapacity <= MAXIMUM_CAPACITY) {
614                ensureCapacity(newCapacity);
615            }
616        }
617    }
618
619    /**
620     * Changes the size of the data structure to the capacity proposed.
621     *
622     * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
623     */
624    @SuppressWarnings("unchecked")
625    protected void ensureCapacity(final int newCapacity) {
626        final int oldCapacity = data.length;
627        if (newCapacity <= oldCapacity) {
628            return;
629        }
630        if (size == 0) {
631            threshold = calculateThreshold(newCapacity, loadFactor);
632            data = new HashEntry[newCapacity];
633        } else {
634            final HashEntry<K, V> oldEntries[] = data;
635            final HashEntry<K, V> newEntries[] = new HashEntry[newCapacity];
636
637            modCount++;
638            for (int i = oldCapacity - 1; i >= 0; i--) {
639                HashEntry<K, V> entry = oldEntries[i];
640                if (entry != null) {
641                    oldEntries[i] = null;  // gc
642                    do {
643                        final HashEntry<K, V> next = entry.next;
644                        final int index = hashIndex(entry.hashCode, newCapacity);
645                        entry.next = newEntries[index];
646                        newEntries[index] = entry;
647                        entry = next;
648                    } while (entry != null);
649                }
650            }
651            threshold = calculateThreshold(newCapacity, loadFactor);
652            data = newEntries;
653        }
654    }
655
656    /**
657     * Calculates the new capacity of the map.
658     * This implementation normalizes the capacity to a power of two.
659     *
660     * @param proposedCapacity  the proposed capacity
661     * @return the normalized new capacity
662     */
663    protected int calculateNewCapacity(final int proposedCapacity) {
664        int newCapacity = 1;
665        if (proposedCapacity > MAXIMUM_CAPACITY) {
666            newCapacity = MAXIMUM_CAPACITY;
667        } else {
668            while (newCapacity < proposedCapacity) {
669                newCapacity <<= 1;  // multiply by two
670            }
671            if (newCapacity > MAXIMUM_CAPACITY) {
672                newCapacity = MAXIMUM_CAPACITY;
673            }
674        }
675        return newCapacity;
676    }
677
678    /**
679     * Calculates the new threshold of the map, where it will be resized.
680     * This implementation uses the load factor.
681     *
682     * @param newCapacity  the new capacity
683     * @param factor  the load factor
684     * @return the new resize threshold
685     */
686    protected int calculateThreshold(final int newCapacity, final float factor) {
687        return (int) (newCapacity * factor);
688    }
689
690    //-----------------------------------------------------------------------
691    /**
692     * Gets the <code>next</code> field from a <code>HashEntry</code>.
693     * Used in subclasses that have no visibility of the field.
694     *
695     * @param entry  the entry to query, must not be null
696     * @return the <code>next</code> field of the entry
697     * @throws NullPointerException if the entry is null
698     * @since 3.1
699     */
700    protected HashEntry<K, V> entryNext(final HashEntry<K, V> entry) {
701        return entry.next;
702    }
703
704    /**
705     * Gets the <code>hashCode</code> field from a <code>HashEntry</code>.
706     * Used in subclasses that have no visibility of the field.
707     *
708     * @param entry  the entry to query, must not be null
709     * @return the <code>hashCode</code> field of the entry
710     * @throws NullPointerException if the entry is null
711     * @since 3.1
712     */
713    protected int entryHashCode(final HashEntry<K, V> entry) {
714        return entry.hashCode;
715    }
716
717    /**
718     * Gets the <code>key</code> field from a <code>HashEntry</code>.
719     * Used in subclasses that have no visibility of the field.
720     *
721     * @param entry  the entry to query, must not be null
722     * @return the <code>key</code> field of the entry
723     * @throws NullPointerException if the entry is null
724     * @since 3.1
725     */
726    protected K entryKey(final HashEntry<K, V> entry) {
727        return entry.getKey();
728    }
729
730    /**
731     * Gets the <code>value</code> field from a <code>HashEntry</code>.
732     * Used in subclasses that have no visibility of the field.
733     *
734     * @param entry  the entry to query, must not be null
735     * @return the <code>value</code> field of the entry
736     * @throws NullPointerException if the entry is null
737     * @since 3.1
738     */
739    protected V entryValue(final HashEntry<K, V> entry) {
740        return entry.getValue();
741    }
742
743    //-----------------------------------------------------------------------
744    /**
745     * Gets an iterator over the map.
746     * Changes made to the iterator affect this map.
747     * <p>
748     * A MapIterator returns the keys in the map. It also provides convenient
749     * methods to get the key and value, and set the value.
750     * It avoids the need to create an entrySet/keySet/values object.
751     * It also avoids creating the Map.Entry object.
752     *
753     * @return the map iterator
754     */
755    public MapIterator<K, V> mapIterator() {
756        if (size == 0) {
757            return EmptyMapIterator.<K, V>emptyMapIterator();
758        }
759        return new HashMapIterator<K, V>(this);
760    }
761
762    /**
763     * MapIterator implementation.
764     */
765    protected static class HashMapIterator<K, V> extends HashIterator<K, V> implements MapIterator<K, V> {
766
767        protected HashMapIterator(final AbstractHashedMap<K, V> parent) {
768            super(parent);
769        }
770
771        public K next() {
772            return super.nextEntry().getKey();
773        }
774
775        public K getKey() {
776            final HashEntry<K, V> current = currentEntry();
777            if (current == null) {
778                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
779            }
780            return current.getKey();
781        }
782
783        public V getValue() {
784            final HashEntry<K, V> current = currentEntry();
785            if (current == null) {
786                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
787            }
788            return current.getValue();
789        }
790
791        public V setValue(final V value) {
792            final HashEntry<K, V> current = currentEntry();
793            if (current == null) {
794                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
795            }
796            return current.setValue(value);
797        }
798    }
799
800    //-----------------------------------------------------------------------
801    /**
802     * Gets the entrySet view of the map.
803     * Changes made to the view affect this map.
804     * To simply iterate through the entries, use {@link #mapIterator()}.
805     *
806     * @return the entrySet view
807     */
808    @Override
809    public Set<Map.Entry<K, V>> entrySet() {
810        if (entrySet == null) {
811            entrySet = new EntrySet<K, V>(this);
812        }
813        return entrySet;
814    }
815
816    /**
817     * Creates an entry set iterator.
818     * Subclasses can override this to return iterators with different properties.
819     *
820     * @return the entrySet iterator
821     */
822    protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
823        if (size() == 0) {
824            return EmptyIterator.<Map.Entry<K, V>>emptyIterator();
825        }
826        return new EntrySetIterator<K, V>(this);
827    }
828
829    /**
830     * EntrySet implementation.
831     */
832    protected static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
833        /** The parent map */
834        private final AbstractHashedMap<K, V> parent;
835
836        protected EntrySet(final AbstractHashedMap<K, V> parent) {
837            super();
838            this.parent = parent;
839        }
840
841        @Override
842        public int size() {
843            return parent.size();
844        }
845
846        @Override
847        public void clear() {
848            parent.clear();
849        }
850
851        @Override
852        public boolean contains(final Object entry) {
853            if (entry instanceof Map.Entry) {
854                final Map.Entry<?, ?> e = (Map.Entry<?, ?>) entry;
855                final Entry<K, V> match = parent.getEntry(e.getKey());
856                return match != null && match.equals(e);
857            }
858            return false;
859        }
860
861        @Override
862        public boolean remove(final Object obj) {
863            if (obj instanceof Map.Entry == false) {
864                return false;
865            }
866            if (contains(obj) == false) {
867                return false;
868            }
869            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
870            parent.remove(entry.getKey());
871            return true;
872        }
873
874        @Override
875        public Iterator<Map.Entry<K, V>> iterator() {
876            return parent.createEntrySetIterator();
877        }
878    }
879
880    /**
881     * EntrySet iterator.
882     */
883    protected static class EntrySetIterator<K, V> extends HashIterator<K, V> implements Iterator<Map.Entry<K, V>> {
884
885        protected EntrySetIterator(final AbstractHashedMap<K, V> parent) {
886            super(parent);
887        }
888
889        public Map.Entry<K, V> next() {
890            return super.nextEntry();
891        }
892    }
893
894    //-----------------------------------------------------------------------
895    /**
896     * Gets the keySet view of the map.
897     * Changes made to the view affect this map.
898     * To simply iterate through the keys, use {@link #mapIterator()}.
899     *
900     * @return the keySet view
901     */
902    @Override
903    public Set<K> keySet() {
904        if (keySet == null) {
905            keySet = new KeySet<K>(this);
906        }
907        return keySet;
908    }
909
910    /**
911     * Creates a key set iterator.
912     * Subclasses can override this to return iterators with different properties.
913     *
914     * @return the keySet iterator
915     */
916    protected Iterator<K> createKeySetIterator() {
917        if (size() == 0) {
918            return EmptyIterator.<K>emptyIterator();
919        }
920        return new KeySetIterator<K>(this);
921    }
922
923    /**
924     * KeySet implementation.
925     */
926    protected static class KeySet<K> extends AbstractSet<K> {
927        /** The parent map */
928        private final AbstractHashedMap<K, ?> parent;
929
930        protected KeySet(final AbstractHashedMap<K, ?> parent) {
931            super();
932            this.parent = parent;
933        }
934
935        @Override
936        public int size() {
937            return parent.size();
938        }
939
940        @Override
941        public void clear() {
942            parent.clear();
943        }
944
945        @Override
946        public boolean contains(final Object key) {
947            return parent.containsKey(key);
948        }
949
950        @Override
951        public boolean remove(final Object key) {
952            final boolean result = parent.containsKey(key);
953            parent.remove(key);
954            return result;
955        }
956
957        @Override
958        public Iterator<K> iterator() {
959            return parent.createKeySetIterator();
960        }
961    }
962
963    /**
964     * KeySet iterator.
965     */
966    protected static class KeySetIterator<K> extends HashIterator<K, Object> implements Iterator<K> {
967
968        @SuppressWarnings("unchecked")
969        protected KeySetIterator(final AbstractHashedMap<K, ?> parent) {
970            super((AbstractHashedMap<K, Object>) parent);
971        }
972
973        public K next() {
974            return super.nextEntry().getKey();
975        }
976    }
977
978    //-----------------------------------------------------------------------
979    /**
980     * Gets the values view of the map.
981     * Changes made to the view affect this map.
982     * To simply iterate through the values, use {@link #mapIterator()}.
983     *
984     * @return the values view
985     */
986    @Override
987    public Collection<V> values() {
988        if (values == null) {
989            values = new Values<V>(this);
990        }
991        return values;
992    }
993
994    /**
995     * Creates a values iterator.
996     * Subclasses can override this to return iterators with different properties.
997     *
998     * @return the values iterator
999     */
1000    protected Iterator<V> createValuesIterator() {
1001        if (size() == 0) {
1002            return EmptyIterator.<V>emptyIterator();
1003        }
1004        return new ValuesIterator<V>(this);
1005    }
1006
1007    /**
1008     * Values implementation.
1009     */
1010    protected static class Values<V> extends AbstractCollection<V> {
1011        /** The parent map */
1012        private final AbstractHashedMap<?, V> parent;
1013
1014        protected Values(final AbstractHashedMap<?, V> parent) {
1015            super();
1016            this.parent = parent;
1017        }
1018
1019        @Override
1020        public int size() {
1021            return parent.size();
1022        }
1023
1024        @Override
1025        public void clear() {
1026            parent.clear();
1027        }
1028
1029        @Override
1030        public boolean contains(final Object value) {
1031            return parent.containsValue(value);
1032        }
1033
1034        @Override
1035        public Iterator<V> iterator() {
1036            return parent.createValuesIterator();
1037        }
1038    }
1039
1040    /**
1041     * Values iterator.
1042     */
1043    protected static class ValuesIterator<V> extends HashIterator<Object, V> implements Iterator<V> {
1044
1045        @SuppressWarnings("unchecked")
1046        protected ValuesIterator(final AbstractHashedMap<?, V> parent) {
1047            super((AbstractHashedMap<Object, V>) parent);
1048        }
1049
1050        public V next() {
1051            return super.nextEntry().getValue();
1052        }
1053    }
1054
1055    //-----------------------------------------------------------------------
1056    /**
1057     * HashEntry used to store the data.
1058     * <p>
1059     * If you subclass <code>AbstractHashedMap</code> but not <code>HashEntry</code>
1060     * then you will not be able to access the protected fields.
1061     * The <code>entryXxx()</code> methods on <code>AbstractHashedMap</code> exist
1062     * to provide the necessary access.
1063     */
1064    protected static class HashEntry<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
1065        /** The next entry in the hash chain */
1066        protected HashEntry<K, V> next;
1067        /** The hash code of the key */
1068        protected int hashCode;
1069        /** The key */
1070        protected Object key;
1071        /** The value */
1072        protected Object value;
1073
1074        protected HashEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
1075            super();
1076            this.next = next;
1077            this.hashCode = hashCode;
1078            this.key = key;
1079            this.value = value;
1080        }
1081
1082        @SuppressWarnings("unchecked")
1083        public K getKey() {
1084            if (key == NULL) {
1085                return null;
1086            }
1087            return (K) key;
1088        }
1089
1090        @SuppressWarnings("unchecked")
1091        public V getValue() {
1092            return (V) value;
1093        }
1094
1095        @SuppressWarnings("unchecked")
1096        public V setValue(final V value) {
1097            final Object old = this.value;
1098            this.value = value;
1099            return (V) old;
1100        }
1101
1102        @Override
1103        public boolean equals(final Object obj) {
1104            if (obj == this) {
1105                return true;
1106            }
1107            if (obj instanceof Map.Entry == false) {
1108                return false;
1109            }
1110            final Map.Entry<?, ?> other = (Map.Entry<?, ?>) obj;
1111            return
1112                (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) &&
1113                (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()));
1114        }
1115
1116        @Override
1117        public int hashCode() {
1118            return (getKey() == null ? 0 : getKey().hashCode()) ^
1119                   (getValue() == null ? 0 : getValue().hashCode());
1120        }
1121
1122        @Override
1123        public String toString() {
1124            return new StringBuilder().append(getKey()).append('=').append(getValue()).toString();
1125        }
1126    }
1127
1128    /**
1129     * Base Iterator
1130     */
1131    protected static abstract class HashIterator<K, V> {
1132
1133        /** The parent map */
1134        private final AbstractHashedMap<K, V> parent;
1135        /** The current index into the array of buckets */
1136        private int hashIndex;
1137        /** The last returned entry */
1138        private HashEntry<K, V> last;
1139        /** The next entry */
1140        private HashEntry<K, V> next;
1141        /** The modification count expected */
1142        private int expectedModCount;
1143
1144        protected HashIterator(final AbstractHashedMap<K, V> parent) {
1145            super();
1146            this.parent = parent;
1147            final HashEntry<K, V>[] data = parent.data;
1148            int i = data.length;
1149            HashEntry<K, V> next = null;
1150            while (i > 0 && next == null) {
1151                next = data[--i];
1152            }
1153            this.next = next;
1154            this.hashIndex = i;
1155            this.expectedModCount = parent.modCount;
1156        }
1157
1158        public boolean hasNext() {
1159            return next != null;
1160        }
1161
1162        protected HashEntry<K, V> nextEntry() {
1163            if (parent.modCount != expectedModCount) {
1164                throw new ConcurrentModificationException();
1165            }
1166            final HashEntry<K, V> newCurrent = next;
1167            if (newCurrent == null)  {
1168                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
1169            }
1170            final HashEntry<K, V>[] data = parent.data;
1171            int i = hashIndex;
1172            HashEntry<K, V> n = newCurrent.next;
1173            while (n == null && i > 0) {
1174                n = data[--i];
1175            }
1176            next = n;
1177            hashIndex = i;
1178            last = newCurrent;
1179            return newCurrent;
1180        }
1181
1182        protected HashEntry<K, V> currentEntry() {
1183            return last;
1184        }
1185
1186        public void remove() {
1187            if (last == null) {
1188                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
1189            }
1190            if (parent.modCount != expectedModCount) {
1191                throw new ConcurrentModificationException();
1192            }
1193            parent.remove(last.getKey());
1194            last = null;
1195            expectedModCount = parent.modCount;
1196        }
1197
1198        @Override
1199        public String toString() {
1200            if (last != null) {
1201                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
1202            }
1203            return "Iterator[]";
1204        }
1205    }
1206
1207    //-----------------------------------------------------------------------
1208    /**
1209     * Writes the map data to the stream. This method must be overridden if a
1210     * subclass must be setup before <code>put()</code> is used.
1211     * <p>
1212     * Serialization is not one of the JDK's nicest topics. Normal serialization will
1213     * initialise the superclass before the subclass. Sometimes however, this isn't
1214     * what you want, as in this case the <code>put()</code> method on read can be
1215     * affected by subclass state.
1216     * <p>
1217     * The solution adopted here is to serialize the state data of this class in
1218     * this protected method. This method must be called by the
1219     * <code>writeObject()</code> of the first serializable subclass.
1220     * <p>
1221     * Subclasses may override if they have a specific field that must be present
1222     * on read before this implementation will work. Generally, the read determines
1223     * what must be serialized here, if anything.
1224     *
1225     * @param out  the output stream
1226     * @throws IOException if an error occurs while writing tothe stream
1227     */
1228    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
1229        out.writeFloat(loadFactor);
1230        out.writeInt(data.length);
1231        out.writeInt(size);
1232        for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
1233            out.writeObject(it.next());
1234            out.writeObject(it.getValue());
1235        }
1236    }
1237
1238    /**
1239     * Reads the map data from the stream. This method must be overridden if a
1240     * subclass must be setup before <code>put()</code> is used.
1241     * <p>
1242     * Serialization is not one of the JDK's nicest topics. Normal serialization will
1243     * initialise the superclass before the subclass. Sometimes however, this isn't
1244     * what you want, as in this case the <code>put()</code> method on read can be
1245     * affected by subclass state.
1246     * <p>
1247     * The solution adopted here is to deserialize the state data of this class in
1248     * this protected method. This method must be called by the
1249     * <code>readObject()</code> of the first serializable subclass.
1250     * <p>
1251     * Subclasses may override if the subclass has a specific field that must be present
1252     * before <code>put()</code> or <code>calculateThreshold()</code> will work correctly.
1253     *
1254     * @param in  the input stream
1255     * @throws IOException if an error occurs while reading from the stream
1256     * @throws ClassNotFoundException if an object read from the stream can not be loaded
1257     */
1258    @SuppressWarnings("unchecked")
1259    protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
1260        loadFactor = in.readFloat();
1261        final int capacity = in.readInt();
1262        final int size = in.readInt();
1263        init();
1264        threshold = calculateThreshold(capacity, loadFactor);
1265        data = new HashEntry[capacity];
1266        for (int i = 0; i < size; i++) {
1267            final K key = (K) in.readObject();
1268            final V value = (V) in.readObject();
1269            put(key, value);
1270        }
1271    }
1272
1273    //-----------------------------------------------------------------------
1274    /**
1275     * Clones the map without cloning the keys or values.
1276     * <p>
1277     * To implement <code>clone()</code>, a subclass must implement the
1278     * <code>Cloneable</code> interface and make this method public.
1279     *
1280     * @return a shallow clone
1281     * @throws InternalError if {@link AbstractMap#clone()} failed
1282     */
1283    @Override
1284    @SuppressWarnings("unchecked")
1285    protected AbstractHashedMap<K, V> clone() {
1286        try {
1287            final AbstractHashedMap<K, V> cloned = (AbstractHashedMap<K, V>) super.clone();
1288            cloned.data = new HashEntry[data.length];
1289            cloned.entrySet = null;
1290            cloned.keySet = null;
1291            cloned.values = null;
1292            cloned.modCount = 0;
1293            cloned.size = 0;
1294            cloned.init();
1295            cloned.putAll(this);
1296            return cloned;
1297        } catch (final CloneNotSupportedException ex) {
1298            throw new InternalError();
1299        }
1300    }
1301
1302    /**
1303     * Compares this map with another.
1304     *
1305     * @param obj  the object to compare to
1306     * @return true if equal
1307     */
1308    @Override
1309    public boolean equals(final Object obj) {
1310        if (obj == this) {
1311            return true;
1312        }
1313        if (obj instanceof Map == false) {
1314            return false;
1315        }
1316        final Map<?,?> map = (Map<?,?>) obj;
1317        if (map.size() != size()) {
1318            return false;
1319        }
1320        final MapIterator<?,?> it = mapIterator();
1321        try {
1322            while (it.hasNext()) {
1323                final Object key = it.next();
1324                final Object value = it.getValue();
1325                if (value == null) {
1326                    if (map.get(key) != null || map.containsKey(key) == false) {
1327                        return false;
1328                    }
1329                } else {
1330                    if (value.equals(map.get(key)) == false) {
1331                        return false;
1332                    }
1333                }
1334            }
1335        } catch (final ClassCastException ignored)   {
1336            return false;
1337        } catch (final NullPointerException ignored) {
1338            return false;
1339        }
1340        return true;
1341    }
1342
1343    /**
1344     * Gets the standard Map hashCode.
1345     *
1346     * @return the hash code defined in the Map interface
1347     */
1348    @Override
1349    public int hashCode() {
1350        int total = 0;
1351        final Iterator<Map.Entry<K, V>> it = createEntrySetIterator();
1352        while (it.hasNext()) {
1353            total += it.next().hashCode();
1354        }
1355        return total;
1356    }
1357
1358    /**
1359     * Gets the map as a String.
1360     *
1361     * @return a string version of the map
1362     */
1363    @Override
1364    public String toString() {
1365        if (size() == 0) {
1366            return "{}";
1367        }
1368        final StringBuilder buf = new StringBuilder(32 * size());
1369        buf.append('{');
1370
1371        final MapIterator<K, V> it = mapIterator();
1372        boolean hasNext = it.hasNext();
1373        while (hasNext) {
1374            final K key = it.next();
1375            final V value = it.getValue();
1376            buf.append(key == this ? "(this Map)" : key)
1377               .append('=')
1378               .append(value == this ? "(this Map)" : value);
1379
1380            hasNext = it.hasNext();
1381            if (hasNext) {
1382                buf.append(',').append(' ');
1383            }
1384        }
1385
1386        buf.append('}');
1387        return buf.toString();
1388    }
1389}