IdentityHashMap 从它的名字上可以看出来用于表示唯一的 HashMap,但是分析了其源码,发现其数据结构与 HashMap 使用的数据结构完全不同。
01、摘要
在集合系列的第一章,咱们了解到,Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。
应该有很多人不知道 IdentityHashMap 的存在,其中不乏工作很多年的 Java 开发者,本文主要从数据结构和算法层面,探讨 IdentityHashMap 的实现。
02、简介
IdentityHashMap 的数据结构很简单,底层实际就是一个 Object 数组,但是在存储上并没有使用链表来存储,而是将 K 和 V 都存放在 Object 数组上。
当添加元素的时候,会根据 Key 计算得到散列位置,如果发现该位置上已经有改元素,直接进行新值替换;如果没有,直接进行存放。当元素个数达到一定阈值时,Object 数组会自动进行扩容处理。
打开 IdentityHashMap 的源码,可以看到 IdentityHashMap 继承了 AbstractMap 抽象类,实现了 Map 接口、可序列化接口、可克隆接口。
1 |
|
可以看到类的底层,使用了一个 Object 数组来存放元素;在对象初始化时,IdentityHashMap 容量大小为64
;
1 |
|
1 |
|
03、常用方法介绍
3.1、put方法
put 方法是将指定的 key, value 对添加到 map 里。该方法首先会对map做一次查找,通过==
判断是否存在key
,如果有,则将旧value
返回,将新value
覆盖旧value
;如果没有,直接插入,数组长度+1
,返回null
。
源码如下:
1 |
|
maskNull 函数,判断 key 是否为空
1 |
|
hash 函数,通过 key 获取 hash 值,结合数组长度通过位运算获取数组散列下标
1 |
|
nextKeyIndex 函数,通过 hash 函数计算得到的数组散列下标,进行加2;因为一个 key、value 都存放在数组中,所以一个 map 对象占用两个数组下标,所以加2。
1 |
|
resize 函数,通过数组长度,进行扩容处理,扩容之后的长度为当前长度的2倍
1 |
|
3.2、get方法
get 方法根据指定的 key 值返回对应的 value。同样的,该方法会循环遍历数组,通过==
判断是否存在key
,如果有,直接返回value,因为 key、value 是相邻的存储在数组中,所以直接在当前数组下标+1
,即可获取 value;如果没有找到,直接返回null
。
值得注意的地方是,在循环遍历中,是通过==
判断当前元素是否与key
相同,如果相同,则返回value
。咱们都知道,在 java 中,==
对于对象类型参数,判断的是引用地址
,确切的说,是堆内存地址,所以,这里判断的是key
的引用地址是否相同,如果相同,则返回对应的 value;如果不相同,则返回null
。
源码如下:
1 |
|
3.3、remove方法
remove 的作用是通过 key 删除对应的元素。该方法会循环遍历数组,通过==
判断是否存在key
,如果有,直接将key
、value
设置为null
,对数组进行重新排列,返回旧 value。
源码如下:
1 |
|
closeDeletion 函数,删除该元素后,需要把原来有冲突往后移的元素移到前面来,对数组进行重写排列;
1 |
|
04、总结
-
IdentityHashMap
的实现不同于HashMap
,虽然也是数组,不过IdentityHashMap
中没有用到链表,解决冲突的方式是计算下一个有效索引,并且将数据key
和value
紧挨着存在map
中,即table[i]=key
、table[i+1]=value
; -
IdentityHashMap
允许key
、value
都为null
,当key
为null
的时候,默认会初始化一个Object
对象作为key
; -
IdentityHashMap
在保存、删除、查询数据的时候,以key
为索引,通过==
来判断数组中元素是否与key
相同,本质判断的是对象的引用地址,如果引用地址相同,那么在插入的时候,会将value
值进行替换;
IdentityHashMap 测试例子:
1 |
|
输出结果:
1 |
|
尽管key
的内容是一样的,但是key
的堆地址都不一样,所以在插入的时候,插入了4条记录。
05、参考
1、JDK1.7&JDK1.8 源码