    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.Map;
    024import java.util.Objects;
    025
    026import org.apache.commons.collections4.MapIterator;
    027import org.apache.commons.collections4.keyvalue.MultiKey;
    028import org.apache.commons.collections4.map.AbstractHashedMap.HashEntry;
    029
    030/**
    031 * A {@code Map} implementation that uses multiple keys to map the value.
    032 * <p>
    033 * This class is the most efficient way to uses multiple keys to map to a value.
    034 * The best way to use this class is via the additional map-style methods.
    035 * These provide {@code get}, {@code containsKey}, {@code put} and
    036 * {@code remove} for individual keys which operate without extra object creation.
    037 * </p>
    038 * <p>
    039 * The additional methods are the main interface of this map.
    040 * As such, you will not normally hold this map in a variable of type {@code Map}.
    041 * </p>
    042 * <p>
    043 * The normal map methods take in and return a {@link MultiKey}.
    044 * If you try to use {@code put()} with any other object type a
    045 * {@code ClassCastException} is thrown. If you try to use {@code null} as
    046 * the key in {@code put()} a {@code NullPointerException} is thrown.
    047 * </p>
    048 * <p>
    049 * This map is implemented as a decorator of a {@code AbstractHashedMap} which
    050 * enables extra behavior to be added easily.
    051 * </p>
    052 * <ul>
    053 * <li>{@code MultiKeyMap.decorate(new LinkedMap())} creates an ordered map.
    054 * <li>{@code MultiKeyMap.decorate(new LRUMap())} creates an least recently used map.
    055 * <li>{@code MultiKeyMap.decorate(new ReferenceMap())} creates a garbage collector sensitive map.
    056 * </ul>
    057 * <p>
    058 * Note that {@code IdentityMap} and {@code ReferenceIdentityMap} are unsuitable
    059 * for use as the key comparison would work on the whole MultiKey, not the elements within.
    060 * </p>
    061 * <p>
    062 * As an example, consider a least recently used cache that uses a String airline code
    063 * and a Locale to lookup the airline's name:
    064 * </p>
    065 * <pre>
    066 * private MultiKeyMap cache = MultiKeyMap.multiKeyMap(new LRUMap(50));
    067 *
    068 * public String getAirlineName(String code, String locale) {
    069 *   String name = (String) cache.get(code, locale);
    070 *   if (name == null) {
    071 *     name = getAirlineNameFromDB(code, locale);
    072 *     cache.put(code, locale, name);
    073 *   }
    074 *   return name;
    075 * }
    076 * </pre>
    077 * <p>
    078 * <strong>Note that MultiKeyMap is not synchronized and is not thread-safe.</strong>
    079 * If you wish to use this map from multiple threads concurrently, you must use
    080 * appropriate synchronization. This class may throw exceptions when accessed
    081 * by concurrent threads without synchronization.
    082 * </p>
    083 *
    084 * @param <K> the type of the keys in this map
    085 * @param <V> the type of the values in this map
    086 * @since 3.1
    087 */
    088public class MultiKeyMap<K, V> extends AbstractMapDecorator<MultiKey<? extends K>, V>
    089        implements Serializable, Cloneable {
    090
    091    /** Serialization version */
    092    private static final long serialVersionUID = -1788199231038721040L;
    093
    094    /**
    095     * Decorates the specified map to add the MultiKeyMap API and fast query.
    096     * The map must not be null and must be empty.
    097     *
    098     * @param <K>  the key type
    099     * @param <V>  the value type
    100     * @param map  the map to decorate, not null
    101     * @return a new multi key map
    102     * @throws NullPointerException if map is null
    103     * @throws IllegalArgumentException if the map is not empty
    104     * @since 4.0
    105     */
    106    public static <K, V> MultiKeyMap<K, V> multiKeyMap(final AbstractHashedMap<MultiKey<? extends K>, V> map) {
    107        Objects.requireNonNull(map, "map");
    108        if (map.isEmpty()) {
    109            return new MultiKeyMap<>(map);
    110        }
    111        throw new IllegalArgumentException("Map must be empty");
    112    }
    113
    114    /**
    115     * Constructs a new MultiKeyMap that decorates a {@code HashedMap}.
    116     */
    117    public MultiKeyMap() {
    118        this(new HashedMap<>());
    119    }
    120
    121    /**
    122     * Constructor that decorates the specified map and is called from
    123     * {@link #multiKeyMap(AbstractHashedMap)}.
    124     * The map must not be null and should be empty or only contain valid keys.
    125     * This constructor performs no validation.
    126     *
    127     * @param map  the map to decorate
    128     */
    129    protected MultiKeyMap(final AbstractHashedMap<MultiKey<? extends K>, V> map) {
    130        super(map);
    131        this.map = map;
    132    }
    133
    134    /**
    135     * Check to ensure that input keys are valid MultiKey objects.
    136     *
    137     * @param key  the key to check
    138     */
    139    protected void checkKey(final MultiKey<?> key) {
    140        Objects.requireNonNull(key, "key");
    141    }
    142
    143    /**
    144     * Clones the map without cloning the keys or values.
    145     *
    146     * @return a shallow clone
    147     */
    148    @SuppressWarnings("unchecked")
    149    @Override
    150    public MultiKeyMap<K, V> clone() {
    151        try {
    152            return (MultiKeyMap<K, V>) super.clone();
    153        } catch (final CloneNotSupportedException e) {
    154            throw new UnsupportedOperationException(e);
    155        }
    156    }
    157
    158    /**
    159     * Checks whether the map contains the specified multi-key.
    160     *
    161     * @param key1  the first key
    162     * @param key2  the second key
    163     * @return true if the map contains the key
    164     */
    165    public boolean containsKey(final Object key1, final Object key2) {
    166        final int hashCode = hash(key1, key2);
    167        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    168        while (entry != null) {
    169            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    170                return true;
    171            }
    172            entry = entry.next;
    173        }
    174        return false;
    175    }
    176
    177    /**
    178     * Checks whether the map contains the specified multi-key.
    179     *
    180     * @param key1  the first key
    181     * @param key2  the second key
    182     * @param key3  the third key
    183     * @return true if the map contains the key
    184     */
    185    public boolean containsKey(final Object key1, final Object key2, final Object key3) {
    186        final int hashCode = hash(key1, key2, key3);
    187        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    188        while (entry != null) {
    189            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    190                return true;
    191            }
    192            entry = entry.next;
    193        }
    194        return false;
    195    }
    196
    197    /**
    198     * Checks whether the map contains the specified multi-key.
    199     *
    200     * @param key1  the first key
    201     * @param key2  the second key
    202     * @param key3  the third key
    203     * @param key4  the fourth key
    204     * @return true if the map contains the key
    205     */
    206    public boolean containsKey(final Object key1, final Object key2, final Object key3, final Object key4) {
    207        final int hashCode = hash(key1, key2, key3, key4);
    208        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    209        while (entry != null) {
    210            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    211                return true;
    212            }
    213            entry = entry.next;
    214        }
    215        return false;
    216    }
    217
    218    /**
    219     * Checks whether the map contains the specified multi-key.
    220     *
    221     * @param key1  the first key
    222     * @param key2  the second key
    223     * @param key3  the third key
    224     * @param key4  the fourth key
    225     * @param key5  the fifth key
    226     * @return true if the map contains the key
    227     */
    228    public boolean containsKey(final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    229        final int hashCode = hash(key1, key2, key3, key4, key5);
    230        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    231        while (entry != null) {
    232            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    233                return true;
    234            }
    235            entry = entry.next;
    236        }
    237        return false;
    238    }
    239
    240    /**
    241     * {@inheritDoc}
    242     */
    243    @Override
    244    protected AbstractHashedMap<MultiKey<? extends K>, V> decorated() {
    245        return (AbstractHashedMap<MultiKey<? extends K>, V>) super.decorated();
    246    }
    247
    248    HashEntry<MultiKey<? extends K>, V> decoratedHashEntry(final int hashCode) {
    249        return decorated().data[decoratedHashIndex(hashCode)];
    250    }
    251
    252    int decoratedHashIndex(final int hashCode) {
    253        return decorated().hashIndex(hashCode, decorated().data.length);
    254    }
    255
    256    /**
    257     * Gets the value mapped to the specified multi-key.
    258     *
    259     * @param key1  the first key
    260     * @param key2  the second key
    261     * @return the mapped value, null if no match
    262     */
    263    public V get(final Object key1, final Object key2) {
    264        final int hashCode = hash(key1, key2);
    265        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    266        while (entry != null) {
    267            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    268                return entry.getValue();
    269            }
    270            entry = entry.next;
    271        }
    272        return null;
    273    }
    274
    275    /**
    276     * Gets the value mapped to the specified multi-key.
    277     *
    278     * @param key1  the first key
    279     * @param key2  the second key
    280     * @param key3  the third key
    281     * @return the mapped value, null if no match
    282     */
    283    public V get(final Object key1, final Object key2, final Object key3) {
    284        final int hashCode = hash(key1, key2, key3);
    285        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    286        while (entry != null) {
    287            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    288                return entry.getValue();
    289            }
    290            entry = entry.next;
    291        }
    292        return null;
    293    }
    294
    295    /**
    296     * Gets the value mapped to the specified multi-key.
    297     *
    298     * @param key1  the first key
    299     * @param key2  the second key
    300     * @param key3  the third key
    301     * @param key4  the fourth key
    302     * @return the mapped value, null if no match
    303     */
    304    public V get(final Object key1, final Object key2, final Object key3, final Object key4) {
    305        final int hashCode = hash(key1, key2, key3, key4);
    306        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    307        while (entry != null) {
    308            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    309                return entry.getValue();
    310            }
    311            entry = entry.next;
    312        }
    313        return null;
    314    }
    315
    316    /**
    317     * Gets the value mapped to the specified multi-key.
    318     *
    319     * @param key1  the first key
    320     * @param key2  the second key
    321     * @param key3  the third key
    322     * @param key4  the fourth key
    323     * @param key5  the fifth key
    324     * @return the mapped value, null if no match
    325     */
    326    public V get(final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    327        final int hashCode = hash(key1, key2, key3, key4, key5);
    328        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decoratedHashEntry(hashCode);
    329        while (entry != null) {
    330            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    331                return entry.getValue();
    332            }
    333            entry = entry.next;
    334        }
    335        return null;
    336    }
    337
    338    /**
    339     * Gets the hash code for the specified multi-key.
    340     *
    341     * @param key1  the first key
    342     * @param key2  the second key
    343     * @return the hash code
    344     */
    345    protected int hash(final Object key1, final Object key2) {
    346        int h = 0;
    347        if (key1 != null) {
    348            h ^= key1.hashCode();
    349        }
    350        if (key2 != null) {
    351            h ^= key2.hashCode();
    352        }
    353        h += ~(h << 9);
    354        h ^=  h >>> 14;
    355        h +=  h << 4;
    356        h ^=  h >>> 10;
    357        return h;
    358    }
    359
    360    /**
    361     * Gets the hash code for the specified multi-key.
    362     *
    363     * @param key1  the first key
    364     * @param key2  the second key
    365     * @param key3  the third key
    366     * @return the hash code
    367     */
    368    protected int hash(final Object key1, final Object key2, final Object key3) {
    369        int h = 0;
    370        if (key1 != null) {
    371            h ^= key1.hashCode();
    372        }
    373        if (key2 != null) {
    374            h ^= key2.hashCode();
    375        }
    376        if (key3 != null) {
    377            h ^= key3.hashCode();
    378        }
    379        h += ~(h << 9);
    380        h ^=  h >>> 14;
    381        h +=  h << 4;
    382        h ^=  h >>> 10;
    383        return h;
    384    }
    385
    386    /**
    387     * Gets the hash code for the specified multi-key.
    388     *
    389     * @param key1  the first key
    390     * @param key2  the second key
    391     * @param key3  the third key
    392     * @param key4  the fourth key
    393     * @return the hash code
    394     */
    395    protected int hash(final Object key1, final Object key2, final Object key3, final Object key4) {
    396        int h = 0;
    397        if (key1 != null) {
    398            h ^= key1.hashCode();
    399        }
    400        if (key2 != null) {
    401            h ^= key2.hashCode();
    402        }
    403        if (key3 != null) {
    404            h ^= key3.hashCode();
    405        }
    406        if (key4 != null) {
    407            h ^= key4.hashCode();
    408        }
    409        h += ~(h << 9);
    410        h ^=  h >>> 14;
    411        h +=  h << 4;
    412        h ^=  h >>> 10;
    413        return h;
    414    }
    415
    416    /**
    417     * Gets the hash code for the specified multi-key.
    418     *
    419     * @param key1  the first key
    420     * @param key2  the second key
    421     * @param key3  the third key
    422     * @param key4  the fourth key
    423     * @param key5  the fifth key
    424     * @return the hash code
    425     */
    426    protected int hash(final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    427        int h = 0;
    428        if (key1 != null) {
    429            h ^= key1.hashCode();
    430        }
    431        if (key2 != null) {
    432            h ^= key2.hashCode();
    433        }
    434        if (key3 != null) {
    435            h ^= key3.hashCode();
    436        }
    437        if (key4 != null) {
    438            h ^= key4.hashCode();
    439        }
    440        if (key5 != null) {
    441            h ^= key5.hashCode();
    442        }
    443        h += ~(h << 9);
    444        h ^=  h >>> 14;
    445        h +=  h << 4;
    446        h ^=  h >>> 10;
    447        return h;
    448    }
    449
    450    /**
    451     * Is the key equal to the combined key.
    452     *
    453     * @param entry  the entry to compare to
    454     * @param key1  the first key
    455     * @param key2  the second key
    456     * @return true if the key matches
    457     */
    458    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    459            final Object key1, final Object key2) {
    460        final MultiKey<? extends K> multi = entry.getKey();
    461        return
    462            multi.size() == 2 &&
    463            Objects.equals(key1, multi.getKey(0)) &&
    464            Objects.equals(key2, multi.getKey(1));
    465    }
    466
    467    /**
    468     * Is the key equal to the combined key.
    469     *
    470     * @param entry  the entry to compare to
    471     * @param key1  the first key
    472     * @param key2  the second key
    473     * @param key3  the third key
    474     * @return true if the key matches
    475     */
    476    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    477                                 final Object key1, final Object key2, final Object key3) {
    478        final MultiKey<? extends K> multi = entry.getKey();
    479        return
    480            multi.size() == 3 &&
    481            Objects.equals(key1, multi.getKey(0)) &&
    482            Objects.equals(key2, multi.getKey(1)) &&
    483            Objects.equals(key3, multi.getKey(2));
    484    }
    485
    486    /**
    487     * Is the key equal to the combined key.
    488     *
    489     * @param entry  the entry to compare to
    490     * @param key1  the first key
    491     * @param key2  the second key
    492     * @param key3  the third key
    493     * @param key4  the fourth key
    494     * @return true if the key matches
    495     */
    496    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    497                                 final Object key1, final Object key2, final Object key3, final Object key4) {
    498        final MultiKey<? extends K> multi = entry.getKey();
    499        return
    500            multi.size() == 4 &&
    501            Objects.equals(key1, multi.getKey(0)) &&
    502            Objects.equals(key2, multi.getKey(1)) &&
    503            Objects.equals(key3, multi.getKey(2)) &&
    504            Objects.equals(key4, multi.getKey(3));
    505    }
    506
    507    /**
    508     * Is the key equal to the combined key.
    509     *
    510     * @param entry  the entry to compare to
    511     * @param key1  the first key
    512     * @param key2  the second key
    513     * @param key3  the third key
    514     * @param key4  the fourth key
    515     * @param key5  the fifth key
    516     * @return true if the key matches
    517     */
    518    protected boolean isEqualKey(final AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry,
    519            final Object key1, final Object key2, final Object key3, final Object key4, final Object key5) {
    520        final MultiKey<? extends K> multi = entry.getKey();
    521        return
    522            multi.size() == 5 &&
    523            Objects.equals(key1, multi.getKey(0)) &&
    524            Objects.equals(key2, multi.getKey(1)) &&
    525            Objects.equals(key3, multi.getKey(2)) &&
    526            Objects.equals(key4, multi.getKey(3)) &&
    527            Objects.equals(key5, multi.getKey(4));
    528    }
    529
    530    @Override
    531    public MapIterator<MultiKey<? extends K>, V> mapIterator() {
    532        return decorated().mapIterator();
    533    }
    534
    535    /**
    536     * Associates the specified value with the specified keys in this map.
    537     *
    538     * @param key1  the first key
    539     * @param key2  the second key
    540     * @param key3  the third key
    541     * @param key4  the fourth key
    542     * @param key5  the fifth key
    543     * @param value  the value to store
    544     * @return the value previously mapped to this combined key, null if none
    545     */
    546    public V put(final K key1, final K key2, final K key3, final K key4, final K key5, final V value) {
    547        final int hashCode = hash(key1, key2, key3, key4, key5);
    548        final int index = decoratedHashIndex(hashCode);
    549        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    550        while (entry != null) {
    551            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    552                final V oldValue = entry.getValue();
    553                decorated().updateEntry(entry, value);
    554                return oldValue;
    555            }
    556            entry = entry.next;
    557        }
    558        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3, key4, key5), value);
    559        return null;
    560    }
    561
    562    /**
    563     * Associates the specified value with the specified keys in this map.
    564     *
    565     * @param key1  the first key
    566     * @param key2  the second key
    567     * @param key3  the third key
    568     * @param key4  the fourth key
    569     * @param value  the value to store
    570     * @return the value previously mapped to this combined key, null if none
    571     */
    572    public V put(final K key1, final K key2, final K key3, final K key4, final V value) {
    573        final int hashCode = hash(key1, key2, key3, key4);
    574        final int index = decoratedHashIndex(hashCode);
    575        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    576        while (entry != null) {
    577            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    578                final V oldValue = entry.getValue();
    579                decorated().updateEntry(entry, value);
    580                return oldValue;
    581            }
    582            entry = entry.next;
    583        }
    584        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3, key4), value);
    585        return null;
    586    }
    587
    588    /**
    589     * Associates the specified value with the specified keys in this map.
    590     *
    591     * @param key1  the first key
    592     * @param key2  the second key
    593     * @param key3  the third key
    594     * @param value  the value to store
    595     * @return the value previously mapped to this combined key, null if none
    596     */
    597    public V put(final K key1, final K key2, final K key3, final V value) {
    598        final int hashCode = hash(key1, key2, key3);
    599        final int index = decoratedHashIndex(hashCode);
    600        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    601        while (entry != null) {
    602            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    603                final V oldValue = entry.getValue();
    604                decorated().updateEntry(entry, value);
    605                return oldValue;
    606            }
    607            entry = entry.next;
    608        }
    609        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2, key3), value);
    610        return null;
    611    }
    612
    613    /**
    614     * Associates the specified value with the specified keys in this map.
    615     *
    616     * @param key1  the first key
    617     * @param key2  the second key
    618     * @param value  the value to store
    619     * @return the value previously mapped to this combined key, null if none
    620     */
    621    public V put(final K key1, final K key2, final V value) {
    622        final int hashCode = hash(key1, key2);
    623        final int index = decoratedHashIndex(hashCode);
    624        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    625        while (entry != null) {
    626            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    627                final V oldValue = entry.getValue();
    628                decorated().updateEntry(entry, value);
    629                return oldValue;
    630            }
    631            entry = entry.next;
    632        }
    633        decorated().addMapping(index, hashCode, new MultiKey<>(key1, key2), value);
    634        return null;
    635    }
    636
    637    /**
    638     * Puts the key and value into the map, where the key must be a non-null
    639     * MultiKey object.
    640     *
    641     * @param key  the non-null MultiKey object
    642     * @param value  the value to store
    643     * @return the previous value for the key
    644     * @throws NullPointerException if the key is null
    645     * @throws ClassCastException if the key is not a MultiKey
    646     */
    647    @Override
    648    public V put(final MultiKey<? extends K> key, final V value) {
    649        checkKey(key);
    650        return super.put(key, value);
    651    }
    652
    653    /**
    654     * Copies all of the keys and values from the specified map to this map.
    655     * Each key must be non-null and a MultiKey object.
    656     *
    657     * @param mapToCopy  to this map
    658     * @throws NullPointerException if the mapToCopy or any key within is null
    659     * @throws ClassCastException if any key in mapToCopy is not a MultiKey
    660     */
    661    @Override
    662    public void putAll(final Map<? extends MultiKey<? extends K>, ? extends V> mapToCopy) {
    663        for (final MultiKey<? extends K> key : mapToCopy.keySet()) {
    664            checkKey(key);
    665        }
    666        super.putAll(mapToCopy);
    667    }
    668
    669    /**
    670     * Deserializes the map in using a custom routine.
    671     *
    672     * @param in  the input stream
    673     * @throws IOException if an error occurs while reading from the stream
    674     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
    675     */
    676    @SuppressWarnings("unchecked")
    677    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    678        in.defaultReadObject();
    679        map = (Map<MultiKey<? extends K>, V>) in.readObject();
    680    }
    681
    682    /**
    683     * Removes all mappings where the first key is that specified.
    684     * <p>
    685     * This method removes all the mappings where the {@code MultiKey}
    686     * has one or more keys, and the first matches that specified.
    687     * </p>
    688     *
    689     * @param key1  the first key
    690     * @return true if any elements were removed
    691     */
    692    public boolean removeAll(final Object key1) {
    693        boolean modified = false;
    694        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    695        while (it.hasNext()) {
    696            final MultiKey<? extends K> multi = it.next();
    697            if (multi.size() >= 1 &&
    698                Objects.equals(key1, multi.getKey(0))) {
    699                it.remove();
    700                modified = true;
    701            }
    702        }
    703        return modified;
    704    }
    705
    706    /**
    707     * Removes all mappings where the first two keys are those specified.
    708     * <p>
    709     * This method removes all the mappings where the {@code MultiKey}
    710     * has two or more keys, and the first two match those specified.
    711     * </p>
    712     *
    713     * @param key1  the first key
    714     * @param key2  the second key
    715     * @return true if any elements were removed
    716     */
    717    public boolean removeAll(final Object key1, final Object key2) {
    718        boolean modified = false;
    719        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    720        while (it.hasNext()) {
    721            final MultiKey<? extends K> multi = it.next();
    722            if (multi.size() >= 2 &&
    723                Objects.equals(key1, multi.getKey(0)) &&
    724                Objects.equals(key2, multi.getKey(1))) {
    725                it.remove();
    726                modified = true;
    727            }
    728        }
    729        return modified;
    730    }
    731
    732    /**
    733     * Removes all mappings where the first three keys are those specified.
    734     * <p>
    735     * This method removes all the mappings where the {@code MultiKey}
    736     * has three or more keys, and the first three match those specified.
    737     * </p>
    738     *
    739     * @param key1  the first key
    740     * @param key2  the second key
    741     * @param key3  the third key
    742     * @return true if any elements were removed
    743     */
    744    public boolean removeAll(final Object key1, final Object key2, final Object key3) {
    745        boolean modified = false;
    746        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    747        while (it.hasNext()) {
    748            final MultiKey<? extends K> multi = it.next();
    749            if (multi.size() >= 3 &&
    750                Objects.equals(key1, multi.getKey(0)) &&
    751                Objects.equals(key2, multi.getKey(1)) &&
    752                Objects.equals(key3, multi.getKey(2))) {
    753                it.remove();
    754                modified = true;
    755            }
    756        }
    757        return modified;
    758    }
    759
    760    /**
    761     * Removes all mappings where the first four keys are those specified.
    762     * <p>
    763     * This method removes all the mappings where the {@code MultiKey}
    764     * has four or more keys, and the first four match those specified.
    765     * </p>
    766     *
    767     * @param key1  the first key
    768     * @param key2  the second key
    769     * @param key3  the third key
    770     * @param key4  the fourth key
    771     * @return true if any elements were removed
    772     */
    773    public boolean removeAll(final Object key1, final Object key2, final Object key3, final Object key4) {
    774        boolean modified = false;
    775        final MapIterator<MultiKey<? extends K>, V> it = mapIterator();
    776        while (it.hasNext()) {
    777            final MultiKey<? extends K> multi = it.next();
    778            if (multi.size() >= 4 &&
    779                Objects.equals(key1, multi.getKey(0)) &&
    780                Objects.equals(key2, multi.getKey(1)) &&
    781                Objects.equals(key3, multi.getKey(2)) &&
    782                Objects.equals(key4, multi.getKey(3))) {
    783                it.remove();
    784                modified = true;
    785            }
    786        }
    787        return modified;
    788    }
    789
    790    /**
    791     * Removes the specified multi-key from this map.
    792     *
    793     * @param key1  the first key
    794     * @param key2  the second key
    795     * @return the value mapped to the removed key, null if key not in map
    796     * @since 4.0 (previous name: remove(Object, Object))
    797     */
    798    public V removeMultiKey(final Object key1, final Object key2) {
    799        final int hashCode = hash(key1, key2);
    800        final int index = decoratedHashIndex(hashCode);
    801        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    802        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    803        while (entry != null) {
    804            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2)) {
    805                final V oldValue = entry.getValue();
    806                decorated().removeMapping(entry, index, previous);
    807                return oldValue;
    808            }
    809            previous = entry;
    810            entry = entry.next;
    811        }
    812        return null;
    813    }
    814
    815    /**
    816     * Removes the specified multi-key from this map.
    817     *
    818     * @param key1  the first key
    819     * @param key2  the second key
    820     * @param key3  the third key
    821     * @return the value mapped to the removed key, null if key not in map
    822     * @since 4.0 (previous name: remove(Object, Object, Object))
    823     */
    824    public V removeMultiKey(final Object key1, final Object key2, final Object key3) {
    825        final int hashCode = hash(key1, key2, key3);
    826        final int index = decoratedHashIndex(hashCode);
    827        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    828        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    829        while (entry != null) {
    830            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3)) {
    831                final V oldValue = entry.getValue();
    832                decorated().removeMapping(entry, index, previous);
    833                return oldValue;
    834            }
    835            previous = entry;
    836            entry = entry.next;
    837        }
    838        return null;
    839    }
    840
    841    /**
    842     * Removes the specified multi-key from this map.
    843     *
    844     * @param key1  the first key
    845     * @param key2  the second key
    846     * @param key3  the third key
    847     * @param key4  the fourth key
    848     * @return the value mapped to the removed key, null if key not in map
    849     * @since 4.0 (previous name: remove(Object, Object, Object, Object))
    850     */
    851    public V removeMultiKey(final Object key1, final Object key2, final Object key3, final Object key4) {
    852        final int hashCode = hash(key1, key2, key3, key4);
    853        final int index = decoratedHashIndex(hashCode);
    854        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    855        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    856        while (entry != null) {
    857            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4)) {
    858                final V oldValue = entry.getValue();
    859                decorated().removeMapping(entry, index, previous);
    860                return oldValue;
    861            }
    862            previous = entry;
    863            entry = entry.next;
    864        }
    865        return null;
    866    }
    867
    868    /**
    869     * Removes the specified multi-key from this map.
    870     *
    871     * @param key1  the first key
    872     * @param key2  the second key
    873     * @param key3  the third key
    874     * @param key4  the fourth key
    875     * @param key5  the fifth key
    876     * @return the value mapped to the removed key, null if key not in map
    877     * @since 4.0 (previous name: remove(Object, Object, Object, Object, Object))
    878     */
    879    public V removeMultiKey(final Object key1, final Object key2, final Object key3,
    880                            final Object key4, final Object key5) {
    881        final int hashCode = hash(key1, key2, key3, key4, key5);
    882        final int index = decoratedHashIndex(hashCode);
    883        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> entry = decorated().data[index];
    884        AbstractHashedMap.HashEntry<MultiKey<? extends K>, V> previous = null;
    885        while (entry != null) {
    886            if (entry.hashCode == hashCode && isEqualKey(entry, key1, key2, key3, key4, key5)) {
    887                final V oldValue = entry.getValue();
    888                decorated().removeMapping(entry, index, previous);
    889                return oldValue;
    890            }
    891            previous = entry;
    892            entry = entry.next;
    893        }
    894        return null;
    895    }
    896
    897    /**
    898     * Serializes this object to an ObjectOutputStream.
    899     *
    900     * @param out the target ObjectOutputStream.
    901     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    902     */
    903    private void writeObject(final ObjectOutputStream out) throws IOException {
    904        out.defaultWriteObject();
    905        out.writeObject(map);
    906    }
    907
    908}