Java中的Map【十】IdentityHashMap类

朴灿烈づ我的快乐病毒、 2021-09-21 08:32 426阅读 0赞

**         所使用的jdk版本为1.8.0\_172版本**，先看一下IdentityHashMap<K,V> 在JDK中Map的UML类图中的主要继承实现关系：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70][]

# 概述 #

IdentityHashMap 利用哈希表实现 Map 接口，比较键（和值）时使用引用相等性代替对象相等性。换句话说，在 IdentityHashMap 中，当且仅当 (k1==k2) 时，才认为两个键 k1 和 k2 相等（在正常 Map 实现（如 HashMap）中，当且仅当满足下列条件时才认为两个键 k1 和 k2 相等：(k1==null ? k2==null : e1.equals(e2))）。

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

**      IdentityHashMap的实现是不同步的。**

show with code :

public static void main(String[] args) {
            Map<String, Integer> hashMap = new HashMap<>();
            hashMap.put(new String("one"), 1);
            hashMap.put(new String("one"), 2);
            hashMap.put(new String("one"), 3);
            System.out.println("hashMap:");
            System.out.println(hashMap);
    
            Map<String, Integer> identityHashMap = new IdentityHashMap<>();
            identityHashMap.put(new String("one"), 1);
            identityHashMap.put(new String("one"), 2);
            identityHashMap.put(new String("one"), 3);
            System.out.println("identityHashMap:");
            System.out.println(identityHashMap);
        }

程序输出结果：

hashMap:
    {one=3}
    identityHashMap:
    {one=2, one=3, one=1}

# 数据结构 #

public class IdentityHashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, java.io.Serializable, Cloneable
    {
        /**
         * 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.
         */
        /**
         * 无参数构造函数使用的初始容量。一定是2的幂。
         * 值32对应于（指定的）预期最大大小21，给定的负载系数为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.
         */
        /**
         * 最小容量，如果隐式指定一个较低的值，则使用
         * 由两个带有参数的构造函数组成。 给定2/3的负载系数，值4对应于预期的最大大小2。 必须是2的幂。
         */
        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()
         */
        /**
         * 最大容量，如果隐式指定了更高的值，则使用的最大容量
         * 由任何一个带参数的构造函数。必须是2的幂且 <= 1<<29。
         *
         * 事实上，该Map最多只能有MAXIMUM_CAPACITY-1个元素，因为它必须有一个key等于null的位置，
         * 这是为了避免get,put,remove方法的无限循环
         */
        private static final int MAXIMUM_CAPACITY = 1 << 29;
    
        /**
         * The table, resized as necessary. Length MUST always be a power of two.
         */
        /**
         * 对象数组table，根据需要调整大小。 长度必须始终为2的幂。
         * 注意：是Object对象数组；其他的 Map 都是Entry<K,V>或者Node<K,V>的类结构
         */
        transient Object[] table; // non-private to simplify nested class access
    
        /**
         * The number of key-value mappings contained in this identity hash map.
         *
         * @serial
         */
        /** map中键值对的数量 */
        int size;
    
        /**
         * The number of modifications, to support fast-fail iterators
         */
        /**
         * 修改的数量，以支持 fast-fail 的迭代器
         */
        transient int modCount;

有趣的是之前分析的其它 map 中的 table，要么是 Entry<K,V>\[\] 数组，要么是Node<K,V>\[\] 数组，但在IdentityHashMap中使用的是 Object\[\] 对象数组。这就决定它内部 put 、 get 方法存、取键值对时，会比较特殊一些（table 数组索引为偶数存储的是键key，索引为奇数存储的是值value）。

# 实现原理 #

## V put(K key, V value) ##

/**
         * 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>.)
         *         返回与 key 相关联的先前值，如果 key 没有映射关系，则返回 null（返回 null 可能还表示映射以前将 null 与指定键关联）
         * @see     Object#equals(Object)
         * @see     #get(Object)
         * @see     #containsKey(Object)
         */
        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;
                    }
                }
    
                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;
    
                modCount++;
                tab[i] = k;
                tab[i + 1] = value;
                size = s;
                return null;
            }
        }

可以看出，IdentityHashMap内部的数组Object \[\]table 是交替存储键对象和值对象的，偶数索引存键，奇数索引存值。这里需要注意在 hash 时，使用的 hashCode 是从 System.identityHashCode(x)  返回的:

/**
         * Returns index for Object x.
         * 返回对象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);
        }

/**
         * 无论给定对象的类是否覆盖hashCode（），都为给定对象返回与默认方法hashCode（）返回的哈希码相同的哈希码。
         * null 对象返回的是 0
         *
         * @param x object for which the hashCode is to be calculated
         * @return  the hashCode
         * @since   JDK1.1
         */
        public static native int identityHashCode(Object x);

比如我们知道 Integer 、String类重写了 hashCode 方法，identityHashCode 方法在计算hashCode时，都会使用原生Object类里面的hashCode 方法，而不是Integer 、String类重写的 hashCode 方法：

public static void main(String[] args) {
            System.out.println(System.identityHashCode(new Integer(1)));
            System.out.println(new Integer(1).hashCode());
    
            System.out.println(System.identityHashCode(new String("A")));
            System.out.println(new String("A").hashCode());
            System.out.println(new String("A").hashCode());
        }

运行结果：

1627674070
    1
    1360875712
    65
    65

## V get(Object key) ##

public V get(Object 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);
            }
        }

## V remove(Object key) ##

因为采用线性探测解决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 方法简单列一下，在纸上画一下图比较好理解，复杂点就是要考虑 table 是循环数组，线性探测的下一个键位置可能会在当前空出来的键位置的前面：

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;
                }
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIyMDc2MzQ1_size_16_color_FFFFFF_t_70]: /images/20210920/9131aebb15034c1fbc87f89c19449377.png