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