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