View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.collections4.map;
18  
19  import java.io.IOException;
20  import java.io.ObjectInputStream;
21  import java.io.ObjectOutputStream;
22  import java.util.AbstractCollection;
23  import java.util.AbstractMap;
24  import java.util.AbstractSet;
25  import java.util.Collection;
26  import java.util.ConcurrentModificationException;
27  import java.util.Iterator;
28  import java.util.Map;
29  import java.util.NoSuchElementException;
30  import java.util.Set;
31  
32  import org.apache.commons.collections4.IterableMap;
33  import org.apache.commons.collections4.KeyValue;
34  import org.apache.commons.collections4.MapIterator;
35  import org.apache.commons.collections4.iterators.EmptyIterator;
36  import org.apache.commons.collections4.iterators.EmptyMapIterator;
37  
38  /**
39   * An abstract implementation of a hash-based map which provides numerous points for
40   * subclasses to override.
41   * <p>
42   * This class implements all the features necessary for a subclass hash-based map.
43   * Key-value entries are stored in instances of the <code>HashEntry</code> class,
44   * which can be overridden and replaced. The iterators can similarly be replaced,
45   * without the need to replace the KeySet, EntrySet and Values view classes.
46   * <p>
47   * Overridable methods are provided to change the default hashing behaviour, and
48   * to change how entries are added to and removed from the map. Hopefully, all you
49   * need for unusual subclasses is here.
50   * <p>
51   * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
52   * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
53   * This extends clause will be removed in v5.0.
54   *
55   * @param <K> the type of the keys in this map
56   * @param <V> the type of the values in this map
57   * @since 3.0
58   */
59  public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {
60  
61      protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
62      protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
63      protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
64      protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
65      protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
66      protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
67  
68      /** The default capacity to use */
69      protected static final int DEFAULT_CAPACITY = 16;
70      /** The default threshold to use */
71      protected static final int DEFAULT_THRESHOLD = 12;
72      /** The default load factor to use */
73      protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
74      /** The maximum capacity allowed */
75      protected static final int MAXIMUM_CAPACITY = 1 << 30;
76      /** An object for masking null */
77      protected static final Object NULL = new Object();
78  
79      /** Load factor, normally 0.75 */
80      transient float loadFactor;
81      /** The size of the map */
82      transient int size;
83      /** Map entries */
84      transient HashEntry<K, V>[] data;
85      /** Size at which to rehash */
86      transient int threshold;
87      /** Modification count for iterators */
88      transient int modCount;
89      /** Entry set */
90      transient EntrySet<K, V> entrySet;
91      /** Key set */
92      transient KeySet<K> keySet;
93      /** Values */
94      transient Values<V> values;
95  
96      /**
97       * Constructor only used in deserialization, do not use otherwise.
98       */
99      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 }