细读源码之IdentityHashMap

本文主要是介绍细读源码之IdentityHashMap，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

应该有很多人不知道IdentityHashMap的存在，包括作者本人，也从来没有在日常工作中使用过它。

实际上IdentityHashMap是Jdk自带的集合类，可以在一些特定的场景下使用。

相比HashMap而言，IdentityHashMap的结构更简单，更容易维护。

本文将从以下几个方面讲解：

1. Java中与Hash相关的操作

2. IdentityHashMap使用举例

3. IdentityHashMap和HashMap对比

4. IdentityHashMap源码分析

5. IdentityHashMap使用场景

1、Java中与Hash相关的操作

A.等于(==)操作

JAVA中的==操作符是来判断两个对象是否是同一个对象，返回结果通过下面三条规则进行确定：

1.对于两个空对象x == null并且y == null，则x == y返回true；

2.对于两个非空对象x,y，当且仅当x和y引用同一对象时，x == y才返回true；

3.对于空对象x和非空对象y，或者非空对象x和空对象y，x == y都返回false。

==操作强调的是，两个对象是否引用同一对象，更通俗的说，引用的对象在堆内存中地址是否相同。

B.equals比较

equals方法用来判断其他对象是否“等于”此对象，注意这里的等于是加了引号的，以区别上面讲解的"=="。equals强调的是逻辑上的相等，不要求比较的两个对象必须是同一对象，equals方法的实现要必须要满足以下几个特性：

1.自反性

对于任何非空的引用对象x，x.equals(x)应该返回true；

2.对称性

对于任何非空的引用对象x和y，当且仅当y.equals(x)返回true时，x.equals(y)才能返回true；

3.传递性

对于任何非空引用对象x、y和z，如果x.equals(y)返回true，y.equals(z)返回true，那么x.equals(z)也必须返回true；

4.一致性

对于任何非空的引用对象x和y，在equals中比较的字段没有被修改的前提下，任意多次调用x.equals(y)始终返回true或false；

5.null值处理

对于任何非空引用值x，x.equals(null)应返回false。

需要注意，当重写了hashCode方法时，通常都需要重写equals方法，以维护hashCode的约定：x.equals(y)返回true，那么x和y的hashCode值必须相等。

C. Object.hashCode方法

Object.hashCode返回对象的hash值。在Hash存储结构中，是以hashCode的值为基础，去定位在table中的位置。

hashCode方法的实现要满足下面约定：

1. 一次Java运行期间，在equals方法中比较的字段没有被修改的前提下，任意多次调用hashCode必须始终返回相同的整数；而一个Java程序的多次执行，hashCode不需要保持一致；

2. 对于任何非空引用对象x、y，如果x.equals(y)返回true，那么x.haseCode和y.hashCode返回值必须相等；

3. 对于任何非空引用对象x、y，如果x.equals(y)返回false，虽然不强制要求，x.haseCode和y.hashCode必须返回不同的值。但是我们需要知道，为不相等的对象生成不同的哈希值，可以提高Hash存储结构（如：HashMap）的执行效率。

D.System.identityHashCode方法

在不重写Object.hashCode方法时，System.identityHashCode和Object.hashCode返回的值相同，可以理解为System.identityHashCode是Object.hashCode方法的默认实现。

另外需要注意两点：

1.System.identityHashCode(null)始终返回0；

2.无论是否重写Object.hashCode，都不影响System.identityHashCode的执行结果。

举例说明：

 上面代码执行结果如下所示：

String类重写了Object.hashCode方法，所以value.hashCode与System.identityHashCode(value)返回的值不相等。

2、IdentityHashMap使用举例

下面通过一个例子，来说明IdentityHashMap的特性，代码如下：

上面代码执行结果：

上面代码中put的4个key："1"，String.value(1)，String.value('1')和new String("1")，它们指向的内存中的不同的地址空间，是4个不同对象，使用==进行判等，两两互不相等。

而String类重写了hashCode和equals方法，这4个对象hashCode都返回相同的值，两两执行equals方法，返回的都是true。

当HashMap对4个key执行put操作时，使用hashCode作为hash值，使用equals进行相等判断，后3个put操作，最终执行的是更新操作，最后HashMap中只有1项。

而IdentityHashMap对4个key执行put操作时，使用System.identityHashCode作为hash值，使用==进行相等判断，后3个put操作，最终执行的是插入操作，最后IdentityHashMap中有4项。

以上就是HashMap和IdentityHashMap在功能上最本质的差别。

3、IdentityHashMap和HashMap比较

4、IdentityHashMap源码分析

IdentityHashMap和HashMap都是实现了Hash表这种数据结构，下面主要将两者不同的地方拿来分析。

1.hash定位索引index

调用的是System.identityHashCode得到hash值，然后以此为基础去计算在table中的索引位置index。

2.get查找

IdentityHashMap的get方法比HashMap的get方法简单很多，一种只用3种情况：

1. item == k，找到了对应的key，将相应的value返回，value存在key右相邻的位置，返回tab[i + 1]；

2. item == null，根据hash定位到item为空，表示当前的key在table中不存在，直接返回null；

3. item != null && item != key，表示hash冲突发生，调用nextKeyIndex获取处理冲突后的index位置，然后重复上面的过程。

需要注意的是这里的判断是否相等操作使用的==，而不是equals方法。

3.nextKeyIndex处理hash冲突

IdentityHashMap处理冲突的方式是开发地址法中的线型再探测，当前的位置别占用后，就在右相邻的位置去找，而IdentityHashMap中一个key-value键值对，占用table的两个位置，所以这里的操作是加2，如果超出table大小，再从0开始。

4.put方法

IdentityHashMap的put方法也非常简单，调用hash方法，获取key在table的位置index，然后进行赋值操作，也是分成了3种情况：

1.item == k，找到了对应的key，value存在key右相邻的位置，对tab[i + 1]进行更新，并返回原来的值；

2.item == null，表示table中没有对应的key值，跳出for循环，执行tab[i] = k和tab[i + 1] = value进行新key的插入操作。个人觉得这里的扩容时机选择的不太好，好不容易找到的更新位置，因为扩容给整没了，还得再次重新计算，可以和HashMap一样，在更新后再扩容。

3.item != null && item != key，表示hash冲突发生，调用nextKeyIndex获取处理冲突后的index位置，然后重复上面的过程。

5、IdentityHashMap使用场景

当Hash存储结构Key的类型，没有重写hashCode和equals方法时，并且Hash结构中存储的数据较少，Hash冲突不严重的时候，就可以使用IdentityHashMap替换HashMap。

在JDK动态代理实现中，就使用了IdentityHashMap，作用是对传入的代理接口进行重复性验证，代码在Proxy.ProxyClassFactory.apply方法中，部分代码如下：

这里interfaceSet是IdentityHashMap类型，用来检查传入interfaces数组里面是不是有重复的项。

其中Key是Class类型，而Class类没有重写hashCode和equals方法，所以把IdentityHashMap替换为HashMap功能上没有任何问题。

但是这里IdentityHashMap的效果更好，因为动态代理出入的接口的个数非常少，产生冲突的概率非常小，结构更简单的IdentityHashMap在此场景下，就更加适用。

JAVA的集合框架，几乎是面试中的必考题，而Map结构又是重点中的重点。

预祝大家在面试中有个完美的发挥，拿到自己心意的Offer。

这篇关于细读源码之IdentityHashMap的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！