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