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