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