Java容器之IdentityHashMap源码分析(Source code analysis of identityhashmap in Java container)

一、概述

利用哈希表实现接口,比较键(和值)时使用引用相等性代替对象相等性。换句话说,在中,当且仅当()时,才认为两个键和相等(在正常实现(如)中,当且仅当满足下列条件时才认为两个键和相等:()。

IdentityHashMap
Map
IdentityHashMap
k1==k2
k1
k2
Map
HashMap
k1
k2
k1==null ? k2==null : e1.equals(e2))

此类不是通用实现!此类实现接口时,它有意违反的常规协定,该协定在比较对象时强制使用方法。此类设计仅用于其中需要引用相等性语义的罕见情况。

Map
Map
Map
equals

二、源码分析

2.1 属性

/**
 * 无参数构造函数使用的初始容量。一定是2的幂。
 * 值32对应于(指定的)预期最大大小21,给定的负载系数为2/3。
 */
private static final int DEFAULT_CAPACITY = 32;

/**
 * 最小容量,如果隐式指定一个较低的值,则使用
 * 由两个带有参数的构造函数组成。 给定2/3的负载系数,值4对应于预期的最大大小2。 必须是2的幂。
 */
private static final int MINIMUM_CAPACITY = 4;

/**
 * 最大容量,如果隐式指定了更高的值,则使用的最大容量
 * 由任何一个带参数的构造函数。必须是2的幂且 <= 1<<29。
 *
 * 事实上,该Map最多只能有MAXIMUM_CAPACITY-1个元素,因为它必须有一个key等于null的位置,
 * 这是为了避免get,put,remove方法的无限循环
 */
private static final int MAXIMUM_CAPACITY = 1 << 29;

/**
 * 对象数组table,根据需要调整大小。 长度必须始终为2的幂。
 * 注意:是Object对象数组;其他的 Map 都是Entry<K,V>或者Node<K,V>的类结构
 */
transient Object[] table; // non-private to simplify nested class access

/**
 * map中键值对的数量
 */
int size;

/**
 * 修改的数量,以支持 fast-fail 的迭代器
 */
transient int modCount;

/**
 * 存储键为null的key,如果键为null,实际用NULL_KEY存储
 */
static final Object NULL_KEY = new Object();

有趣的是之前分析的其它中的,要么是数组,要么是数组,但在中使用的是对象数组。这就决定它内部、方法存、取键值对时,会比较特殊一些(数组索引为偶数存储的是键,索引为奇数存储的是值)。`

map
table
Entry<K,V>[]
Node<K,V>[]
IdentityHashMap
Object[]
put
get
table
key
value

注意:的加载因子为。

IdentityHashMap
2/3

2.2 构造方法

//默认构造函数,容量为32,加载因子为2/3,最多可存储32*2/3=21个键值对
public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}

//根据指定容量构造
public IdentityHashMap(int expectedMaxSize) {
    if (expectedMaxSize < 0)
        throw new IllegalArgumentException("expectedMaxSize is negative: "
                                           + expectedMaxSize);
    init(capacity(expectedMaxSize));
}

//返回一个介于MINIMUM_CAPACITY和MAXIMUM_CAPACITY,且大于3*expectedMaxSize/2的值
//如果该值不存在,返回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));
}

//初始化内部存储数组table,table数组大小为参数initCapacity的两倍
//为何是两倍?因为这是包括了键和值,刚好两倍
private void init(int initCapacity) {
    table = new Object[2 * initCapacity];
}

//通过指定map初始化
public IdentityHashMap(Map<? extends K, ? extends V> m) {
    this((int) ((1 + m.size()) * 1.1));
    putAll(m);
}

2.3 put()方法

该方法将指定的对添加到数组中,如果对应已经存在,则更新对应的。该方法返回该之前对应的。

key-value
table
key
value
key
value
/**
 * 在此标识哈希映射中关联指定值与指定键。如果映射以前包含了一个此键的映射关系,那么将替换旧值。
 *
 * @param key 要将指定值关联到的键
 * @param value 要关联到指定键的值
 * @return 返回与 key 相关联的先前值,如果 key 没有映射关系,则返回 null(返回 null 可能还表示映射以前将 null 与指定键关联)
 */
public V put(K key, V value) {
    //key = null的处理
    final Object k = maskNull(key);
    //retryAfterResize是java label标签,用于循环代码块之前
    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        // 计算键在数组中的位置,结果一定是偶数
        int i = hash(k, len);

        for (Object item; (item = tab[i]) != null;
            // 线性探测法 解决 hash 冲突;每次递增2
            // 找到下一个 key的位置,即 (i + 2 < len ? i + 2 : 0)
            i = nextKeyIndex(i, len)) {
            // 使用 == 比较键对象,如果为true,新值替换旧值
            if (item == k) {
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }
        //键值对数量加1
        final int s = size + 1;
        // Use optimized form of 3 * s.使用3 * s的优化形式。
        // Next capacity is len, 2 * current capacity.
        // 如果 map 中键值对的数目size * 3 大于 table 数组的长度 len,则触发扩容操作
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;
        //修改次数+1
        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

该方法查找对应的键值对,如果已经存在,替换并返回老的。添加键值对之前先判断是否需要重新分配数组的大小。如果需要,则重新分配。

key
value

的方法其实是循环调用了方法,不再说明。

IdentityHashMap
putAll
put

2.3.1 hash()方法

//返回对象x的在table数组中的索引位置,结果一定是偶数。
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);
}

调用类的方法

System
identityHashCode()
//无论给定对象的类是否覆盖hashCode(),都为给定对象返回与默认方法hashCode()返回的哈希码相同的哈希码。
public static native int identityHashCode(Object x);

2.3.2 nextKeyIndex()方法

//返回当前键索引的下一个索引,如果越过数组大小,返回数组位置0
private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}

2.3.3 resize()方法

private boolean resize(int newCapacity) {
    //新数组的大小为参数的两倍
    int newLength = newCapacity * 2;
    Object[] oldTable = table;
    int oldLength = oldTable.length;
    if (oldLength == 2 * MAXIMUM_CAPACITY) { 
        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];
            //let gc
            oldTable[j] = null;
            oldTable[j+1] = null;
            //找到key在新数组的索引
            int i = hash(key, newLength);
            //找到不为空的索引位置
            while (newTable[i] != null)
                i = nextKeyIndex(i, newLength);
            //存储到新数组的位置
            newTable[i] = key;
            newTable[i + 1] = value;
        }
    }
    table = newTable;
    return true;
}

方法首先确定新数组的大小,然后将老数组的元素复制到新的数组。

resize

2.4 get()方法

该方法返回键对应的值。

public V get(Object key) {
    //如果key为null,取null键对应的key
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    // 获取 key 在 table 数组中的索引
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        //相等,返回数组下一个位置存储的值
        if (item == k)
            return (V) tab[i + 1];
        //下一个key的索引位置为null,意味着当前 map 中所有键对象均已被遍历,没有找到对应key
        if (item == null)
            return null;
        //遍历下一个key的索引位置
        i = nextKeyIndex(i, len);
    }
}

通过该方法可以发现的存储原理,将键值对存储到内部的数组中,相邻两个位置处分别是和。查找过程中,如果发现当前位置存储的不是要查找的键,则轮询下一个()位置,这也是解决冲突的方法。

IdentityHashMap
Object[]
key
value
i + 2
IdentityHashMap

的、方法实现和实现基本相同,不再说明。

IdentityHashMap
containsKey
containsMapping
get

2.5 containsValue()方法

该方法判断是否存在指定的值。

public boolean containsValue(Object value) {
    Object[] tab = table;
    for (int i = 1; i < tab.length; i += 2)
        if (tab[i] == value && tab[i - 1] != null)
            return true;
    return false;
}

该方法实现很简单,中第一个存储的位置是,因此从开始查找,步长为。引用相等并且该对应的的不为的情况下,返回。

table
value
1
1
2
value
key
null
true

2.6 remove()方法

因为采用线性探测解决碰撞,数据都是连续存储的,所以当从中删除一个键时,需要更新维护线性探测关系。

hash
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;
            // 该位置的键值对移除了,空出了位置,看后面是否有键值对要填补这个位置(有些键值对是因为线性探测导致其位置偏离了其hash值)
            // 维持 put、get 等方法依赖的线性探测关系
            closeDeletion(i);
            return oldValue;
        }
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}

这里主要看下方法的用处。方法在删除某个键值对后调用,比如位置处的元素删除了,调用方法更新该位置之后的元素,减少地址冲突。复杂点就是要考虑是循环数组,线性探测的下一个键位置可能会在当前空出来的键位置的前面:

closeDeletion
closeDeletion
i
closeDeletion
table

2.6.1 closeDeletion()方法

private void closeDeletion(int d) {
    // Adapted from Knuth Section 6.4 Algorithm R
    Object[] tab = table;
    int len = tab.length;
 
    Object item;
    // d 是当前空出来的键值对位置
    // i 是当前处理的键值对位置
    // 循环遍历,当key为null时退出循环
    for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
         i = nextKeyIndex(i, len) ) {

        /**
         * 以下测试会触发插槽i中的项目(散列在插槽r中)是否应占据d腾出的位置。 
         * 如果是这样,我们将其交换,然后在新腾出的i处继续d。 当我们在此运行结束时点击空插槽时,此过程将终止。 
         * 因为table 是循环数组,需要注意i<r 的情况。
         * */
        int r = hash(item, len);
        if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
            tab[d] = item;
            tab[d + 1] = tab[i + 1];
            tab[i] = null;
            tab[i + 1] = null;
            d = i;
        }
    }
}

的方法和该方法的实现类似,不再说明。

IdentityHashMap
removeMapping

2.7 clear()方法

方法很简单,遍历数组并将数组元素值设置为。

clear
table
null
public void clear() {
    modCount++;
    Object[] tab = table;
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    size = 0;
}

2.8 迭代器-IdentityHashMapIterator

的迭代器是由抽象内部类实现的

IdentityHashMap
IdentityHashMapIterator
private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
    //当前位置
    int index = (size != 0 ? 0 : table.length); 
    //迭代器的快速失败机制
    int expectedModCount = modCount; 
    //最后一个返回的位置,删除的时候也是删除该位置的值
    int lastReturnedIndex = -1; 
    //这个参数是为了避免无效计算
    boolean indexValid; 
    Object[] traversalTable = table; 

    //哈希表是否还有下一个元素
    public boolean hasNext() {
        Object[] tab = traversalTable;
        for (int i = index; i < tab.length; i+=2) {
            Object key = tab[i];
            if (key != null) {
                //更新当前位置并返回true
                index = i;
                return indexValid = true;
            }
        }
        //到这,说明已经没有更多元素了
        index = tab.length;
        return false;
    }
    //返回下一个索引
    protected int nextIndex() {
        //迭代器的快速失败机制,说明有其他线程并发修改了该哈希表
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (!indexValid && !hasNext())
            throw new NoSuchElementException();
        //调用nextIndex方法后,设置indexValid为不可用,也就是说,不能连续调用nextIndex方法
        indexValid = false;
        lastReturnedIndex = index;
        index += 2;
        return lastReturnedIndex;
    }
    //删除当前位置的键值对后,重新调整后面的元素,减少冲突
    public void remove() {
        if (lastReturnedIndex == -1)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        expectedModCount = ++modCount;
        int deletedSlot = lastReturnedIndex;
        lastReturnedIndex = -1;
        index = deletedSlot;
        indexValid = false;
        Object[] tab = traversalTable;
        int len = tab.length;
        int d = deletedSlot;
        Object key = tab[d];
        tab[d] = null;      
        tab[d + 1] = null;
        if (tab != IdentityHashMap.this.table) {
            IdentityHashMap.this.remove(key);
            expectedModCount = modCount;
            return;
        }

        size--;

        Object item;
        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) {
            int r = hash(item, len);
            if ((i < r && (r <= d || d <= i)) ||
              (r <= d && d <= i)) {

                if (i < deletedSlot && d >= deletedSlot &&
                    traversalTable == IdentityHashMap.this.table) {
                    int remaining = len - deletedSlot;
                    Object[] newTable = new Object[remaining];
                    System.arraycopy(tab, deletedSlot,
                             newTable, 0, remaining);
                    traversalTable = newTable;
                    index = 0;
                }

                tab[d] = item;
                tab[d + 1] = tab[i + 1];
                tab[i] = null;
                tab[i + 1] = null;
                d = i;
            }
        }
    }
}

三、总结

  • 对于要保存的key,k1和k2,当且仅当k1 == k2的时候,IdentityHashMap才会相等,而对于HashMap来说,相等的条件则是:对比两个key的hashCode和equals。
  • IdentityHashMap不是Map的通用实现,它有意违反了Map的常规协定。并且IdentityHashMap允许key和value都为null。
  • 同HashMap,IdentityHashMap也是无序的,并且该类不是线程安全的,如果要使之线程安全,可以调用Collections.synchronizedMap(new IdentityHashMap(…))方法来实现。
————————

1、 Overview

The hash table is used to implement the interface. When comparing keys (and values), reference equality is used to replace object equality. In other words, in, two key sums are considered equal if and only if () (in a normal implementation (such as), two key sums are considered equal if and only if the following conditions are met: ().

IdentityHashMap
Map
IdentityHashMap
k1==k2
k1
k2
Map
HashMap
k1
k2
k1==null ? k2==null : e1.equals(e2))

This kind of implementation is not universal! When this class implements an interface, it intentionally violates a conventional convention that enforces the use of methods when comparing objects. Semantic equivalence is only required in rare cases.

Map
Map
Map
equals

2、 Source code analysis

2.1 properties

/**
 * 无参数构造函数使用的初始容量。一定是2的幂。
 * 值32对应于(指定的)预期最大大小21,给定的负载系数为2/3。
 */
private static final int DEFAULT_CAPACITY = 32;

/**
 * 最小容量,如果隐式指定一个较低的值,则使用
 * 由两个带有参数的构造函数组成。 给定2/3的负载系数,值4对应于预期的最大大小2。 必须是2的幂。
 */
private static final int MINIMUM_CAPACITY = 4;

/**
 * 最大容量,如果隐式指定了更高的值,则使用的最大容量
 * 由任何一个带参数的构造函数。必须是2的幂且 <= 1<<29。
 *
 * 事实上,该Map最多只能有MAXIMUM_CAPACITY-1个元素,因为它必须有一个key等于null的位置,
 * 这是为了避免get,put,remove方法的无限循环
 */
private static final int MAXIMUM_CAPACITY = 1 << 29;

/**
 * 对象数组table,根据需要调整大小。 长度必须始终为2的幂。
 * 注意:是Object对象数组;其他的 Map 都是Entry<K,V>或者Node<K,V>的类结构
 */
transient Object[] table; // non-private to simplify nested class access

/**
 * map中键值对的数量
 */
int size;

/**
 * 修改的数量,以支持 fast-fail 的迭代器
 */
transient int modCount;

/**
 * 存储键为null的key,如果键为null,实际用NULL_KEY存储
 */
static final Object NULL_KEY = new Object();

Interestingly, the other in the previous analysis are either arrays or arrays, but the object array is used in. This determines that its internal, method storage and key value pairs will be more special (the array index is even, the key is stored, and the index is odd, the value is stored)`

map
table
Entry<K,V>[]
Node<K,V>[]
IdentityHashMap
Object[]
put
get
table
key
value

Note: the loading factor is.

IdentityHashMap
2/3

2.2 construction method

//默认构造函数,容量为32,加载因子为2/3,最多可存储32*2/3=21个键值对
public IdentityHashMap() {
    init(DEFAULT_CAPACITY);
}

//根据指定容量构造
public IdentityHashMap(int expectedMaxSize) {
    if (expectedMaxSize < 0)
        throw new IllegalArgumentException("expectedMaxSize is negative: "
                                           + expectedMaxSize);
    init(capacity(expectedMaxSize));
}

//返回一个介于MINIMUM_CAPACITY和MAXIMUM_CAPACITY,且大于3*expectedMaxSize/2的值
//如果该值不存在,返回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));
}

//初始化内部存储数组table,table数组大小为参数initCapacity的两倍
//为何是两倍?因为这是包括了键和值,刚好两倍
private void init(int initCapacity) {
    table = new Object[2 * initCapacity];
}

//通过指定map初始化
public IdentityHashMap(Map<? extends K, ? extends V> m) {
    this((int) ((1 + m.size()) * 1.1));
    putAll(m);
}

2.3 put () method

This method adds the specified pair to the array. If the corresponding pair already exists, the corresponding pair will be updated. This method returns the previous corresponding.

key-value
table
key
value
key
value
/**
 * 在此标识哈希映射中关联指定值与指定键。如果映射以前包含了一个此键的映射关系,那么将替换旧值。
 *
 * @param key 要将指定值关联到的键
 * @param value 要关联到指定键的值
 * @return 返回与 key 相关联的先前值,如果 key 没有映射关系,则返回 null(返回 null 可能还表示映射以前将 null 与指定键关联)
 */
public V put(K key, V value) {
    //key = null的处理
    final Object k = maskNull(key);
    //retryAfterResize是java label标签,用于循环代码块之前
    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        // 计算键在数组中的位置,结果一定是偶数
        int i = hash(k, len);

        for (Object item; (item = tab[i]) != null;
            // 线性探测法 解决 hash 冲突;每次递增2
            // 找到下一个 key的位置,即 (i + 2 < len ? i + 2 : 0)
            i = nextKeyIndex(i, len)) {
            // 使用 == 比较键对象,如果为true,新值替换旧值
            if (item == k) {
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }
        //键值对数量加1
        final int s = size + 1;
        // Use optimized form of 3 * s.使用3 * s的优化形式。
        // Next capacity is len, 2 * current capacity.
        // 如果 map 中键值对的数目size * 3 大于 table 数组的长度 len,则触发扩容操作
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;
        //修改次数+1
        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

This method finds the corresponding key value pair. If it already exists, replace it and return the old one. Before adding key value pairs, judge whether to reallocate the size of the array. Reassign if necessary.

key
value

The method of is actually a circular call method, which will not be explained.

IdentityHashMap
putAll
put

2.3.1 hash () method

//返回对象x的在table数组中的索引位置,结果一定是偶数。
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);
}

Call the method of the class

System
identityHashCode()
//无论给定对象的类是否覆盖hashCode(),都为给定对象返回与默认方法hashCode()返回的哈希码相同的哈希码。
public static native int identityHashCode(Object x);

2.3.2 nextKeyIndex()方法

//返回当前键索引的下一个索引,如果越过数组大小,返回数组位置0
private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}

2.3.3 resize() method

private boolean resize(int newCapacity) {
    //新数组的大小为参数的两倍
    int newLength = newCapacity * 2;
    Object[] oldTable = table;
    int oldLength = oldTable.length;
    if (oldLength == 2 * MAXIMUM_CAPACITY) { 
        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];
            //let gc
            oldTable[j] = null;
            oldTable[j+1] = null;
            //找到key在新数组的索引
            int i = hash(key, newLength);
            //找到不为空的索引位置
            while (newTable[i] != null)
                i = nextKeyIndex(i, newLength);
            //存储到新数组的位置
            newTable[i] = key;
            newTable[i + 1] = value;
        }
    }
    table = newTable;
    return true;
}

Method first determines the size of the new array, and then copies the elements of the old array to the new array.

resize

2.4 get() method

This method returns the value corresponding to the key.

public V get(Object key) {
    //如果key为null,取null键对应的key
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    // 获取 key 在 table 数组中的索引
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        //相等,返回数组下一个位置存储的值
        if (item == k)
            return (V) tab[i + 1];
        //下一个key的索引位置为null,意味着当前 map 中所有键对象均已被遍历,没有找到对应key
        if (item == null)
            return null;
        //遍历下一个key的索引位置
        i = nextKeyIndex(i, len);
    }
}

The storage principle can be found through this method. The key value pairs are stored in the internal array, and the two adjacent positions are and respectively. During the search process, if it is found that the key stored in the current location is not the key to be searched, the next () location will be polled, which is also the method to solve the conflict.

IdentityHashMap
Object[]
key
value
i + 2
IdentityHashMap

The method, implementation and implementation are basically the same and will not be described.

IdentityHashMap
containsKey
containsMapping
get

2.5 containsValue()方法

This method determines whether the specified value exists.

public boolean containsValue(Object value) {
    Object[] tab = table;
    for (int i = 1; i < tab.length; i += 2)
        if (tab[i] == value && tab[i - 1] != null)
            return true;
    return false;
}

The implementation of this method is very simple. The first storage location in the is, so the step size is from the beginning. Returns if the references are equal and the corresponding is not.

table
value
1
1
2
value
key
null
true

2.6 remove()方法

Because the collision is solved by linear detection, the data is stored continuously, so when a key is deleted from it, the linear detection relationship needs to be updated and maintained.

hash
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;
            // 该位置的键值对移除了,空出了位置,看后面是否有键值对要填补这个位置(有些键值对是因为线性探测导致其位置偏离了其hash值)
            // 维持 put、get 等方法依赖的线性探测关系
            closeDeletion(i);
            return oldValue;
        }
        if (item == null)
            return null;
        i = nextKeyIndex(i, len);
    }
}

Here we mainly look at the usefulness of the method. Method is called after deleting a key value pair. For example, if the element at the position is deleted, the method is called to update the element after the position to reduce address conflicts. The complex point is to consider that it is a circular array. The next key position of linear detection may be in front of the current empty key position:

closeDeletion
closeDeletion
i
closeDeletion
table

2.6.1 closeDeletion()方法

private void closeDeletion(int d) {
    // Adapted from Knuth Section 6.4 Algorithm R
    Object[] tab = table;
    int len = tab.length;
 
    Object item;
    // d 是当前空出来的键值对位置
    // i 是当前处理的键值对位置
    // 循环遍历,当key为null时退出循环
    for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
         i = nextKeyIndex(i, len) ) {

        /**
         * 以下测试会触发插槽i中的项目(散列在插槽r中)是否应占据d腾出的位置。 
         * 如果是这样,我们将其交换,然后在新腾出的i处继续d。 当我们在此运行结束时点击空插槽时,此过程将终止。 
         * 因为table 是循环数组,需要注意i<r 的情况。
         * */
        int r = hash(item, len);
        if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
            tab[d] = item;
            tab[d + 1] = tab[i + 1];
            tab[i] = null;
            tab[i + 1] = null;
            d = i;
        }
    }
}

The method is similar to the implementation of this method and will not be described.

IdentityHashMap
removeMapping

2.7 clear () method

The method is simple, traversing the array and setting the value of the array element to.

clear
table
null
public void clear() {
    modCount++;
    Object[] tab = table;
    for (int i = 0; i < tab.length; i++)
        tab[i] = null;
    size = 0;
}

2.8 迭代器-IdentityHashMapIterator

Iterators are implemented by abstract inner classes

IdentityHashMap
IdentityHashMapIterator
private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
    //当前位置
    int index = (size != 0 ? 0 : table.length); 
    //迭代器的快速失败机制
    int expectedModCount = modCount; 
    //最后一个返回的位置,删除的时候也是删除该位置的值
    int lastReturnedIndex = -1; 
    //这个参数是为了避免无效计算
    boolean indexValid; 
    Object[] traversalTable = table; 

    //哈希表是否还有下一个元素
    public boolean hasNext() {
        Object[] tab = traversalTable;
        for (int i = index; i < tab.length; i+=2) {
            Object key = tab[i];
            if (key != null) {
                //更新当前位置并返回true
                index = i;
                return indexValid = true;
            }
        }
        //到这,说明已经没有更多元素了
        index = tab.length;
        return false;
    }
    //返回下一个索引
    protected int nextIndex() {
        //迭代器的快速失败机制,说明有其他线程并发修改了该哈希表
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (!indexValid && !hasNext())
            throw new NoSuchElementException();
        //调用nextIndex方法后,设置indexValid为不可用,也就是说,不能连续调用nextIndex方法
        indexValid = false;
        lastReturnedIndex = index;
        index += 2;
        return lastReturnedIndex;
    }
    //删除当前位置的键值对后,重新调整后面的元素,减少冲突
    public void remove() {
        if (lastReturnedIndex == -1)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        expectedModCount = ++modCount;
        int deletedSlot = lastReturnedIndex;
        lastReturnedIndex = -1;
        index = deletedSlot;
        indexValid = false;
        Object[] tab = traversalTable;
        int len = tab.length;
        int d = deletedSlot;
        Object key = tab[d];
        tab[d] = null;      
        tab[d + 1] = null;
        if (tab != IdentityHashMap.this.table) {
            IdentityHashMap.this.remove(key);
            expectedModCount = modCount;
            return;
        }

        size--;

        Object item;
        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) {
            int r = hash(item, len);
            if ((i < r && (r <= d || d <= i)) ||
              (r <= d && d <= i)) {

                if (i < deletedSlot && d >= deletedSlot &&
                    traversalTable == IdentityHashMap.this.table) {
                    int remaining = len - deletedSlot;
                    Object[] newTable = new Object[remaining];
                    System.arraycopy(tab, deletedSlot,
                             newTable, 0, remaining);
                    traversalTable = newTable;
                    index = 0;
                }

                tab[d] = item;
                tab[d + 1] = tab[i + 1];
                tab[i] = null;
                tab[i + 1] = null;
                d = i;
            }
        }
    }
}

3、 Summary

  • 对于要保存的key,k1和k2,当且仅当k1 == k2的时候,IdentityHashMap才会相等,而对于HashMap来说,相等的条件则是:对比两个key的hashCode和equals。
  • IdentityHashMap不是Map的通用实现,它有意违反了Map的常规协定。并且IdentityHashMap允许key和value都为null。
  • 同HashMap,IdentityHashMap也是无序的,并且该类不是线程安全的,如果要使之线程安全,可以调用Collections.synchronizedMap(new IdentityHashMap(…))方法来实现。