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