IdentityHashMap 源码

2020-02-10

技术

字数统计: 2.5k字 | 阅读时长≈ 14分钟

概述

IdentityHashMap 使用 hash 表存储数据，实现了 Map 接口。
与 HashMap 不同的是，IdentityHashMap 使用 引用相等 替换 对象相等；

也就是说，IdentityHashMap 判断两个 key 相等的方式是 (k1==k2)，
而 HashMap 判断两个 key 相等的方式是 (k1==null ? k2==null : k1.equals(k2))；

继承结构

IdentityHashMap继承结构

实现了 Map 接口，拥有 Map 特性；

源码实现

属性

View Code

/**
 * The initial capacity used by the no-args constructor.
 * MUST be a power of two.  The value 32 corresponds to the
 * (specified) expected maximum size of 21, given a load factor
 * of 2/3.
 */
private static final int DEFAULT_CAPACITY = 32;

/**
 * The minimum capacity, used if a lower value is implicitly specified
 * by either of the constructors with arguments.  The value 4 corresponds
 * to an expected maximum size of 2, given a load factor of 2/3.
 * MUST be a power of two.
 */
private static final int MINIMUM_CAPACITY = 4;

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<29.
 *
 * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
 * because it has to have at least one slot with the key == null
 * in order to avoid infinite loops in get(), put(), remove()
 */
private static final int MAXIMUM_CAPACITY = 1 << 29;

/**
 * The table, resized as necessary. Length MUST always be a power of two.
 */
transient Object[] table; // non-private to simplify nested class access

/**
 * The number of key-value mappings contained in this identity hash map.
 *
 * @serial
 */
int size;

/**
 * The number of modifications, to support fast-fail iterators
 */
transient int modCount;

/**
 * Value representing null keys inside tables.
 */
static final Object NULL_KEY = new Object();

/**
 * Use NULL_KEY for key if it is null.
 */
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

/**
 * Returns internal representation of null key back to caller as null.
 */
static final Object unmaskNull(Object key) {
    return (key == NULL_KEY ? null : key);
}

默认容量：32
最小容量：4
最大容量为：1 << 29

这里小于 MAXIMUM_CAPACITY-1，是因为它必须有一个 key 等于 null 的位置，
为了避免 get,put,remove 方法进入无限循环

构造方法

View Code

/**
 * Constructs a new, empty identity hash map with a default expected
 * maximum size (21).
 */
public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}

/**
 * Constructs a new, empty map with the specified expected maximum size.
 * Putting more than the expected number of key-value mappings into
 * the map may cause the internal data structure to grow, which may be
 * somewhat time-consuming.
 *
 * @param expectedMaxSize the expected maximum size of the map
 * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
 */
public IdentityHashMap(int expectedMaxSize) {
    if (expectedMaxSize < 0)
        throw new IllegalArgumentException("expectedMaxSize is negative: "
                                           + expectedMaxSize);
    init(capacity(expectedMaxSize));
}

/**
 * Returns the appropriate capacity for the given expected maximum size.
 * Returns the smallest power of two between MINIMUM_CAPACITY and
 * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
 * expectedMaxSize)/2, if such a number exists.  Otherwise returns
 * MAXIMUM_CAPACITY.
 */
private static int capacity(int expectedMaxSize) {
    // assert expectedMaxSize >= 0;
    return
        (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
        (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
        Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}

/**
 * Constructs a new identity hash map containing the keys-value mappings
 * in the specified map.
 *
 * @param m the map whose mappings are to be placed into this map
 * @throws NullPointerException if the specified map is null
 */
public IdentityHashMap(Map<? extends K, ? extends V> m) {
    // Allow for a bit of growth
    this((int) ((1 + m.size()) * 1.1));
    putAll(m);
}

没有指定初始容量，则使用默认的初始容量：32；
指定期望的初始容量，使用大于期望容量最小 2 的 n 次幂；

put(K key, V value)

View Code

/**
 * Associates the specified value with the specified key in this identity
 * hash map.  If the map previously contained a mapping for the key, the
 * old value is replaced.
 *
 * @param key the key with which the specified value is to be associated
 * @param value the value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 * @see     Object#equals(Object)
 * @see     #get(Object)
 * @see     #containsKey(Object)
 */
public V put(K key, V value) {
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        int i = hash(k, len);

        for (Object item; (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) {
            if (item == k) {
                @SuppressWarnings("unchecked")
                    V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }

        final int s = size + 1;
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        // 如果3*size 大于数组的length，则进行扩容
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

/**
 * Returns index for Object x.
 */
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

put 的时候先通过引用是否相等判断key是不是已经在表中存在，如果存在更新 oldValue 为新的 value，如果元素个数达到阈值，扩容处理，然后再找合适的位置放置 key 和 value；
在数组的i索引处存key，而紧挨着 i 的 i+1 处存 value，并且由于 hash 方法的原因，key 所对应的 index 全是偶数，自然 i+1 就是奇数了。这也说明了另一点，数组初始化的时候，数组的长度被定义为默认容量的 2 倍，因为数组元素的每次保存是都占了数组的两个位置。
put 的扩容条件是当存放的数组达到数组长度的 1/3 的时候，就需要扩容。
System.identityHashCode(x) 是取地址值进行计算；

get(Object key)

View Code

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key == k)},
 * then this method returns {@code v}; otherwise it returns
 * {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
@SuppressWarnings("unchecked")
public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)
            return (V) tab[i + 1];
        if (item == null)
            return null;
        // hash 冲突，移位遍历
        i = nextKeyIndex(i, len);
    }
}

/**
 * Circularly traverses table of size len.
 */
private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}

如果 i 处找到 key，说明 i+1 处就是索引对应的 value；
如果 i 处找到的 key 值和传入的 key 不相等，说明 hash 冲突，移动 2 个位置继续查找；

remove(Object key)

View Code

/**
 * Removes the mapping for this key from this map if present.
 *
 * @param key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);

    while (true) {
        Object item = tab[i];
        if (item == k) {
            modCount++;
            size--;
            @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
            tab[i + 1] = null;
            tab[i] = null;
            closeDeletion(i);
            return oldValue;
        }
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}

删除方法与查找方法类似，找到则置空，释放空间；

resize(int newCapacity)

View Code

/**
 * Resizes the table if necessary to hold given capacity.
 *
 * @param newCapacity the new capacity, must be a power of two.
 * @return whether a resize did in fact take place
 */
private boolean resize(int newCapacity) {
    // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
    int newLength = newCapacity * 2;

    Object[] oldTable = table;
    int oldLength = oldTable.length;
    if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
        if (size == MAXIMUM_CAPACITY - 1)
            throw new IllegalStateException("Capacity exhausted.");
        return false;
    }
    if (oldLength >= newLength)
        return false;

    Object[] newTable = new Object[newLength];

    for (int j = 0; j < oldLength; j += 2) {
        Object key = oldTable[j];
        if (key != null) {
            Object value = oldTable[j+1];
            oldTable[j] = null;
            oldTable[j+1] = null;
            int i = hash(key, newLength);
            while (newTable[i] != null)
                i = nextKeyIndex(i, newLength);
            newTable[i] = key;
            newTable[i + 1] = value;
        }
    }
    table = newTable;
    return true;
}

扩容的数组是原来的两倍；

hashCode() & equals(Object o)

View Code

/**
 * Returns the hash code value for this map.  The hash code of a map is
 * defined to be the sum of the hash codes of each entry in the map's
 * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two
 * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as
 * required by the general contract of {@link Object#hashCode}.
 *
 * <p><b>Owing to the reference-equality-based semantics of the
 * <tt>Map.Entry</tt> instances in the set returned by this map's
 * <tt>entrySet</tt> method, it is possible that the contractual
 * requirement of <tt>Object.hashCode</tt> mentioned in the previous
 * paragraph will be violated if one of the two objects being compared is
 * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>
 *
 * @return the hash code value for this map
 * @see Object#equals(Object)
 * @see #equals(Object)
 */
public int hashCode() {
    int result = 0;
    Object[] tab = table;
    for (int i = 0; i < tab.length; i +=2) {
        Object key = tab[i];
        if (key != null) {
            Object k = unmaskNull(key);
            result += System.identityHashCode(k) ^
                      System.identityHashCode(tab[i + 1]);
        }
    }
    return result;
}

/**
 * Compares the specified object with this map for equality.  Returns
 * <tt>true</tt> if the given object is also a map and the two maps
 * represent identical object-reference mappings.  More formally, this
 * map is equal to another map <tt>m</tt> if and only if
 * <tt>this.entrySet().equals(m.entrySet())</tt>.
 *
 * <p><b>Owing to the reference-equality-based semantics of this map it is
 * possible that the symmetry and transitivity requirements of the
 * <tt>Object.equals</tt> contract may be violated if this map is compared
 * to a normal map.  However, the <tt>Object.equals</tt> contract is
 * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>
 *
 * @param  o object to be compared for equality with this map
 * @return <tt>true</tt> if the specified object is equal to this map
 * @see Object#equals(Object)
 */
public boolean equals(Object o) {
    if (o == this) {
        return true;
    } else if (o instanceof IdentityHashMap) {
        IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
        if (m.size() != size)
            return false;

        Object[] tab = m.table;
        for (int i = 0; i < tab.length; i+=2) {
            Object k = tab[i];
            if (k != null && !containsMapping(k, tab[i + 1]))
                return false;
        }
        return true;
    } else if (o instanceof Map) {
        Map<?,?> m = (Map<?,?>)o;
        return entrySet().equals(m.entrySet());
    } else {
        return false;  // o is not a Map
    }
}

IdentityHashMap 重写了 equals 和 hashcode 方法，通过 System.identityHashCode 方法来实现的 hashCode ，确保使用地址值来判断；
通过重写 equals 方法，判定只有 key 值全等情况下才会判断 value 值相等；

总结

IdentityHashMap 的实现不同于 HashMap，虽然也是数组，不过 IdentityHashMap 中没有用到链表，解决冲突的方式是计算下一个有效索引，并且将数据 key 和 value 紧挨着存在map中，即 table[i]=key，那么 table[i+1]=value。
IdentityHashMap 的 hash 的计算没有使用 Object 的 hashCode 方法，而是使用的 System.identityHashCode 方法，这是根据对象的内存地址来计算散列码。