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