    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.io.Serializable;
    023import java.util.AbstractCollection;
    024import java.util.AbstractSet;
    025import java.util.Collection;
    026import java.util.Iterator;
    027import java.util.Map;
    028import java.util.NoSuchElementException;
    029import java.util.Objects;
    030import java.util.Set;
    031
    032import org.apache.commons.collections4.CollectionUtils;
    033import org.apache.commons.collections4.IterableMap;
    034import org.apache.commons.collections4.MapIterator;
    035import org.apache.commons.collections4.ResettableIterator;
    036import org.apache.commons.collections4.iterators.EmptyIterator;
    037import org.apache.commons.collections4.iterators.EmptyMapIterator;
    038
    039/**
    040 * A {@code Map} implementation that stores data in simple fields until
    041 * the size is greater than 3.
    042 * <p>
    043 * This map is designed for performance and can outstrip HashMap.
    044 * It also has good garbage collection characteristics.
    045 * </p>
    046 * <ul>
    047 * <li>Optimised for operation at size 3 or less.
    048 * <li>Still works well once size 3 exceeded.
    049 * <li>Gets at size 3 or less are about 0-10% faster than HashMap,
    050 * <li>Puts at size 3 or less are over 4 times faster than HashMap.
    051 * <li>Performance 5% slower than HashMap once size 3 exceeded once.
    052 * </ul>
    053 * <p>
    054 * The design uses two distinct modes of operation - flat and delegate.
    055 * While the map is size 3 or less, operations map straight onto fields using
    056 * switch statements. Once size 4 is reached, the map switches to delegate mode
    057 * and only switches back when cleared. In delegate mode, all operations are
    058 * forwarded straight to a HashMap resulting in the 5% performance loss.
    059 * </p>
    060 * <p>
    061 * The performance gains on puts are due to not needing to create a Map Entry
    062 * object. This is a large saving not only in performance but in garbage collection.
    063 * </p>
    064 * <p>
    065 * Whilst in flat mode this map is also easy for the garbage collector to dispatch.
    066 * This is because it contains no complex objects or arrays which slow the progress.
    067 * </p>
    068 * <p>
    069 * Do not use {@code Flat3Map} if the size is likely to grow beyond 3.
    070 * </p>
    071 * <p>
    072 * <strong>Note that Flat3Map is not synchronized and is not thread-safe.</strong>
    073 * If you wish to use this map from multiple threads concurrently, you must use
    074 * appropriate synchronization. The simplest approach is to wrap this map
    075 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
    076 * exceptions when accessed by concurrent threads without synchronization.
    077 * </p>
    078 *
    079 * @param <K> the type of the keys in this map
    080 * @param <V> the type of the values in this map
    081 * @since 3.0
    082 */
    083public class Flat3Map<K, V> implements IterableMap<K, V>, Serializable, Cloneable {
    084
    085    abstract static class EntryIterator<K, V> {
    086        private final Flat3Map<K, V> parent;
    087        private int nextIndex;
    088        private FlatMapEntry<K, V> currentEntry;
    089
    090        /**
    091         * Create a new Flat3Map.EntryIterator.
    092         */
    093        EntryIterator(final Flat3Map<K, V> parent) {
    094            this.parent = parent;
    095        }
    096
    097        public boolean hasNext() {
    098            return nextIndex < parent.size;
    099        }
    100
    101        public Map.Entry<K, V> nextEntry() {
    102            if (!hasNext()) {
    103                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
    104            }
    105            currentEntry = new FlatMapEntry<>(parent, ++nextIndex);
    106            return currentEntry;
    107        }
    108
    109        public void remove() {
    110            if (currentEntry == null) {
    111                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
    112            }
    113            parent.remove(currentEntry.getKey());
    114            currentEntry.setRemoved(true);
    115            nextIndex--;
    116            currentEntry = null;
    117        }
    118
    119    }
    120
    121    /**
    122     * EntrySet
    123     */
    124    static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
    125        private final Flat3Map<K, V> parent;
    126
    127        EntrySet(final Flat3Map<K, V> parent) {
    128            this.parent = parent;
    129        }
    130
    131        @Override
    132        public void clear() {
    133            parent.clear();
    134        }
    135
    136        @Override
    137        public Iterator<Map.Entry<K, V>> iterator() {
    138            if (parent.delegateMap != null) {
    139                return parent.delegateMap.entrySet().iterator();
    140            }
    141            if (parent.isEmpty()) {
    142                return EmptyIterator.<Map.Entry<K, V>>emptyIterator();
    143            }
    144            return new EntrySetIterator<>(parent);
    145        }
    146
    147        @Override
    148        public boolean remove(final Object obj) {
    149            if (!(obj instanceof Map.Entry)) {
    150                return false;
    151            }
    152            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
    153            final Object key = entry.getKey();
    154            final boolean result = parent.containsKey(key);
    155            parent.remove(key);
    156            return result;
    157        }
    158
    159        @Override
    160        public int size() {
    161            return parent.size();
    162        }
    163    }
    164    /**
    165     * EntrySetIterator and MapEntry
    166     */
    167    static class EntrySetIterator<K, V> extends EntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
    168        EntrySetIterator(final Flat3Map<K, V> parent) {
    169            super(parent);
    170        }
    171
    172        @Override
    173        public Map.Entry<K, V> next() {
    174            return nextEntry();
    175        }
    176    }
    177    static class FlatMapEntry<K, V> implements Map.Entry<K, V> {
    178        private final Flat3Map<K, V> parent;
    179        private final int index;
    180        private volatile boolean removed;
    181
    182        FlatMapEntry(final Flat3Map<K, V> parent, final int index) {
    183            this.parent = parent;
    184            this.index = index;
    185            this.removed = false;
    186        }
    187
    188        @Override
    189        public boolean equals(final Object obj) {
    190            if (removed) {
    191                return false;
    192            }
    193            if (!(obj instanceof Map.Entry)) {
    194                return false;
    195            }
    196            final Map.Entry<?, ?> other = (Map.Entry<?, ?>) obj;
    197            final Object key = getKey();
    198            final Object value = getValue();
    199            return (key == null ? other.getKey() == null : key.equals(other.getKey())) &&
    200                   (value == null ? other.getValue() == null : value.equals(other.getValue()));
    201        }
    202
    203        @Override
    204        public K getKey() {
    205            if (removed) {
    206                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
    207            }
    208            switch (index) {
    209            case 3:
    210                return parent.key3;
    211            case 2:
    212                return parent.key2;
    213            case 1:
    214                return parent.key1;
    215            }
    216            throw new IllegalStateException("Invalid map index: " + index);
    217        }
    218
    219        @Override
    220        public V getValue() {
    221            if (removed) {
    222                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
    223            }
    224            switch (index) {
    225            case 3:
    226                return parent.value3;
    227            case 2:
    228                return parent.value2;
    229            case 1:
    230                return parent.value1;
    231            }
    232            throw new IllegalStateException("Invalid map index: " + index);
    233        }
    234
    235        @Override
    236        public int hashCode() {
    237            if (removed) {
    238                return 0;
    239            }
    240            final Object key = getKey();
    241            final Object value = getValue();
    242            return (key == null ? 0 : key.hashCode()) ^
    243                   (value == null ? 0 : value.hashCode());
    244        }
    245
    246        /**
    247         * Used by the iterator that created this entry to indicate that
    248         * {@link java.util.Iterator#remove()} has been called.
    249         * <p>
    250         * As a consequence, all subsequent call to {@link #getKey()},
    251         * {@link #setValue(Object)} and {@link #getValue()} will fail.
    252         *
    253         * @param flag the new value of the removed flag
    254         */
    255        void setRemoved(final boolean flag) {
    256            this.removed = flag;
    257        }
    258
    259        @Override
    260        public V setValue(final V value) {
    261            if (removed) {
    262                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
    263            }
    264            final V old = getValue();
    265            switch (index) {
    266            case 3:
    267                parent.value3 = value;
    268                break;
    269            case 2:
    270                parent.value2 = value;
    271                break;
    272            case 1:
    273                parent.value1 = value;
    274                break;
    275            default:
    276                throw new IllegalStateException("Invalid map index: " + index);
    277            }
    278            return old;
    279        }
    280
    281        @Override
    282        public String toString() {
    283            if (!removed) {
    284                return getKey() + "=" + getValue();
    285            }
    286            return "";
    287        }
    288
    289    }
    290    /**
    291     * FlatMapIterator
    292     */
    293    static class FlatMapIterator<K, V> implements MapIterator<K, V>, ResettableIterator<K> {
    294        private final Flat3Map<K, V> parent;
    295        private int nextIndex;
    296        private boolean canRemove;
    297
    298        FlatMapIterator(final Flat3Map<K, V> parent) {
    299            this.parent = parent;
    300        }
    301
    302        @Override
    303        public K getKey() {
    304            if (!canRemove) {
    305                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
    306            }
    307            switch (nextIndex) {
    308            case 3:
    309                return parent.key3;
    310            case 2:
    311                return parent.key2;
    312            case 1:
    313                return parent.key1;
    314            }
    315            throw new IllegalStateException("Invalid map index: " + nextIndex);
    316        }
    317
    318        @Override
    319        public V getValue() {
    320            if (!canRemove) {
    321                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
    322            }
    323            switch (nextIndex) {
    324            case 3:
    325                return parent.value3;
    326            case 2:
    327                return parent.value2;
    328            case 1:
    329                return parent.value1;
    330            }
    331            throw new IllegalStateException("Invalid map index: " + nextIndex);
    332        }
    333
    334        @Override
    335        public boolean hasNext() {
    336            return nextIndex < parent.size;
    337        }
    338
    339        @Override
    340        public K next() {
    341            if (!hasNext()) {
    342                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
    343            }
    344            canRemove = true;
    345            nextIndex++;
    346            return getKey();
    347        }
    348
    349        @Override
    350        public void remove() {
    351            if (!canRemove) {
    352                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
    353            }
    354            parent.remove(getKey());
    355            nextIndex--;
    356            canRemove = false;
    357        }
    358
    359        @Override
    360        public void reset() {
    361            nextIndex = 0;
    362            canRemove = false;
    363        }
    364
    365        @Override
    366        public V setValue(final V value) {
    367            if (!canRemove) {
    368                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
    369            }
    370            final V old = getValue();
    371            switch (nextIndex) {
    372            case 3:
    373                parent.value3 = value;
    374                break;
    375            case 2:
    376                parent.value2 = value;
    377                break;
    378            case 1:
    379                parent.value1 = value;
    380                break;
    381            default:
    382                throw new IllegalStateException("Invalid map index: " + nextIndex);
    383            }
    384            return old;
    385        }
    386
    387        @Override
    388        public String toString() {
    389            if (canRemove) {
    390                return "Iterator[" + getKey() + "=" + getValue() + "]";
    391            }
    392            return "Iterator[]";
    393        }
    394    }
    395    /**
    396     * KeySet
    397     */
    398    static class KeySet<K> extends AbstractSet<K> {
    399        private final Flat3Map<K, ?> parent;
    400
    401        KeySet(final Flat3Map<K, ?> parent) {
    402            this.parent = parent;
    403        }
    404
    405        @Override
    406        public void clear() {
    407            parent.clear();
    408        }
    409
    410        @Override
    411        public boolean contains(final Object key) {
    412            return parent.containsKey(key);
    413        }
    414
    415        @Override
    416        public Iterator<K> iterator() {
    417            if (parent.delegateMap != null) {
    418                return parent.delegateMap.keySet().iterator();
    419            }
    420            if (parent.isEmpty()) {
    421                return EmptyIterator.<K>emptyIterator();
    422            }
    423            return new KeySetIterator<>(parent);
    424        }
    425
    426        @Override
    427        public boolean remove(final Object key) {
    428            final boolean result = parent.containsKey(key);
    429            parent.remove(key);
    430            return result;
    431        }
    432
    433        @Override
    434        public int size() {
    435            return parent.size();
    436        }
    437    }
    438    /**
    439     * KeySetIterator
    440     */
    441    static class KeySetIterator<K> extends EntryIterator<K, Object> implements Iterator<K> {
    442
    443        @SuppressWarnings("unchecked")
    444        KeySetIterator(final Flat3Map<K, ?> parent) {
    445            super((Flat3Map<K, Object>) parent);
    446        }
    447
    448        @Override
    449        public K next() {
    450            return nextEntry().getKey();
    451        }
    452    }
    453    /**
    454     * Values
    455     */
    456    static class Values<V> extends AbstractCollection<V> {
    457        private final Flat3Map<?, V> parent;
    458
    459        Values(final Flat3Map<?, V> parent) {
    460            this.parent = parent;
    461        }
    462
    463        @Override
    464        public void clear() {
    465            parent.clear();
    466        }
    467
    468        @Override
    469        public boolean contains(final Object value) {
    470            return parent.containsValue(value);
    471        }
    472
    473        @Override
    474        public Iterator<V> iterator() {
    475            if (parent.delegateMap != null) {
    476                return parent.delegateMap.values().iterator();
    477            }
    478            if (parent.isEmpty()) {
    479                return EmptyIterator.<V>emptyIterator();
    480            }
    481            return new ValuesIterator<>(parent);
    482        }
    483
    484        @Override
    485        public int size() {
    486            return parent.size();
    487        }
    488    }
    489    /**
    490     * ValuesIterator
    491     */
    492    static class ValuesIterator<V> extends EntryIterator<Object, V> implements Iterator<V> {
    493
    494        @SuppressWarnings("unchecked")
    495        ValuesIterator(final Flat3Map<?, V> parent) {
    496            super((Flat3Map<Object, V>) parent);
    497        }
    498
    499        @Override
    500        public V next() {
    501            return nextEntry().getValue();
    502        }
    503    }
    504    /** Serialization version */
    505    private static final long serialVersionUID = -6701087419741928296L;
    506    /** The size of the map, used while in flat mode */
    507    private transient int size;
    508    /** Hash, used while in flat mode */
    509    private transient int hash1;
    510
    511    /** Hash, used while in flat mode */
    512    private transient int hash2;
    513
    514    /** Hash, used while in flat mode */
    515    private transient int hash3;
    516
    517    /** Key, used while in flat mode */
    518    private transient K key1;
    519
    520    /** Key, used while in flat mode */
    521    private transient K key2;
    522
    523    /** Key, used while in flat mode */
    524    private transient K key3;
    525
    526    /** Value, used while in flat mode */
    527    private transient V value1;
    528
    529    /** Value, used while in flat mode */
    530    private transient V value2;
    531
    532    /** Value, used while in flat mode */
    533    private transient V value3;
    534
    535    /** Map, used while in delegate mode */
    536    private transient AbstractHashedMap<K, V> delegateMap;
    537
    538    /**
    539     * Constructs a new instance.
    540     */
    541    public Flat3Map() {
    542    }
    543
    544    /**
    545     * Constructor copying elements from another map.
    546     *
    547     * @param map  the map to copy
    548     * @throws NullPointerException if the map is null
    549     */
    550    public Flat3Map(final Map<? extends K, ? extends V> map) {
    551        putAll(map);
    552    }
    553
    554    /**
    555     * Clears the map, resetting the size to zero and nullifying references
    556     * to avoid garbage collection issues.
    557     */
    558    @Override
    559    public void clear() {
    560        if (delegateMap != null) {
    561            delegateMap.clear();  // should aid gc
    562            delegateMap = null;  // switch back to flat mode
    563        } else {
    564            size = 0;
    565            hash1 = hash2 = hash3 = 0;
    566            key1 = key2 = key3 = null;
    567            value1 = value2 = value3 = null;
    568        }
    569    }
    570
    571    /**
    572     * Clones the map without cloning the keys or values.
    573     *
    574     * @return a shallow clone
    575     * @since 3.1
    576     */
    577    @Override
    578    @SuppressWarnings("unchecked")
    579    public Flat3Map<K, V> clone() {
    580        try {
    581            final Flat3Map<K, V> cloned = (Flat3Map<K, V>) super.clone();
    582            if (cloned.delegateMap != null) {
    583                cloned.delegateMap = cloned.delegateMap.clone();
    584            }
    585            return cloned;
    586        } catch (final CloneNotSupportedException ex) {
    587            throw new UnsupportedOperationException(ex);
    588        }
    589    }
    590
    591    /**
    592     * Checks whether the map contains the specified key.
    593     *
    594     * @param key  the key to search for
    595     * @return true if the map contains the key
    596     */
    597    @Override
    598    public boolean containsKey(final Object key) {
    599        if (delegateMap != null) {
    600            return delegateMap.containsKey(key);
    601        }
    602        if (key == null) {
    603            switch (size) {  // drop through
    604            case 3:
    605                if (key3 == null) {
    606                    return true;
    607                }
    608            case 2:
    609                if (key2 == null) {
    610                    return true;
    611                }
    612            case 1:
    613                if (key1 == null) {
    614                    return true;
    615                }
    616            }
    617        } else {
    618            if (size > 0) {
    619                final int hashCode = key.hashCode();
    620                switch (size) {  // drop through
    621                case 3:
    622                    if (hash3 == hashCode && key.equals(key3)) {
    623                        return true;
    624                    }
    625                case 2:
    626                    if (hash2 == hashCode && key.equals(key2)) {
    627                        return true;
    628                    }
    629                case 1:
    630                    if (hash1 == hashCode && key.equals(key1)) {
    631                        return true;
    632                    }
    633                }
    634            }
    635        }
    636        return false;
    637    }
    638
    639    /**
    640     * Checks whether the map contains the specified value.
    641     *
    642     * @param value  the value to search for
    643     * @return true if the map contains the key
    644     */
    645    @Override
    646    public boolean containsValue(final Object value) {
    647        if (delegateMap != null) {
    648            return delegateMap.containsValue(value);
    649        }
    650        if (value == null) {  // drop through
    651            switch (size) {
    652            case 3:
    653                if (value3 == null) {
    654                    return true;
    655                }
    656            case 2:
    657                if (value2 == null) {
    658                    return true;
    659                }
    660            case 1:
    661                if (value1 == null) {
    662                    return true;
    663                }
    664            }
    665        } else {
    666            switch (size) {  // drop through
    667            case 3:
    668                if (value.equals(value3)) {
    669                    return true;
    670                }
    671            case 2:
    672                if (value.equals(value2)) {
    673                    return true;
    674                }
    675            case 1:
    676                if (value.equals(value1)) {
    677                    return true;
    678                }
    679            }
    680        }
    681        return false;
    682    }
    683
    684    /**
    685     * Converts the flat map data to a map.
    686     */
    687    private void convertToMap() {
    688        delegateMap = createDelegateMap();
    689        switch (size) {  // drop through
    690        case 3:
    691            delegateMap.put(key3, value3);
    692        case 2:
    693            delegateMap.put(key2, value2);
    694        case 1:
    695            delegateMap.put(key1, value1);
    696        case 0:
    697            break;
    698        default:
    699            throw new IllegalStateException("Invalid map index: " + size);
    700        }
    701
    702        size = 0;
    703        hash1 = hash2 = hash3 = 0;
    704        key1 = key2 = key3 = null;
    705        value1 = value2 = value3 = null;
    706    }
    707
    708    /**
    709     * Create an instance of the map used for storage when in delegation mode.
    710     * <p>
    711     * This can be overridden by subclasses to provide a different map implementation.
    712     * Not every AbstractHashedMap is suitable, identity and reference based maps
    713     * would be poor choices.
    714     *
    715     * @return a new AbstractHashedMap or subclass
    716     * @since 3.1
    717     */
    718    protected AbstractHashedMap<K, V> createDelegateMap() {
    719        return new HashedMap<>();
    720    }
    721
    722    /**
    723     * Gets the entrySet view of the map.
    724     * Changes made to the view affect this map.
    725     * <p>
    726     * NOTE: from 4.0, the returned Map Entry will be an independent object and will
    727     * not change anymore as the iterator progresses. To avoid this additional object
    728     * creation and simply iterate through the entries, use {@link #mapIterator()}.
    729     *
    730     * @return the entrySet view
    731     */
    732    @Override
    733    public Set<Map.Entry<K, V>> entrySet() {
    734        if (delegateMap != null) {
    735            return delegateMap.entrySet();
    736        }
    737        return new EntrySet<>(this);
    738    }
    739
    740    /**
    741     * Compares this map with another.
    742     *
    743     * @param obj  the object to compare to
    744     * @return true if equal
    745     */
    746    @Override
    747    public boolean equals(final Object obj) {
    748        if (obj == this) {
    749            return true;
    750        }
    751        if (delegateMap != null) {
    752            return delegateMap.equals(obj);
    753        }
    754        if (!(obj instanceof Map)) {
    755            return false;
    756        }
    757        final Map<?, ?> other = (Map<?, ?>) obj;
    758        if (size != other.size()) {
    759            return false;
    760        }
    761        if (size > 0) {
    762            Object otherValue = null;
    763            switch (size) {  // drop through
    764            case 3:
    765                if (!other.containsKey(key3)) {
    766                    return false;
    767                }
    768                otherValue = other.get(key3);
    769                if (!Objects.equals(value3, otherValue)) {
    770                    return false;
    771                }
    772            case 2:
    773                if (!other.containsKey(key2)) {
    774                    return false;
    775                }
    776                otherValue = other.get(key2);
    777                if (!Objects.equals(value2, otherValue)) {
    778                    return false;
    779                }
    780            case 1:
    781                if (!other.containsKey(key1)) {
    782                    return false;
    783                }
    784                otherValue = other.get(key1);
    785                if (!Objects.equals(value1, otherValue)) {
    786                    return false;
    787                }
    788            }
    789        }
    790        return true;
    791    }
    792
    793    /**
    794     * Gets the value mapped to the key specified.
    795     *
    796     * @param key  the key
    797     * @return the mapped value, null if no match
    798     */
    799    @Override
    800    public V get(final Object key) {
    801        if (delegateMap != null) {
    802            return delegateMap.get(key);
    803        }
    804        if (key == null) {
    805            switch (size) {
    806            // drop through
    807            case 3:
    808                if (key3 == null) {
    809                    return value3;
    810                }
    811            case 2:
    812                if (key2 == null) {
    813                    return value2;
    814                }
    815            case 1:
    816                if (key1 == null) {
    817                    return value1;
    818                }
    819            }
    820        } else {
    821            if (size > 0) {
    822                final int hashCode = key.hashCode();
    823                switch (size) {
    824                // drop through
    825                case 3:
    826                    if (hash3 == hashCode && key.equals(key3)) {
    827                        return value3;
    828                    }
    829                case 2:
    830                    if (hash2 == hashCode && key.equals(key2)) {
    831                        return value2;
    832                    }
    833                case 1:
    834                    if (hash1 == hashCode && key.equals(key1)) {
    835                        return value1;
    836                    }
    837                }
    838            }
    839        }
    840        return null;
    841    }
    842
    843    /**
    844     * Gets the standard Map hashCode.
    845     *
    846     * @return the hash code defined in the Map interface
    847     */
    848    @Override
    849    public int hashCode() {
    850        if (delegateMap != null) {
    851            return delegateMap.hashCode();
    852        }
    853        int total = 0;
    854        switch (size) {  // drop through
    855        case 3:
    856            total += hash3 ^ (value3 == null ? 0 : value3.hashCode());
    857        case 2:
    858            total += hash2 ^ (value2 == null ? 0 : value2.hashCode());
    859        case 1:
    860            total += hash1 ^ (value1 == null ? 0 : value1.hashCode());
    861        case 0:
    862            break;
    863        default:
    864            throw new IllegalStateException("Invalid map index: " + size);
    865        }
    866        return total;
    867    }
    868
    869    /**
    870     * Checks whether the map is currently empty.
    871     *
    872     * @return true if the map is currently size zero
    873     */
    874    @Override
    875    public boolean isEmpty() {
    876        return size() == 0;
    877    }
    878
    879    /**
    880     * Gets the keySet view of the map.
    881     * Changes made to the view affect this map.
    882     * To simply iterate through the keys, use {@link #mapIterator()}.
    883     *
    884     * @return the keySet view
    885     */
    886    @Override
    887    public Set<K> keySet() {
    888        if (delegateMap != null) {
    889            return delegateMap.keySet();
    890        }
    891        return new KeySet<>(this);
    892    }
    893
    894    /**
    895     * Gets an iterator over the map.
    896     * Changes made to the iterator affect this map.
    897     * <p>
    898     * A MapIterator returns the keys in the map. It also provides convenient
    899     * methods to get the key and value, and set the value.
    900     * It avoids the need to create an entrySet/keySet/values object.
    901     * It also avoids creating the Map Entry object.
    902     *
    903     * @return the map iterator
    904     */
    905    @Override
    906    public MapIterator<K, V> mapIterator() {
    907        if (delegateMap != null) {
    908            return delegateMap.mapIterator();
    909        }
    910        if (size == 0) {
    911            return EmptyMapIterator.<K, V>emptyMapIterator();
    912        }
    913        return new FlatMapIterator<>(this);
    914    }
    915
    916    /**
    917     * Puts a key-value mapping into this map.
    918     *
    919     * @param key  the key to add
    920     * @param value  the value to add
    921     * @return the value previously mapped to this key, null if none
    922     */
    923    @Override
    924    public V put(final K key, final V value) {
    925        if (delegateMap != null) {
    926            return delegateMap.put(key, value);
    927        }
    928        // change existing mapping
    929        if (key == null) {
    930            switch (size) {  // drop through
    931            case 3:
    932                if (key3 == null) {
    933                    final V old = value3;
    934                    value3 = value;
    935                    return old;
    936                }
    937            case 2:
    938                if (key2 == null) {
    939                    final V old = value2;
    940                    value2 = value;
    941                    return old;
    942                }
    943            case 1:
    944                if (key1 == null) {
    945                    final V old = value1;
    946                    value1 = value;
    947                    return old;
    948                }
    949            }
    950        } else {
    951            if (size > 0) {
    952                final int hashCode = key.hashCode();
    953                switch (size) {  // drop through
    954                case 3:
    955                    if (hash3 == hashCode && key.equals(key3)) {
    956                        final V old = value3;
    957                        value3 = value;
    958                        return old;
    959                    }
    960                case 2:
    961                    if (hash2 == hashCode && key.equals(key2)) {
    962                        final V old = value2;
    963                        value2 = value;
    964                        return old;
    965                    }
    966                case 1:
    967                    if (hash1 == hashCode && key.equals(key1)) {
    968                        final V old = value1;
    969                        value1 = value;
    970                        return old;
    971                    }
    972                }
    973            }
    974        }
    975
    976        // add new mapping
    977        switch (size) {
    978        default:
    979            convertToMap();
    980            delegateMap.put(key, value);
    981            return null;
    982        case 2:
    983            hash3 = key == null ? 0 : key.hashCode();
    984            key3 = key;
    985            value3 = value;
    986            break;
    987        case 1:
    988            hash2 = key == null ? 0 : key.hashCode();
    989            key2 = key;
    990            value2 = value;
    991            break;
    992        case 0:
    993            hash1 = key == null ? 0 : key.hashCode();
    994            key1 = key;
    995            value1 = value;
    996            break;
    997        }
    998        size++;
    999        return null;
    1000    }
    1001
    1002    /**
    1003     * Puts all the values from the specified map into this map.
    1004     *
    1005     * @param map  the map to add
    1006     * @throws NullPointerException if the map is null
    1007     */
    1008    @Override
    1009    public void putAll(final Map<? extends K, ? extends V> map) {
    1010        final int size = map.size();
    1011        if (size == 0) {
    1012            return;
    1013        }
    1014        if (delegateMap != null) {
    1015            delegateMap.putAll(map);
    1016            return;
    1017        }
    1018        if (size < 4) {
    1019            for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    1020                put(entry.getKey(), entry.getValue());
    1021            }
    1022        } else {
    1023            convertToMap();
    1024            delegateMap.putAll(map);
    1025        }
    1026    }
    1027
    1028    /**
    1029     * Read the map in using a custom routine.
    1030     *
    1031     * @param in the input stream
    1032     * @throws IOException if an error occurs while reading from the stream
    1033     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    1034     */
    1035    @SuppressWarnings("unchecked")
    1036    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    1037        in.defaultReadObject();
    1038        final int count = in.readInt();
    1039        if (count > 3) {
    1040            delegateMap = createDelegateMap();
    1041        }
    1042        for (int i = count; i > 0; i--) {
    1043            put((K) in.readObject(), (V) in.readObject());
    1044        }
    1045    }
    1046
    1047    /**
    1048     * Removes the specified mapping from this map.
    1049     *
    1050     * @param key  the mapping to remove
    1051     * @return the value mapped to the removed key, null if key not in map
    1052     */
    1053    @Override
    1054    public V remove(final Object key) {
    1055        if (delegateMap != null) {
    1056            return delegateMap.remove(key);
    1057        }
    1058        if (size == 0) {
    1059            return null;
    1060        }
    1061        if (key == null) {
    1062            switch (size) {  // drop through
    1063            case 3:
    1064                if (key3 == null) {
    1065                    final V old = value3;
    1066                    hash3 = 0;
    1067                    key3 = null;
    1068                    value3 = null;
    1069                    size = 2;
    1070                    return old;
    1071                }
    1072                if (key2 == null) {
    1073                    final V old = value2;
    1074                    hash2 = hash3;
    1075                    key2 = key3;
    1076                    value2 = value3;
    1077                    hash3 = 0;
    1078                    key3 = null;
    1079                    value3 = null;
    1080                    size = 2;
    1081                    return old;
    1082                }
    1083                if (key1 == null) {
    1084                    final V old = value1;
    1085                    hash1 = hash3;
    1086                    key1 = key3;
    1087                    value1 = value3;
    1088                    hash3 = 0;
    1089                    key3 = null;
    1090                    value3 = null;
    1091                    size = 2;
    1092                    return old;
    1093                }
    1094                return null;
    1095            case 2:
    1096                if (key2 == null) {
    1097                    final V old = value2;
    1098                    hash2 = 0;
    1099                    key2 = null;
    1100                    value2 = null;
    1101                    size = 1;
    1102                    return old;
    1103                }
    1104                if (key1 == null) {
    1105                    final V old = value1;
    1106                    hash1 = hash2;
    1107                    key1 = key2;
    1108                    value1 = value2;
    1109                    hash2 = 0;
    1110                    key2 = null;
    1111                    value2 = null;
    1112                    size = 1;
    1113                    return old;
    1114                }
    1115                return null;
    1116            case 1:
    1117                if (key1 == null) {
    1118                    final V old = value1;
    1119                    hash1 = 0;
    1120                    key1 = null;
    1121                    value1 = null;
    1122                    size = 0;
    1123                    return old;
    1124                }
    1125            }
    1126        } else {
    1127            if (size > 0) {
    1128                final int hashCode = key.hashCode();
    1129                switch (size) {  // drop through
    1130                case 3:
    1131                    if (hash3 == hashCode && key.equals(key3)) {
    1132                        final V old = value3;
    1133                        hash3 = 0;
    1134                        key3 = null;
    1135                        value3 = null;
    1136                        size = 2;
    1137                        return old;
    1138                    }
    1139                    if (hash2 == hashCode && key.equals(key2)) {
    1140                        final V old = value2;
    1141                        hash2 = hash3;
    1142                        key2 = key3;
    1143                        value2 = value3;
    1144                        hash3 = 0;
    1145                        key3 = null;
    1146                        value3 = null;
    1147                        size = 2;
    1148                        return old;
    1149                    }
    1150                    if (hash1 == hashCode && key.equals(key1)) {
    1151                        final V old = value1;
    1152                        hash1 = hash3;
    1153                        key1 = key3;
    1154                        value1 = value3;
    1155                        hash3 = 0;
    1156                        key3 = null;
    1157                        value3 = null;
    1158                        size = 2;
    1159                        return old;
    1160                    }
    1161                    return null;
    1162                case 2:
    1163                    if (hash2 == hashCode && key.equals(key2)) {
    1164                        final V old = value2;
    1165                        hash2 = 0;
    1166                        key2 = null;
    1167                        value2 = null;
    1168                        size = 1;
    1169                        return old;
    1170                    }
    1171                    if (hash1 == hashCode && key.equals(key1)) {
    1172                        final V old = value1;
    1173                        hash1 = hash2;
    1174                        key1 = key2;
    1175                        value1 = value2;
    1176                        hash2 = 0;
    1177                        key2 = null;
    1178                        value2 = null;
    1179                        size = 1;
    1180                        return old;
    1181                    }
    1182                    return null;
    1183                case 1:
    1184                    if (hash1 == hashCode && key.equals(key1)) {
    1185                        final V old = value1;
    1186                        hash1 = 0;
    1187                        key1 = null;
    1188                        value1 = null;
    1189                        size = 0;
    1190                        return old;
    1191                    }
    1192                }
    1193            }
    1194        }
    1195        return null;
    1196    }
    1197
    1198    /**
    1199     * Gets the size of the map.
    1200     *
    1201     * @return the size
    1202     */
    1203    @Override
    1204    public int size() {
    1205        if (delegateMap != null) {
    1206            return delegateMap.size();
    1207        }
    1208        return size;
    1209    }
    1210
    1211    /**
    1212     * Gets the map as a String.
    1213     *
    1214     * @return a string version of the map
    1215     */
    1216    @Override
    1217    public String toString() {
    1218        if (delegateMap != null) {
    1219            return delegateMap.toString();
    1220        }
    1221        if (size == 0) {
    1222            return "{}";
    1223        }
    1224        final StringBuilder buf = new StringBuilder(128);
    1225        buf.append('{');
    1226        switch (size) {  // drop through
    1227        case 3:
    1228            buf.append(key3 == this ? "(this Map)" : key3);
    1229            buf.append('=');
    1230            buf.append(value3 == this ? "(this Map)" : value3);
    1231            buf.append(CollectionUtils.COMMA);
    1232        case 2:
    1233            buf.append(key2 == this ? "(this Map)" : key2);
    1234            buf.append('=');
    1235            buf.append(value2 == this ? "(this Map)" : value2);
    1236            buf.append(CollectionUtils.COMMA);
    1237        case 1:
    1238            buf.append(key1 == this ? "(this Map)" : key1);
    1239            buf.append('=');
    1240            buf.append(value1 == this ? "(this Map)" : value1);
    1241            break;
    1242        // case 0: has already been dealt with
    1243        default:
    1244            throw new IllegalStateException("Invalid map index: " + size);
    1245        }
    1246        buf.append('}');
    1247        return buf.toString();
    1248    }
    1249
    1250    /**
    1251     * Gets the values view of the map.
    1252     * Changes made to the view affect this map.
    1253     * To simply iterate through the values, use {@link #mapIterator()}.
    1254     *
    1255     * @return the values view
    1256     */
    1257    @Override
    1258    public Collection<V> values() {
    1259        if (delegateMap != null) {
    1260            return delegateMap.values();
    1261        }
    1262        return new Values<>(this);
    1263    }
    1264
    1265    /**
    1266     * Write the map out using a custom routine.
    1267     *
    1268     * @param out  the output stream
    1269     * @throws IOException if an error occurs while writing to the stream
    1270     */
    1271    private void writeObject(final ObjectOutputStream out) throws IOException {
    1272        out.defaultWriteObject();
    1273        out.writeInt(size());
    1274        for (final MapIterator<?, ?> it = mapIterator(); it.hasNext();) {
    1275            out.writeObject(it.next());  // key
    1276            out.writeObject(it.getValue());  // value
    1277        }
    1278    }
    1279
    1280}