    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.lang.ref.Reference;
    023import java.lang.ref.ReferenceQueue;
    024import java.lang.ref.SoftReference;
    025import java.lang.ref.WeakReference;
    026import java.util.ArrayList;
    027import java.util.Collection;
    028import java.util.ConcurrentModificationException;
    029import java.util.Iterator;
    030import java.util.List;
    031import java.util.Map;
    032import java.util.NoSuchElementException;
    033import java.util.Objects;
    034import java.util.Set;
    035
    036import org.apache.commons.collections4.MapIterator;
    037import org.apache.commons.collections4.keyvalue.DefaultMapEntry;
    038
    039/**
    040 * An abstract implementation of a hash-based map that allows the entries to
    041 * be removed by the garbage collector.
    042 * <p>
    043 * This class implements all the features necessary for a subclass reference
    044 * hash-based map. Key-value entries are stored in instances of the
    045 * {@code ReferenceEntry} class which can be overridden and replaced.
    046 * The iterators can similarly be replaced, without the need to replace the KeySet,
    047 * EntrySet and Values view classes.
    048 * </p>
    049 * <p>
    050 * Overridable methods are provided to change the default hashing behavior, and
    051 * to change how entries are added to and removed from the map. Hopefully, all you
    052 * need for unusual subclasses is here.
    053 * </p>
    054 * <p>
    055 * When you construct an {@code AbstractReferenceMap}, you can specify what
    056 * kind of references are used to store the map's keys and values.
    057 * If non-hard references are used, then the garbage collector can remove
    058 * mappings if a key or value becomes unreachable, or if the JVM's memory is
    059 * running low. For information on how the different reference types behave,
    060 * see {@link Reference}.
    061 * </p>
    062 * <p>
    063 * Different types of references can be specified for keys and values.
    064 * The keys can be configured to be weak but the values hard,
    065 * in which case this class will behave like a
    066 * <a href="https://docs.oracle.com/javase/8/docs/api/java/util/WeakHashMap.html">
    067 * {@code WeakHashMap}</a>. However, you can also specify hard keys and
    068 * weak values, or any other combination. The default constructor uses
    069 * hard keys and soft values, providing a memory-sensitive cache.
    070 * </p>
    071 * <p>
    072 * This {@link Map} implementation does <i>not</i> allow null elements.
    073 * Attempting to add a null key or value to the map will raise a
    074 * {@code NullPointerException}.
    075 * </p>
    076 * <p>
    077 * All the available iterators can be reset back to the start by casting to
    078 * {@code ResettableIterator} and calling {@code reset()}.
    079 * </p>
    080 * <p>
    081 * This implementation is not synchronized.
    082 * You can use {@link java.util.Collections#synchronizedMap} to
    083 * provide synchronized access to a {@code ReferenceMap}.
    084 * </p>
    085 *
    086 * @param <K> the type of the keys in this map
    087 * @param <V> the type of the values in this map
    088 *
    089 * @see java.lang.ref.Reference
    090 * @since 3.1 (extracted from ReferenceMap in 3.0)
    091 */
    092public abstract class AbstractReferenceMap<K, V> extends AbstractHashedMap<K, V> {
    093
    094    /**
    095     * Base iterator class.
    096     */
    097    static class ReferenceBaseIterator<K, V> {
    098        /** The parent map */
    099        final AbstractReferenceMap<K, V> parent;
    100
    101        // These fields keep track of where we are in the table.
    102        int index;
    103        ReferenceEntry<K, V> next;
    104        ReferenceEntry<K, V> current;
    105
    106        // These Object fields provide hard references to the
    107        // current and next entry; this assures that if hasNext()
    108        // returns true, next() will actually return a valid element.
    109        K currentKey, nextKey;
    110        V currentValue, nextValue;
    111
    112        int expectedModCount;
    113
    114        ReferenceBaseIterator(final AbstractReferenceMap<K, V> parent) {
    115            this.parent = parent;
    116            index = !parent.isEmpty() ? parent.data.length : 0;
    117            // have to do this here!  size() invocation above
    118            // may have altered the modCount.
    119            expectedModCount = parent.modCount;
    120        }
    121
    122        private void checkMod() {
    123            if (parent.modCount != expectedModCount) {
    124                throw new ConcurrentModificationException();
    125            }
    126        }
    127
    128        protected ReferenceEntry<K, V> currentEntry() {
    129            checkMod();
    130            return current;
    131        }
    132
    133        public boolean hasNext() {
    134            checkMod();
    135            while (nextNull()) {
    136                ReferenceEntry<K, V> e = next;
    137                int i = index;
    138                while (e == null && i > 0) {
    139                    i--;
    140                    e = (ReferenceEntry<K, V>) parent.data[i];
    141                }
    142                next = e;
    143                index = i;
    144                if (e == null) {
    145                    return false;
    146                }
    147                nextKey = e.getKey();
    148                nextValue = e.getValue();
    149                if (nextNull()) {
    150                    next = next.next();
    151                }
    152            }
    153            return true;
    154        }
    155
    156        protected ReferenceEntry<K, V> nextEntry() {
    157            checkMod();
    158            if (nextNull() && !hasNext()) {
    159                throw new NoSuchElementException();
    160            }
    161            current = next;
    162            next = next.next();
    163            currentKey = nextKey;
    164            currentValue = nextValue;
    165            nextKey = null;
    166            nextValue = null;
    167            return current;
    168        }
    169
    170        private boolean nextNull() {
    171            return nextKey == null || nextValue == null;
    172        }
    173
    174        public void remove() {
    175            checkMod();
    176            if (current == null) {
    177                throw new IllegalStateException();
    178            }
    179            parent.remove(currentKey);
    180            current = null;
    181            currentKey = null;
    182            currentValue = null;
    183            expectedModCount = parent.modCount;
    184        }
    185    }
    186
    187    /**
    188     * A MapEntry implementation for the map.
    189     * <p>
    190     * If getKey() or getValue() returns null, it means
    191     * the mapping is stale and should be removed.
    192     * </p>
    193     *
    194     * @param <K> the type of the keys
    195     * @param <V> the type of the values
    196     * @since 3.1
    197     */
    198    protected static class ReferenceEntry<K, V> extends HashEntry<K, V> {
    199        /** The parent map */
    200        private final AbstractReferenceMap<K, V> parent;
    201
    202        /**
    203         * Creates a new entry object for the ReferenceMap.
    204         *
    205         * @param parent  the parent map
    206         * @param next  the next entry in the hash bucket
    207         * @param hashCode  the hash code of the key
    208         * @param key  the key
    209         * @param value  the value
    210         */
    211        public ReferenceEntry(final AbstractReferenceMap<K, V> parent, final HashEntry<K, V> next,
    212                              final int hashCode, final K key, final V value) {
    213            super(next, hashCode, null, null);
    214            this.parent = parent;
    215            this.key = toReference(parent.keyType, key, hashCode);
    216            this.value = toReference(parent.valueType, value, hashCode); // the key hashCode is passed in deliberately
    217        }
    218
    219        /**
    220         * Compares this map entry to another.
    221         * <p>
    222         * This implementation uses {@code isEqualKey} and
    223         * {@code isEqualValue} on the main map for comparison.
    224         *
    225         * @param obj  the other map entry to compare to
    226         * @return true if equal, false if not
    227         */
    228        @Override
    229        public boolean equals(final Object obj) {
    230            if (obj == this) {
    231                return true;
    232            }
    233            if (!(obj instanceof Map.Entry)) {
    234                return false;
    235            }
    236
    237            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    238            final Object entryKey = entry.getKey();  // convert to hard reference
    239            final Object entryValue = entry.getValue();  // convert to hard reference
    240            if (entryKey == null || entryValue == null) {
    241                return false;
    242            }
    243            // compare using map methods, aiding identity subclass
    244            // note that key is direct access and value is via method
    245            return parent.isEqualKey(entryKey, key) &&
    246                   parent.isEqualValue(entryValue, getValue());
    247        }
    248
    249        /**
    250         * Gets the key from the entry.
    251         * This method dereferences weak and soft keys and thus may return null.
    252         *
    253         * @return the key, which may be null if it was garbage collected
    254         */
    255        @Override
    256        @SuppressWarnings("unchecked")
    257        public K getKey() {
    258            return (K) (parent.keyType == ReferenceStrength.HARD ? key : ((Reference<K>) key).get());
    259        }
    260
    261        /**
    262         * Gets the value from the entry.
    263         * This method dereferences weak and soft value and thus may return null.
    264         *
    265         * @return the value, which may be null if it was garbage collected
    266         */
    267        @Override
    268        @SuppressWarnings("unchecked")
    269        public V getValue() {
    270            return (V) (parent.valueType == ReferenceStrength.HARD ? value : ((Reference<V>) value).get());
    271        }
    272
    273        /**
    274         * Gets the hash code of the entry using temporary hard references.
    275         * <p>
    276         * This implementation uses {@code hashEntry} on the main map.
    277         *
    278         * @return the hash code of the entry
    279         */
    280        @Override
    281        public int hashCode() {
    282            return parent.hashEntry(getKey(), getValue());
    283        }
    284
    285        /**
    286         * Gets the next entry in the bucket.
    287         *
    288         * @return the next entry in the bucket
    289         */
    290        protected ReferenceEntry<K, V> next() {
    291            return (ReferenceEntry<K, V>) next;
    292        }
    293
    294        /**
    295         * This method can be overridden to provide custom logic to purge value
    296         */
    297        protected void nullValue() {
    298            value = null;
    299        }
    300
    301        /**
    302         * This is the callback for custom "after purge" logic
    303         */
    304        protected void onPurge() {
    305            // empty
    306        }
    307
    308        /**
    309         * Purges the specified reference
    310         * @param ref  the reference to purge
    311         * @return true or false
    312         */
    313        protected boolean purge(final Reference<?> ref) {
    314            boolean r = parent.keyType != ReferenceStrength.HARD && key == ref;
    315            r = r || parent.valueType != ReferenceStrength.HARD && value == ref;
    316            if (r) {
    317                if (parent.keyType != ReferenceStrength.HARD) {
    318                    ((Reference<?>) key).clear();
    319                }
    320                if (parent.valueType != ReferenceStrength.HARD) {
    321                    ((Reference<?>) value).clear();
    322                } else if (parent.purgeValues) {
    323                    nullValue();
    324                }
    325            }
    326            return r;
    327        }
    328
    329        /**
    330         * Sets the value of the entry.
    331         *
    332         * @param obj  the object to store
    333         * @return the previous value
    334         */
    335        @Override
    336        @SuppressWarnings("unchecked")
    337        public V setValue(final V obj) {
    338            final V old = getValue();
    339            if (parent.valueType != ReferenceStrength.HARD) {
    340                ((Reference<V>) value).clear();
    341            }
    342            value = toReference(parent.valueType, obj, hashCode);
    343            return old;
    344        }
    345
    346        /**
    347         * Constructs a reference of the given type to the given referent.
    348         * The reference is registered with the queue for later purging.
    349         *
    350         * @param <T> the type of the referenced object
    351         * @param type  HARD, SOFT or WEAK
    352         * @param referent  the object to refer to
    353         * @param hash  the hash code of the <i>key</i> of the mapping;
    354         *    this number might be different from referent.hashCode() if
    355         *    the referent represents a value and not a key
    356         * @return the reference to the object
    357         */
    358        protected <T> Object toReference(final ReferenceStrength type, final T referent, final int hash) {
    359            if (type == ReferenceStrength.HARD) {
    360                return referent;
    361            }
    362            if (type == ReferenceStrength.SOFT) {
    363                return new SoftRef<>(hash, referent, parent.queue);
    364            }
    365            if (type == ReferenceStrength.WEAK) {
    366                return new WeakRef<>(hash, referent, parent.queue);
    367            }
    368            throw new Error();
    369        }
    370    }
    371
    372    /**
    373     * EntrySet implementation.
    374     */
    375    static class ReferenceEntrySet<K, V> extends EntrySet<K, V> {
    376
    377        protected ReferenceEntrySet(final AbstractHashedMap<K, V> parent) {
    378            super(parent);
    379        }
    380
    381        @Override
    382        public Object[] toArray() {
    383            return toArray(new Object[size()]);
    384        }
    385
    386        @Override
    387        public <T> T[] toArray(final T[] arr) {
    388            // special implementation to handle disappearing entries
    389            final ArrayList<Map.Entry<K, V>> list = new ArrayList<>(size());
    390            for (final Map.Entry<K, V> entry : this) {
    391                list.add(new DefaultMapEntry<>(entry));
    392            }
    393            return list.toArray(arr);
    394        }
    395    }
    396
    397    /**
    398     * The EntrySet iterator.
    399     */
    400    static class ReferenceEntrySetIterator<K, V>
    401            extends ReferenceBaseIterator<K, V> implements Iterator<Map.Entry<K, V>> {
    402
    403        ReferenceEntrySetIterator(final AbstractReferenceMap<K, V> parent) {
    404            super(parent);
    405        }
    406
    407        @Override
    408        public Map.Entry<K, V> next() {
    409            return nextEntry();
    410        }
    411
    412    }
    413
    414    /**
    415     * KeySet implementation.
    416     */
    417    static class ReferenceKeySet<K> extends KeySet<K> {
    418
    419        protected ReferenceKeySet(final AbstractHashedMap<K, ?> parent) {
    420            super(parent);
    421        }
    422
    423        @Override
    424        public Object[] toArray() {
    425            return toArray(new Object[size()]);
    426        }
    427
    428        @Override
    429        public <T> T[] toArray(final T[] arr) {
    430            // special implementation to handle disappearing keys
    431            final List<K> list = new ArrayList<>(size());
    432            for (final K key : this) {
    433                list.add(key);
    434            }
    435            return list.toArray(arr);
    436        }
    437    }
    438
    439    /**
    440     * The keySet iterator.
    441     */
    442    static class ReferenceKeySetIterator<K> extends ReferenceBaseIterator<K, Object> implements Iterator<K> {
    443
    444        @SuppressWarnings("unchecked")
    445        ReferenceKeySetIterator(final AbstractReferenceMap<K, ?> parent) {
    446            super((AbstractReferenceMap<K, Object>) parent);
    447        }
    448
    449        @Override
    450        public K next() {
    451            return nextEntry().getKey();
    452        }
    453    }
    454
    455    /**
    456     * The MapIterator implementation.
    457     */
    458    static class ReferenceMapIterator<K, V> extends ReferenceBaseIterator<K, V> implements MapIterator<K, V> {
    459
    460        protected ReferenceMapIterator(final AbstractReferenceMap<K, V> parent) {
    461            super(parent);
    462        }
    463
    464        @Override
    465        public K getKey() {
    466            final HashEntry<K, V> current = currentEntry();
    467            if (current == null) {
    468                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
    469            }
    470            return current.getKey();
    471        }
    472
    473        @Override
    474        public V getValue() {
    475            final HashEntry<K, V> current = currentEntry();
    476            if (current == null) {
    477                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
    478            }
    479            return current.getValue();
    480        }
    481
    482        @Override
    483        public K next() {
    484            return nextEntry().getKey();
    485        }
    486
    487        @Override
    488        public V setValue(final V value) {
    489            final HashEntry<K, V> current = currentEntry();
    490            if (current == null) {
    491                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
    492            }
    493            return current.setValue(value);
    494        }
    495    }
    496
    497    /**
    498     * Reference type enum.
    499     */
    500    public enum ReferenceStrength {
    501        HARD(0), SOFT(1), WEAK(2);
    502
    503        /**
    504         * Resolve enum from int.
    505         * @param value  the int value
    506         * @return ReferenceType
    507         * @throws IllegalArgumentException if the specified value is invalid.
    508         */
    509        public static ReferenceStrength resolve(final int value) {
    510            switch (value) {
    511            case 0:
    512                return HARD;
    513            case 1:
    514                return SOFT;
    515            case 2:
    516                return WEAK;
    517            default:
    518                throw new IllegalArgumentException();
    519            }
    520        }
    521
    522        /** Value */
    523        public final int value;
    524
    525        ReferenceStrength(final int value) {
    526            this.value = value;
    527        }
    528
    529    }
    530
    531    /**
    532     * Values implementation.
    533     */
    534    static class ReferenceValues<V> extends Values<V> {
    535
    536        protected ReferenceValues(final AbstractHashedMap<?, V> parent) {
    537            super(parent);
    538        }
    539
    540        @Override
    541        public Object[] toArray() {
    542            return toArray(new Object[size()]);
    543        }
    544
    545        @Override
    546        public <T> T[] toArray(final T[] arr) {
    547            // special implementation to handle disappearing values
    548            final List<V> list = new ArrayList<>(size());
    549            for (final V value : this) {
    550                list.add(value);
    551            }
    552            return list.toArray(arr);
    553        }
    554    }
    555
    556    /**
    557     * The values iterator.
    558     */
    559    static class ReferenceValuesIterator<V> extends ReferenceBaseIterator<Object, V> implements Iterator<V> {
    560
    561        @SuppressWarnings("unchecked")
    562        ReferenceValuesIterator(final AbstractReferenceMap<?, V> parent) {
    563            super((AbstractReferenceMap<Object, V>) parent);
    564        }
    565
    566        @Override
    567        public V next() {
    568            return nextEntry().getValue();
    569        }
    570    }
    571
    572    /**
    573     * A soft reference holder.
    574     */
    575    static class SoftRef<T> extends SoftReference<T> {
    576        /** The hashCode of the key (even if the reference points to a value) */
    577        private final int hash;
    578
    579        SoftRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
    580            super(r, q);
    581            this.hash = hash;
    582        }
    583
    584        @Override
    585        public boolean equals(final Object obj) {
    586            if (this == obj) {
    587                return true;
    588            }
    589            if (obj == null) {
    590                return false;
    591            }
    592            if (getClass() != obj.getClass()) {
    593                return false;
    594            }
    595            final SoftRef<?> other = (SoftRef<?>) obj;
    596            return hash == other.hash;
    597        }
    598
    599        @Override
    600        public int hashCode() {
    601            return hash;
    602        }
    603    }
    604
    605    /**
    606     * A weak reference holder.
    607     */
    608    static class WeakRef<T> extends WeakReference<T> {
    609        /** The hashCode of the key (even if the reference points to a value) */
    610        private final int hash;
    611
    612        WeakRef(final int hash, final T r, final ReferenceQueue<? super T> q) {
    613            super(r, q);
    614            this.hash = hash;
    615        }
    616
    617        @Override
    618        public boolean equals(final Object obj) {
    619            if (this == obj) {
    620                return true;
    621            }
    622            if (obj == null) {
    623                return false;
    624            }
    625            if (getClass() != obj.getClass()) {
    626                return false;
    627            }
    628            final WeakRef<?> other = (WeakRef<?>) obj;
    629            return hash == other.hash;
    630        }
    631
    632        @Override
    633        public int hashCode() {
    634            return hash;
    635        }
    636    }
    637
    638    /**
    639     * The reference type for keys.
    640     */
    641    private ReferenceStrength keyType;
    642
    643    /**
    644     * The reference type for values.
    645     */
    646    private ReferenceStrength valueType;
    647
    648    /**
    649     * Should the value be automatically purged when the associated key has been collected?
    650     */
    651    private boolean purgeValues;
    652
    653    /**
    654     * ReferenceQueue used to eliminate stale mappings.
    655     * See purge.
    656     */
    657    private transient ReferenceQueue<Object> queue;
    658
    659    /**
    660     * Constructor used during deserialization.
    661     */
    662    protected AbstractReferenceMap() {
    663    }
    664
    665    /**
    666     * Constructs a new empty map with the specified reference types,
    667     * load factor and initial capacity.
    668     *
    669     * @param keyType  the type of reference to use for keys;
    670     *   must be {@link ReferenceStrength#HARD HARD},
    671     *   {@link ReferenceStrength#SOFT SOFT},
    672     *   {@link ReferenceStrength#WEAK WEAK}
    673     * @param valueType  the type of reference to use for values;
    674     *   must be {@link ReferenceStrength#HARD},
    675     *   {@link ReferenceStrength#SOFT SOFT},
    676     *   {@link ReferenceStrength#WEAK WEAK}
    677     * @param capacity  the initial capacity for the map
    678     * @param loadFactor  the load factor for the map
    679     * @param purgeValues  should the value be automatically purged when the
    680     *   key is garbage collected
    681     */
    682    protected AbstractReferenceMap(
    683            final ReferenceStrength keyType, final ReferenceStrength valueType, final int capacity,
    684            final float loadFactor, final boolean purgeValues) {
    685        super(capacity, loadFactor);
    686        this.keyType = keyType;
    687        this.valueType = valueType;
    688        this.purgeValues = purgeValues;
    689    }
    690
    691    /**
    692     * Clears this map.
    693     */
    694    @Override
    695    public void clear() {
    696        super.clear();
    697        // Drain the queue
    698        while (queue.poll() != null) { // NOPMD
    699        }
    700    }
    701
    702    /**
    703     * Checks whether the map contains the specified key.
    704     *
    705     * @param key  the key to search for
    706     * @return true if the map contains the key
    707     */
    708    @Override
    709    public boolean containsKey(final Object key) {
    710        purgeBeforeRead();
    711        final Entry<K, V> entry = getEntry(key);
    712        if (entry == null) {
    713            return false;
    714        }
    715        return entry.getValue() != null;
    716    }
    717
    718    /**
    719     * Checks whether the map contains the specified value.
    720     *
    721     * @param value  the value to search for
    722     * @return true if the map contains the value
    723     */
    724    @Override
    725    public boolean containsValue(final Object value) {
    726        purgeBeforeRead();
    727        if (value == null) {
    728            return false;
    729        }
    730        return super.containsValue(value);
    731    }
    732
    733    /**
    734     * Creates a ReferenceEntry instead of a HashEntry.
    735     *
    736     * @param next  the next entry in sequence
    737     * @param hashCode  the hash code to use
    738     * @param key  the key to store
    739     * @param value  the value to store
    740     * @return the newly created entry
    741     */
    742    @Override
    743    protected ReferenceEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode,
    744                                               final K key, final V value) {
    745        return new ReferenceEntry<>(this, next, hashCode, key, value);
    746    }
    747
    748    /**
    749     * Creates an entry set iterator.
    750     *
    751     * @return the entrySet iterator
    752     */
    753    @Override
    754    protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
    755        return new ReferenceEntrySetIterator<>(this);
    756    }
    757
    758    /**
    759     * Creates a key set iterator.
    760     *
    761     * @return the keySet iterator
    762     */
    763    @Override
    764    protected Iterator<K> createKeySetIterator() {
    765        return new ReferenceKeySetIterator<>(this);
    766    }
    767
    768    /**
    769     * Creates a values iterator.
    770     *
    771     * @return the values iterator
    772     */
    773    @Override
    774    protected Iterator<V> createValuesIterator() {
    775        return new ReferenceValuesIterator<>(this);
    776    }
    777
    778    /**
    779     * Replaces the superclass method to read the state of this class.
    780     * <p>
    781     * Serialization is not one of the JDK's nicest topics. Normal serialization will
    782     * initialize the superclass before the subclass. Sometimes however, this isn't
    783     * what you want, as in this case the {@code put()} method on read can be
    784     * affected by subclass state.
    785     * <p>
    786     * The solution adopted here is to deserialize the state data of this class in
    787     * this protected method. This method must be called by the
    788     * {@code readObject()} of the first serializable subclass.
    789     * <p>
    790     * Subclasses may override if the subclass has a specific field that must be present
    791     * before {@code put()} or {@code calculateThreshold()} will work correctly.
    792     *
    793     * @param in  the input stream
    794     * @throws IOException if an error occurs while reading from the stream
    795     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    796     */
    797    @Override
    798    @SuppressWarnings("unchecked")
    799    protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    800        this.keyType = ReferenceStrength.resolve(in.readInt());
    801        this.valueType = ReferenceStrength.resolve(in.readInt());
    802        this.purgeValues = in.readBoolean();
    803        this.loadFactor = in.readFloat();
    804        final int capacity = in.readInt();
    805        init();
    806        data = new HashEntry[capacity];
    807
    808        // COLLECTIONS-599: Calculate threshold before populating, otherwise it will be 0
    809        // when it hits AbstractHashedMap.checkCapacity() and so will unnecessarily
    810        // double up the size of the "data" array during population.
    811        //
    812        // NB: AbstractHashedMap.doReadObject() DOES calculate the threshold before populating.
    813        //
    814        threshold = calculateThreshold(data.length, loadFactor);
    815
    816        while (true) {
    817            final K key = (K) in.readObject();
    818            if (key == null) {
    819                break;
    820            }
    821            final V value = (V) in.readObject();
    822            put(key, value);
    823        }
    824        // do not call super.doReadObject() as code there doesn't work for reference map
    825    }
    826
    827    /**
    828     * Replaces the superclass method to store the state of this class.
    829     * <p>
    830     * Serialization is not one of the JDK's nicest topics. Normal serialization will
    831     * initialize the superclass before the subclass. Sometimes however, this isn't
    832     * what you want, as in this case the {@code put()} method on read can be
    833     * affected by subclass state.
    834     * <p>
    835     * The solution adopted here is to serialize the state data of this class in
    836     * this protected method. This method must be called by the
    837     * {@code writeObject()} of the first serializable subclass.
    838     * <p>
    839     * Subclasses may override if they have a specific field that must be present
    840     * on read before this implementation will work. Generally, the read determines
    841     * what must be serialized here, if anything.
    842     *
    843     * @param out  the output stream
    844     * @throws IOException if an error occurs while writing to the stream
    845     */
    846    @Override
    847    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    848        out.writeInt(keyType.value);
    849        out.writeInt(valueType.value);
    850        out.writeBoolean(purgeValues);
    851        out.writeFloat(loadFactor);
    852        out.writeInt(data.length);
    853        for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
    854            out.writeObject(it.next());
    855            out.writeObject(it.getValue());
    856        }
    857        out.writeObject(null);  // null terminate map
    858        // do not call super.doWriteObject() as code there doesn't work for reference map
    859    }
    860
    861    /**
    862     * Returns a set view of this map's entries.
    863     * An iterator returned entry is valid until {@code next()} is called again.
    864     * The {@code setValue()} method on the {@code toArray} entries has no effect.
    865     *
    866     * @return a set view of this map's entries
    867     */
    868    @Override
    869    public Set<Map.Entry<K, V>> entrySet() {
    870        if (entrySet == null) {
    871            entrySet = new ReferenceEntrySet<>(this);
    872        }
    873        return entrySet;
    874    }
    875
    876    /**
    877     * Gets the value mapped to the key specified.
    878     *
    879     * @param key  the key
    880     * @return the mapped value, null if no match
    881     */
    882    @Override
    883    public V get(final Object key) {
    884        purgeBeforeRead();
    885        final Entry<K, V> entry = getEntry(key);
    886        if (entry == null) {
    887            return null;
    888        }
    889        return entry.getValue();
    890    }
    891
    892    /**
    893     * Gets the entry mapped to the key specified.
    894     *
    895     * @param key  the key
    896     * @return the entry, null if no match
    897     */
    898    @Override
    899    protected HashEntry<K, V> getEntry(final Object key) {
    900        if (key == null) {
    901            return null;
    902        }
    903        return super.getEntry(key);
    904    }
    905
    906    /**
    907     * Gets the hash code for a MapEntry.
    908     * Subclasses can override this, for example to use the identityHashCode.
    909     *
    910     * @param key  the key to get a hash code for, may be null
    911     * @param value  the value to get a hash code for, may be null
    912     * @return the hash code, as per the MapEntry specification
    913     */
    914    protected int hashEntry(final Object key, final Object value) {
    915        return (key == null ? 0 : key.hashCode()) ^
    916               (value == null ? 0 : value.hashCode());
    917    }
    918
    919    /**
    920     * Initialize this subclass during construction, cloning or deserialization.
    921     */
    922    @Override
    923    protected void init() {
    924        queue = new ReferenceQueue<>();
    925    }
    926
    927    /**
    928     * Checks whether the map is currently empty.
    929     *
    930     * @return true if the map is currently size zero
    931     */
    932    @Override
    933    public boolean isEmpty() {
    934        purgeBeforeRead();
    935        return super.isEmpty();
    936    }
    937
    938    /**
    939     * Compares two keys, in internal converted form, to see if they are equal.
    940     * <p>
    941     * This implementation converts the key from the entry to a real reference
    942     * before comparison.
    943     *
    944     * @param key1  the first key to compare passed in from outside
    945     * @param key2  the second key extracted from the entry via {@code entry.key}
    946     * @return true if equal
    947     */
    948    @Override
    949    @SuppressWarnings("unchecked")
    950    protected boolean isEqualKey(final Object key1, Object key2) {
    951        key2 = keyType == ReferenceStrength.HARD ? key2 : ((Reference<K>) key2).get();
    952        return key1 == key2 || key1.equals(key2);
    953    }
    954
    955    /**
    956     * Provided protected read-only access to the key type.
    957     * @param type the type to check against.
    958     * @return true if keyType has the specified type
    959     */
    960    protected boolean isKeyType(final ReferenceStrength type) {
    961        return this.keyType == type;
    962    }
    963
    964    /**
    965     * Provided protected read-only access to the value type.
    966     * @param type the type to check against.
    967     * @return true if valueType has the specified type
    968     */
    969    protected boolean isValueType(final ReferenceStrength type) {
    970        return this.valueType == type;
    971    }
    972
    973    /**
    974     * Returns a set view of this map's keys.
    975     *
    976     * @return a set view of this map's keys
    977     */
    978    @Override
    979    public Set<K> keySet() {
    980        if (keySet == null) {
    981            keySet = new ReferenceKeySet<>(this);
    982        }
    983        return keySet;
    984    }
    985
    986    /**
    987     * Gets a MapIterator over the reference map.
    988     * The iterator only returns valid key/value pairs.
    989     *
    990     * @return a map iterator
    991     */
    992    @Override
    993    public MapIterator<K, V> mapIterator() {
    994        return new ReferenceMapIterator<>(this);
    995    }
    996
    997    /**
    998     * Purges stale mappings from this map.
    999     * <p>
    1000     * Note that this method is not synchronized!  Special
    1001     * care must be taken if, for instance, you want stale
    1002     * mappings to be removed on a periodic basis by some
    1003     * background thread.
    1004     */
    1005    protected void purge() {
    1006        Reference<?> ref = queue.poll();
    1007        while (ref != null) {
    1008            purge(ref);
    1009            ref = queue.poll();
    1010        }
    1011    }
    1012
    1013    /**
    1014     * Purges the specified reference.
    1015     *
    1016     * @param ref  the reference to purge
    1017     */
    1018    protected void purge(final Reference<?> ref) {
    1019        // The hashCode of the reference is the hashCode of the
    1020        // mapping key, even if the reference refers to the
    1021        // mapping value...
    1022        final int hash = ref.hashCode();
    1023        final int index = hashIndex(hash, data.length);
    1024        HashEntry<K, V> previous = null;
    1025        HashEntry<K, V> entry = data[index];
    1026        while (entry != null) {
    1027            final ReferenceEntry<K, V> refEntry = (ReferenceEntry<K, V>) entry;
    1028            if (refEntry.purge(ref)) {
    1029                if (previous == null) {
    1030                    data[index] = entry.next;
    1031                } else {
    1032                    previous.next = entry.next;
    1033                }
    1034                this.size--;
    1035                refEntry.onPurge();
    1036                return;
    1037            }
    1038            previous = entry;
    1039            entry = entry.next;
    1040        }
    1041
    1042    }
    1043
    1044    // These two classes store the hashCode of the key of
    1045    // the mapping, so that after they're dequeued a quick
    1046    // lookup of the bucket in the table can occur.
    1047
    1048    /**
    1049     * Purges stale mappings from this map before read operations.
    1050     * <p>
    1051     * This implementation calls {@link #purge()} to maintain a consistent state.
    1052     */
    1053    protected void purgeBeforeRead() {
    1054        purge();
    1055    }
    1056
    1057    /**
    1058     * Purges stale mappings from this map before write operations.
    1059     * <p>
    1060     * This implementation calls {@link #purge()} to maintain a consistent state.
    1061     */
    1062    protected void purgeBeforeWrite() {
    1063        purge();
    1064    }
    1065
    1066    /**
    1067     * Puts a key-value mapping into this map.
    1068     * Neither the key nor the value may be null.
    1069     *
    1070     * @param key  the key to add, must not be null
    1071     * @param value  the value to add, must not be null
    1072     * @return the value previously mapped to this key, null if none
    1073     * @throws NullPointerException if either the key or value is null
    1074     */
    1075    @Override
    1076    public V put(final K key, final V value) {
    1077        Objects.requireNonNull(key, "key");
    1078        Objects.requireNonNull(value, "value");
    1079        purgeBeforeWrite();
    1080        return super.put(key, value);
    1081    }
    1082
    1083    /**
    1084     * Removes the specified mapping from this map.
    1085     *
    1086     * @param key  the mapping to remove
    1087     * @return the value mapped to the removed key, null if key not in map
    1088     */
    1089    @Override
    1090    public V remove(final Object key) {
    1091        if (key == null) {
    1092            return null;
    1093        }
    1094        purgeBeforeWrite();
    1095        return super.remove(key);
    1096    }
    1097
    1098    /**
    1099     * Gets the size of the map.
    1100     *
    1101     * @return the size
    1102     */
    1103    @Override
    1104    public int size() {
    1105        purgeBeforeRead();
    1106        return super.size();
    1107    }
    1108
    1109    /**
    1110     * Returns a collection view of this map's values.
    1111     *
    1112     * @return a set view of this map's values
    1113     */
    1114    @Override
    1115    public Collection<V> values() {
    1116        if (values == null) {
    1117            values = new ReferenceValues<>(this);
    1118        }
    1119        return values;
    1120    }
    1121}