    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.Objects;
    032import java.util.Set;
    033
    034import org.apache.commons.collections4.CollectionUtils;
    035import org.apache.commons.collections4.IterableMap;
    036import org.apache.commons.collections4.KeyValue;
    037import org.apache.commons.collections4.MapIterator;
    038import org.apache.commons.collections4.iterators.EmptyIterator;
    039import org.apache.commons.collections4.iterators.EmptyMapIterator;
    040
    041/**
    042 * An abstract implementation of a hash-based map which provides numerous points for
    043 * subclasses to override.
    044 * <p>
    045 * This class implements all the features necessary for a subclass hash-based map.
    046 * Key-value entries are stored in instances of the {@code HashEntry} class,
    047 * which can be overridden and replaced. The iterators can similarly be replaced,
    048 * without the need to replace the KeySet, EntrySet and Values view classes.
    049 * </p>
    050 * <p>
    051 * Overridable methods are provided to change the default hashing behavior, and
    052 * to change how entries are added to and removed from the map. Hopefully, all you
    053 * need for unusual subclasses is here.
    054 * </p>
    055 * <p>
    056 * NOTE: From Commons Collections 3.1 this class extends AbstractMap.
    057 * This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1.
    058 * This extends clause will be removed in v5.0.
    059 * </p>
    060 *
    061 * @param <K> the type of the keys in this map
    062 * @param <V> the type of the values in this map
    063 * @since 3.0
    064 */
    065public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {
    066
    067    /**
    068     * EntrySet implementation.
    069     *
    070     * @param <K> the type of the keys in the map
    071     * @param <V> the type of the values in the map
    072     */
    073    protected static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
    074
    075        /** The parent map */
    076        private final AbstractHashedMap<K, V> parent;
    077
    078        /**
    079         * Constructs a new instance.
    080         *
    081         * @param parent The parent map.
    082         */
    083        protected EntrySet(final AbstractHashedMap<K, V> parent) {
    084            this.parent = parent;
    085        }
    086
    087        @Override
    088        public void clear() {
    089            parent.clear();
    090        }
    091
    092        @Override
    093        public boolean contains(final Object entry) {
    094            if (entry instanceof Map.Entry) {
    095                final Map.Entry<?, ?> e = (Map.Entry<?, ?>) entry;
    096                final Entry<K, V> match = parent.getEntry(e.getKey());
    097                return match != null && match.equals(e);
    098            }
    099            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}