Java HashMap工作原理

微信扫一扫,分享到朋友圈

Java HashMap工作原理

基本知识

Map

HashMap中,有一个继承的接口Map<K,V>,Map接口实际就是 映射 ,通过键来获取值。在Java的官方注释中是这么描述的:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

这个的大致意思就是:将键映射到值的对象。映射不能包含重复的键;每个键最多可以映射到一个值。

哈希表/散列表

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

HashMap结构

HashMap结构实际上是由数组+链表+红黑树组成的,执行如下的代码:

HashMap<String, Integer> map = new HashMap<String, Integer>(64, 1);
map.put("aa", 1);
map.put("bb", 2);
map.put("cc", 3);
map.put("dd", 4);
map.put("ee", 5);
map.put("ff", 6);
map.put("gg", 7);
map.put("hh", 8);
map.put("ii", 9);
map.put("jj", 10);
map.put("kk", 10);
map.put("ll", 10);
map.put("mm", 10);
map.put("nn", 10);
map.put("oo", 10);
map.put("pp", 10);
map.put("qq", 10);
复制代码

可以的得到如下的内存结构:

红黑树:

链表:

HashMap的数据结构图:

重要参数

loadFactor

loadFactor是哈希表的负载因子,负载因子会影响到HashMap的扩容,负载因子越大,HashMap的碰撞越剧烈,但是resize越少;负载因子越小,HashMap碰撞概率越小,但是resize越多。

threshold

threshold是HashMap要扩容的阈值,在HashMap的源码中是这么描述的:

The next size value at which to resize (capacity * load factor)

这个代表着threshold是整个HashMap的 容量 * 负载因子 得出来的值。当容量大小等于这个阈值的时候,HashMap就会扩容。

重要方法

put方法

在HashMap中最常用的方法就是put方法了,put方法主要的作用就是将Key-Value插入到Map中,在HashMap中put方法的特点是:

  1. 可以重复插入;
  2. 插入的KEY和Value都可以为Null

HashMap put方法的大致思路是:

  1. 首先将Key的hashCode计算,得到对应的hash值;
  2. 判断HashMap里面的槽是不是空的,如果是空的就需要初始化HashMap里面槽的数量;
  3. 判断这个Key所对应的槽是否被占用,如果没有被占用,就将Key-Value生成一个新的节点,放到对应的槽中
  4. 如果这个槽被占用了,分成三步判断:
    4.1. 判断Key是否相同,如果相同则返回原有的Node,如果不相同则进行下面的判断;
    4.2. 判断节点是否属于树节点(TreeNode),如果属于,则添加到红黑树中;
    4.3. 如果不是树节点,则一定是链表的Node,遍历链表,如果链表长度大于等于7了,则将链表转换成为红黑树,否则则添加到链表中;
  5. 最后判断HashMap的大小是否大于阈值,如果大于,则进行扩容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 如果当前HashMap里面的存储数据的table是空的,或者table的大小是0,那么就初始化table
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果table里面对应这个Key的槽为空,就直接创建一个新的Node,添加到table中
tab[i] = newNode(hash, key, value, null);
else {
// 到这里已经证明table里面的槽已经被其他的Node占用了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 判断被占用的Node的Key和当前的Key是否为同一个,如果是同一个,则取出这个Node
e = p;
else if (p instanceof TreeNode)
// 判断这个Node节点是否是一个树节点,如果是的话,就把这个新的Key-Value添加到树中间去
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果都不是的话,则这个Node节点一定是一个链表节点
for (int binCount = 0; ; ++binCount) {
// 循环遍历链表
if ((e = p.next) == null) {
// 判断是否到了链表末尾,如果已经到了链表末尾,则创建一个新的Node
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 判断当前链表的长度是否大于等于构建树的阈值(7),如果大于等于,就将链表转换为红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 如果链表中有一个Node的Key和当前的Key相同,则直接break
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 如果不是创建模式或者原来的值为空,则直接把当前的值存放到这个Node的值上面
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 如果当前表的size大于HashTable的扩容阈值,则进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
复制代码

resize方法

整个resize主要分成两个大的模块,第一个是扩容: 计算出新的table的大小和新的阈值 ,第二个就是迁移: 将原有table里面的Node重新计算迁移后槽的位置 ,并迁移。

第一大块扩容的主要思路是:

  1. 判断当前的table里面的size是否大于0,如果大于0的话,就会判断当前的table里面的size是否超过了最大值,如果超过最大值,就不会再扩容,如果没有超过的话,就会将 原有的size扩大原来的两倍 ,并且判断扩容之后的size是否大于最大值,如果超过最大值就按照最大值来扩容。
  2. 如果当前table里面的size等于0的话,并且当前table里面的阈值大于0的时候,就会将原有的阈值设置为新的table的size大小。
  3. 如果两个条件都不满足的话,则会对新的table设置默认的size(16),和默认的阈值(16 * 0.75)
  4. 如果这个时候新的table的阈值为空,则会重新计算新的阈值

其实由此可以看得出来,扩容的主要思想就是, 只要没有超过定义的最大值,那么每次扩容都是按照两倍的大小来扩容

代码如下:

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 判断现在的table的size是否大于0,如果大于0了才进行扩容操作
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果现在table的size已经大于了最大容量,则不在扩容,任由table去碰撞
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 将新的table的size变成原有的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 如果新扩充的tablesize小于最大容量的话,并且现在的table的size大于默认的初始容量的话,
// 就会将新的table的阈值扩充为原来的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果现在的table的size等于0,并且现在的table的阈值大于0,
// 就将新的table的size大小设置成和现在的table阈值一样
newCap = oldThr;
else {               // zero initial threshold signifies using defaults
// 如果都不是的话,则按照默认大小设置
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 如果新的table的阈值等于0的话,则计算出新的阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
复制代码

第二大块迁移的主要思路是:

首先了解一点,在HashMap中确定槽的位置是通过Key的Hash值和table的size – 1做 按位与 运算得到的((size – 1) & hash)

其次了解的第二点是,HashMap的容量始终为2的幂次

所以有个十分有意思的现象就是:在扩容的时候,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置,如图所示:

所以在扩容迁移元素的时候,不需要重新计算hash值,直接判断新增的高位bit是0还是1就好了。如果是0则不需要移动,如果是1则移动到
原索引+oldCap

的槽位置

@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
// 循环遍历table
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 如果不是链表,就直接放到新计算出的槽
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 不需要迁移的链表定义
Node<K,V> loHead = null, loTail = null;
// 需要迁移的链表定义
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 循环遍历链表
next = e.next;
if ((e.hash & oldCap) == 0) {
// 判断链表是否需要迁移,如果为0则不需要迁移,加入不需要迁移的链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 不为0的时候需要迁移,加入需要迁移的链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// 将不需要迁移的链表放入原来索引的槽
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 将需要迁移的链表放入(原来索引 + oldCap)的槽
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
复制代码

get方法

get方法的大致思路是:

  1. 判断现在HashMap里面的table是否为空,以及要获取的key对应的槽是否为空,如果为空,就直接返回null;
  2. 如果都不为空,就判断槽里面的第一个node是不是想要找的key,如果是直接返回
  3. 如果第一个不是,就判断node节点是不是树节点,如果是,就直接去红黑树里面查找
  4. 如果也不是树节点,那就在链表里面循环查找

代码如下:

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断table是否为空,以及想要查找的key所对应的槽是否为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断这个槽的第一个节点是不是对应的这个key
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断这个槽的第一个节点是不是树节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 如果不是树节点,那么就用链表遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
复制代码

和JDK1.7的对比

  1. JDK1.7和JDK1.8最明显的一点是,插入链表的时候,在JDK1.7的时候,HashMap插入链表是采用的 头插法 ,而在JDK1.8,HashMap插入链表采用的是 尾插法 ,之所以这么改变的原因是因为,头插法的链表在HashMap的resize()过程中可能因为多线程导致的逆序,让 链表形成死循环
  2. 在JDK1.7的HashMap中,HashMap的数据结构是 数组 + 单向链表 ,在JDK1.8的HashMap中,采用的是 数组 + 单链表 + 红黑树 的数据结构。
  3. 在resize()过程中,JDK1.7和JDK1.8的差别主要在迁移时计算新的索引的位置,JDK1.7时,是 重新计算Key的hash值,然后用(size – 1) & hash得到新的索引位置 ,而JDK1.8时,是采用 判断高一个bit位的位值 ,如果高一位的位值 是0那么索引位置就不变 ,如果 是1那么就用原来的HashMap的size大小加上原有的索引位置(原索引+oldCap) ,这么改变的原因是为了降低rehash带来的开销。

关于HashMap的一些细节总结:

1. 在HashMap中链表在什么时候会转化成红黑树?

在put里面可以看到

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
复制代码

这个表示着 链表在大于等于7个 的时候,会将链表转化成为红黑树,在网络上的回答里面也大多是这样说的,但是还有一个细节要注意,在转换红黑树的时候,会去判断你当前HashMap的大小,如果 当前HashMap的大小小于64的时候,会直接帮当前的HashMap扩容,而不是先扩容 ,在HashMap里面将链表转化成为红黑树的的注释是这样:

Replaces all linked nodes in bin at index for given hash unless table is too small, in which case resizes instead.

这句话的大概意思是,会替换所有的链表节点,除非当前的表太小了,这样将会调整大小

2. 在HashMap中为什么容量要是2的幂次方?

第一点:在put的时候,如果直接对长度进行取模,那么运算的消耗比较大,所以选择了与(长度 – 1)的&运算,而如果HashMap的容量不是2的幂次方,那么会使原本需要分散的数据,分散不均匀,加剧了HashMap的碰撞

第二点:在HashMap的resize过程中,因为长度是2的幂次方,所以在迁移节点的时候,不需要重新计算节点对应槽的下标值,而如果不采用2的幂次方的长度的话,每次都需要重新计算对应节点的下标值,增加了性能的消耗

3. HashMap的特性?

第一点:键值对(key – value),在HashMap中所有的数据都是通过键值对来进行存储,同时,HashMap说明了无论是key还是value都是可以为null的。

第二点:分散,在HashMap中所有数据的存储都是分散的,所有数据的存储的位置都和插入顺序无关,而且随着时间的推移,节点可能移动。

参考资料

Java HashMap工作原理及实现

小岛秀夫:我不是先知 《死亡搁浅》没预测疫情

上一篇

HBO官方:想为《最后的生还者》剧集优化、补充剧情

下一篇

你也可能喜欢

Java HashMap工作原理

长按储存图像,分享给朋友