细读源码之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的执行结果。

举例说明:

细读源码之IdentityHashMap

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

细读源码之IdentityHashMap

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

2、IdentityHashMap使用举例

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

 细读源码之IdentityHashMap

 细读源码之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比较

细读源码之IdentityHashMap

 

4、IdentityHashMap源码分析

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

1.hash定位索引index

细读源码之IdentityHashMap

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

2.get查找

细读源码之IdentityHashMap

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

4.put方法

 细读源码之IdentityHashMap

 细读源码之IdentityHashMap

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方法中,部分代码如下:

细读源码之IdentityHashMap

细读源码之IdentityHashMap 

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

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

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

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

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

上一篇:C#删除字符串中的回车、换行、空格等特殊字符


下一篇:API