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