java/util/IdentityHashMap.java

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package java.util;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

/**
 * IdentityHashMap is a variant on HashMap which tests equality by reference
 * instead of equality by value. Basically, keys and values are compared for
 * equality by checking if their references are equal rather than by calling the
 * "equals" function.
 * <p>
 * <b>Note: This class intentionally violates the general contract of {@code
 * Map}'s on comparing objects by their {@code equals} method.</b>
 * <p>
 * IdentityHashMap uses open addressing (linear probing in particular) for
 * collision resolution. This is different from HashMap which uses Chaining.
 * <p>
 * Like HashMap, IdentityHashMap is not thread safe, so access by multiple
 * threads must be synchronized by an external mechanism such as
 * Collections.synchronizedMap.
 *
 * @since 1.4
 */
public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements
        Map<K, V>, Serializable, Cloneable {

    private static final long serialVersionUID = 8188218128353913216L;

    /*
     * The internal data structure to hold key value pairs This array holds keys
     * and values in an alternating fashion.
     */
    transient Object[] elementData;

    /* Actual number of key-value pairs. */
    int size;

    /*
     * maximum number of elements that can be put in this map before having to
     * rehash.
     */
    transient int threshold;

    /*
     * default threshold value that an IdentityHashMap created using the default
     * constructor would have.
     */
    private static final int DEFAULT_MAX_SIZE = 21;

    /* Default load factor of 0.75; */
    private static final int loadFactor = 7500;

    /*
     * modification count, to keep track of structural modifications between the
     * IdentityHashMap and the iterator
     */
    transient int modCount = 0;

    /*
     * Object used to represent null keys and values. This is used to
     * differentiate a literal 'null' key value pair from an empty spot in the
     * map.
     */
    private static final Object NULL_OBJECT = new Object();  //$NON-LOCK-1$

    static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> {
        private final IdentityHashMap<K,V> map;

        IdentityHashMapEntry(IdentityHashMap<K,V> map, K theKey, V theValue) {
            super(theKey, theValue);
            this.map = map;
        }

        @Override
        public Object clone() {
            return super.clone();
        }

        @Override
        public boolean equals(Object object) {
            if (this == object) {
                return true;
            }
            if (object instanceof Map.Entry) {
                Map.Entry<?, ?> entry = (Map.Entry) object;
                return (key == entry.getKey()) && (value == entry.getValue());
            }
            return false;
        }

        @Override
        public int hashCode() {
            return System.identityHashCode(key)
                    ^ System.identityHashCode(value);
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }

        @Override
        public V setValue(V object) {
            V result = super.setValue(object);
            map.put(key, object);
            return result;
        }
    }

    static class IdentityHashMapIterator<E, KT, VT> implements Iterator<E> {
        private int position = 0; // the current position

        // the position of the entry that was last returned from next()
        private int lastPosition = 0;

        final IdentityHashMap<KT, VT> associatedMap;

        int expectedModCount;

        final MapEntry.Type<E, KT, VT> type;

        boolean canRemove = false;

        IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value,
                IdentityHashMap<KT, VT> hm) {
            associatedMap = hm;
            type = value;
            expectedModCount = hm.modCount;
        }

        public boolean hasNext() {
            while (position < associatedMap.elementData.length) {
                // if this is an empty spot, go to the next one
                if (associatedMap.elementData[position] == null) {
                    position += 2;
                } else {
                    return true;
                }
            }
            return false;
        }

        void checkConcurrentMod() throws ConcurrentModificationException {
            if (expectedModCount != associatedMap.modCount) {
                throw new ConcurrentModificationException();
            }
        }

        public E next() {
            checkConcurrentMod();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            IdentityHashMapEntry<KT, VT> result = associatedMap
                    .getEntry(position);
            lastPosition = position;
            position += 2;

            canRemove = true;
            return type.get(result);
        }

        public void remove() {
            checkConcurrentMod();
            if (!canRemove) {
                throw new IllegalStateException();
            }

            canRemove = false;
            associatedMap.remove(associatedMap.elementData[lastPosition]);
            position = lastPosition;
            expectedModCount++;
        }
    }

    static class IdentityHashMapEntrySet<KT, VT> extends
            AbstractSet<Map.Entry<KT, VT>> {
        private final IdentityHashMap<KT, VT> associatedMap;

        public IdentityHashMapEntrySet(IdentityHashMap<KT, VT> hm) {
            associatedMap = hm;
        }

        IdentityHashMap<KT, VT> hashMap() {
            return associatedMap;
        }

        @Override
        public int size() {
            return associatedMap.size;
        }

        @Override
        public void clear() {
            associatedMap.clear();
        }

        @Override
        public boolean remove(Object object) {
            if (contains(object)) {
                associatedMap.remove(((Map.Entry) object).getKey());
                return true;
            }
            return false;
        }

        @Override
        public boolean contains(Object object) {
            if (object instanceof Map.Entry) {
                IdentityHashMapEntry<?, ?> entry = associatedMap
                        .getEntry(((Map.Entry) object).getKey());
                // we must call equals on the entry obtained from "this"
                return entry != null && entry.equals(object);
            }
            return false;
        }

        @Override
        public Iterator<Map.Entry<KT, VT>> iterator() {
            return new IdentityHashMapIterator<Map.Entry<KT, VT>, KT, VT>(
                    new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
                        public Map.Entry<KT, VT> get(MapEntry<KT, VT> entry) {
                            return entry;
                        }
                    }, associatedMap);
        }
    }

    /**
     * Creates an IdentityHashMap with default expected maximum size.
     */
    public IdentityHashMap() {
        this(DEFAULT_MAX_SIZE);
    }

    /**
     * Creates an IdentityHashMap with the specified maximum size parameter.
     *
     * @param maxSize
     *            The estimated maximum number of entries that will be put in
     *            this map.
     */
    public IdentityHashMap(int maxSize) {
        if (maxSize < 0) {
            throw new IllegalArgumentException("maxSize < 0: " + maxSize);
        }
        size = 0;
        threshold = getThreshold(maxSize);
        elementData = newElementArray(computeElementArraySize());
    }

    private int getThreshold(int maxSize) {
        // assign the threshold to maxSize initially, this will change to a
        // higher value if rehashing occurs.
        return maxSize > 3 ? maxSize : 3;
    }

    private int computeElementArraySize() {
        int arraySize = (int) (((long) threshold * 10000) / loadFactor) * 2;
        // ensure arraySize is positive, the above cast from long to int type
        // leads to overflow and negative arraySize if threshold is too big
        return arraySize < 0 ? -arraySize : arraySize;
    }

    /**
     * Create a new element array
     *
     * @param s
     *            the number of elements
     * @return Reference to the element array
     */
    private Object[] newElementArray(int s) {
        return new Object[s];
    }

    /**
     * Creates an IdentityHashMap using the given map as initial values.
     *
     * @param map
     *            A map of (key,value) pairs to copy into the IdentityHashMap.
     */
    public IdentityHashMap(Map<? extends K, ? extends V> map) {
        this(map.size() < 6 ? 11 : map.size() * 2);
        putAllImpl(map);
    }

    @SuppressWarnings("unchecked")
    private V massageValue(Object value) {
        return (V) ((value == NULL_OBJECT) ? null : value);
    }

    /**
     * Removes all elements from this map, leaving it empty.
     *
     * @see #isEmpty()
     * @see #size()
     */
    @Override
    public void clear() {
        size = 0;
        for (int i = 0; i < elementData.length; i++) {
            elementData[i] = null;
        }
        modCount++;
    }

    /**
     * Returns whether this map contains the specified key.
     *
     * @param key
     *            the key to search for.
     * @return {@code true} if this map contains the specified key,
     *         {@code false} otherwise.
     */
    @Override
    public boolean containsKey(Object key) {
        if (key == null) {
            key = NULL_OBJECT;
        }

        int index = findIndex(key, elementData);
        return elementData[index] == key;
    }

    /**
     * Returns whether this map contains the specified value.
     *
     * @param value
     *            the value to search for.
     * @return {@code true} if this map contains the specified value,
     *         {@code false} otherwise.
     */
    @Override
    public boolean containsValue(Object value) {
        if (value == null) {
            value = NULL_OBJECT;
        }

        for (int i = 1; i < elementData.length; i = i + 2) {
            if (elementData[i] == value) {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns the value of the mapping with the specified key.
     *
     * @param key
     *            the key.
     * @return the value of the mapping with the specified key.
     */
    @Override
    public V get(Object key) {
        if (key == null) {
            key = NULL_OBJECT;
        }

        int index = findIndex(key, elementData);

        if (elementData[index] == key) {
            Object result = elementData[index + 1];
            return massageValue(result);
        }

        return null;
    }

    private IdentityHashMapEntry<K, V> getEntry(Object key) {
        if (key == null) {
            key = NULL_OBJECT;
        }

        int index = findIndex(key, elementData);
        if (elementData[index] == key) {
            return getEntry(index);
        }

        return null;
    }

    /**
     * Convenience method for getting the IdentityHashMapEntry without the
     * NULL_OBJECT elements
     */
    @SuppressWarnings("unchecked")
    private IdentityHashMapEntry<K, V> getEntry(int index) {
        Object key = elementData[index];
        Object value = elementData[index + 1];

        if (key == NULL_OBJECT) {
            key = null;
        }
        if (value == NULL_OBJECT) {
            value = null;
        }

        return new IdentityHashMapEntry<K, V>(this, (K) key, (V) value);
    }

    /**
     * Returns the index where the key is found at, or the index of the next
     * empty spot if the key is not found in this table.
     */
    private int findIndex(Object key, Object[] array) {
        int length = array.length;
        int index = getModuloHash(key, length);
        int last = (index + length - 2) % length;
        while (index != last) {
            if (array[index] == key || (array[index] == null)) {
                /*
                 * Found the key, or the next empty spot (which means key is not
                 * in the table)
                 */
                break;
            }
            index = (index + 2) % length;
        }
        return index;
    }

    private int getModuloHash(Object key, int length) {
        return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2;
    }

    /**
     * Maps the specified key to the specified value.
     *
     * @param key
     *            the key.
     * @param value
     *            the value.
     * @return the value of any previous mapping with the specified key or
     *         {@code null} if there was no such mapping.
     */
    @Override
    public V put(K key, V value) {
        Object _key = key;
        Object _value = value;
        if (_key == null) {
            _key = NULL_OBJECT;
        }

        if (_value == null) {
            _value = NULL_OBJECT;
        }

        int index = findIndex(_key, elementData);

        // if the key doesn't exist in the table
        if (elementData[index] != _key) {
            modCount++;
            if (++size > threshold) {
                rehash();
                index = findIndex(_key, elementData);
            }

            // insert the key and assign the value to null initially
            elementData[index] = _key;
            elementData[index + 1] = null;
        }

        // insert value to where it needs to go, return the old value
        Object result = elementData[index + 1];
        elementData[index + 1] = _value;

        return massageValue(result);
    }

    /**
     * Copies all the mappings in the specified map to this map. These mappings
     * will replace all mappings that this map had for any of the keys currently
     * in the given map.
     *
     * @param map
     *            the map to copy mappings from.
     * @throws NullPointerException
     *             if {@code map} is {@code null}.
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> map) {
        putAllImpl(map);
    }

    private void rehash() {
        int newlength = elementData.length * 2;
        if (newlength == 0) {
            newlength = 1;
        }
        Object[] newData = newElementArray(newlength);
        for (int i = 0; i < elementData.length; i = i + 2) {
            Object key = elementData[i];
            if (key != null) {
                // if not empty
                int index = findIndex(key, newData);
                newData[index] = key;
                newData[index + 1] = elementData[i + 1];
            }
        }
        elementData = newData;
        computeMaxSize();
    }

    private void computeMaxSize() {
        threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
    }

    /**
     * Removes the mapping with the specified key from this map.
     *
     * @param key
     *            the key of the mapping to remove.
     * @return the value of the removed mapping, or {@code null} if no mapping
     *         for the specified key was found.
     */
    @Override
    public V remove(Object key) {
        if (key == null) {
            key = NULL_OBJECT;
        }

        boolean hashedOk;
        int index, next, hash;
        Object result, object;
        index = next = findIndex(key, elementData);

        if (elementData[index] != key) {
            return null;
        }

        // store the value for this key
        result = elementData[index + 1];

        // shift the following elements up if needed
        // until we reach an empty spot
        int length = elementData.length;
        while (true) {
            next = (next + 2) % length;
            object = elementData[next];
            if (object == null) {
                break;
            }

            hash = getModuloHash(object, length);
            hashedOk = hash > index;
            if (next < index) {
                hashedOk = hashedOk || (hash <= next);
            } else {
                hashedOk = hashedOk && (hash <= next);
            }
            if (!hashedOk) {
                elementData[index] = object;
                elementData[index + 1] = elementData[next + 1];
                index = next;
            }
        }

        size--;
        modCount++;

        // clear both the key and the value
        elementData[index] = null;
        elementData[index + 1] = null;

        return massageValue(result);
    }

    /**
     * Returns a set containing all of the mappings in this map. Each mapping is
     * an instance of {@link Map.Entry}. As the set is backed by this map,
     * changes in one will be reflected in the other.
     *
     * @return a set of the mappings.
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return new IdentityHashMapEntrySet<K, V>(this);
    }

    /**
     * Returns a set of the keys contained in this map. The set is backed by
     * this map so changes to one are reflected by the other. The set does not
     * support adding.
     *
     * @return a set of the keys.
     */
    @Override
    public Set<K> keySet() {
        if (keySet == null) {
            keySet = new AbstractSet<K>() {
                @Override
                public boolean contains(Object object) {
                    return containsKey(object);
                }

                @Override
                public int size() {
                    return IdentityHashMap.this.size();
                }

                @Override
                public void clear() {
                    IdentityHashMap.this.clear();
                }

                @Override
                public boolean remove(Object key) {
                    if (containsKey(key)) {
                        IdentityHashMap.this.remove(key);
                        return true;
                    }
                    return false;
                }

                @Override
                public Iterator<K> iterator() {
                    return new IdentityHashMapIterator<K, K, V>(
                            new MapEntry.Type<K, K, V>() {
                                public K get(MapEntry<K, V> entry) {
                                    return entry.key;
                                }
                            }, IdentityHashMap.this);
                }
            };
        }
        return keySet;
    }

    /**
     * Returns a collection of the values contained in this map. The collection
     * is backed by this map so changes to one are reflected by the other. The
     * collection supports remove, removeAll, retainAll and clear operations,
     * and it does not support add or addAll operations.
     * <p>
     * This method returns a collection which is the subclass of
     * AbstractCollection. The iterator method of this subclass returns a
     * "wrapper object" over the iterator of map's entrySet(). The {@code size}
     * method wraps the map's size method and the {@code contains} method wraps
     * the map's containsValue method.
     * <p>
     * The collection is created when this method is called for the first time
     * and returned in response to all subsequent calls. This method may return
     * different collections when multiple concurrent calls occur, since no
     * synchronization is performed.
     *
     * @return a collection of the values contained in this map.
     */
    @Override
    public Collection<V> values() {
        if (valuesCollection == null) {
            valuesCollection = new AbstractCollection<V>() {
                @Override
                public boolean contains(Object object) {
                    return containsValue(object);
                }

                @Override
                public int size() {
                    return IdentityHashMap.this.size();
                }

                @Override
                public void clear() {
                    IdentityHashMap.this.clear();
                }

                @Override
                public Iterator<V> iterator() {
                    return new IdentityHashMapIterator<V, K, V>(
                            new MapEntry.Type<V, K, V>() {
                                public V get(MapEntry<K, V> entry) {
                                    return entry.value;
                                }
                            }, IdentityHashMap.this);
                }

                @Override
                public boolean remove(Object object) {
                    Iterator<?> it = iterator();
                    while (it.hasNext()) {
                        if (object == it.next()) {
                            it.remove();
                            return true;
                        }
                    }
                    return false;
                }
            };
        }
        return valuesCollection;
    }

    /**
     * Compares this map with other objects. This map is equal to another map is
     * it represents the same set of mappings. With this map, two mappings are
     * the same if both the key and the value are equal by reference. When
     * compared with a map that is not an IdentityHashMap, the equals method is
     * neither necessarily symmetric (a.equals(b) implies b.equals(a)) nor
     * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
     *
     * @param object
     *            the object to compare to.
     * @return whether the argument object is equal to this object.
     */
    @Override
    public boolean equals(Object object) {
        /*
         * We need to override the equals method in AbstractMap because
         * AbstractMap.equals will call ((Map) object).entrySet().contains() to
         * determine equality of the entries, so it will defer to the argument
         * for comparison, meaning that reference-based comparison will not take
         * place. We must ensure that all comparison is implemented by methods
         * in this class (or in one of our inner classes) for reference-based
         * comparison to take place.
         */
        if (this == object) {
            return true;
        }
        if (object instanceof Map) {
            Map<?, ?> map = (Map) object;
            if (size() != map.size()) {
                return false;
            }

            Set<Map.Entry<K, V>> set = entrySet();
            // ensure we use the equals method of the set created by "this"
            return set.equals(map.entrySet());
        }
        return false;
    }

    /**
     * Returns a new IdentityHashMap with the same mappings and size as this
     * one.
     *
     * @return a shallow copy of this IdentityHashMap.
     * @see java.lang.Cloneable
     */
    @Override
    public Object clone() {
        try {
            IdentityHashMap<K, V> cloneHashMap = (IdentityHashMap<K, V>) super.clone();
            cloneHashMap.elementData = newElementArray(elementData.length);
            System.arraycopy(elementData, 0, cloneHashMap.elementData, 0, elementData.length);
            return cloneHashMap;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError(e);
        }
    }

    /**
     * Returns whether this IdentityHashMap has no elements.
     *
     * @return {@code true} if this IdentityHashMap has no elements,
     *         {@code false} otherwise.
     * @see #size()
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns the number of mappings in this IdentityHashMap.
     *
     * @return the number of mappings in this IdentityHashMap.
     */
    @Override
    public int size() {
        return size;
    }

    private void writeObject(ObjectOutputStream stream) throws IOException {
        stream.defaultWriteObject();
        stream.writeInt(size);
        Iterator<?> iterator = entrySet().iterator();
        while (iterator.hasNext()) {
            MapEntry<?, ?> entry = (MapEntry) iterator.next();
            stream.writeObject(entry.key);
            stream.writeObject(entry.value);
        }
    }

    @SuppressWarnings("unchecked")
    private void readObject(ObjectInputStream stream) throws IOException,
            ClassNotFoundException {
        stream.defaultReadObject();
        int savedSize = stream.readInt();
        threshold = getThreshold(DEFAULT_MAX_SIZE);
        elementData = newElementArray(computeElementArraySize());
        for (int i = savedSize; --i >= 0;) {
            K key = (K) stream.readObject();
            put(key, (V) stream.readObject());
        }
        size = savedSize;
    }

    private void putAllImpl(Map<? extends K, ? extends V> map) {
        if (map.entrySet() != null) {
            super.putAll(map);
        }
    }
}