HashMap源码学习-基于JDK8

1. 定义

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
  • 实现了Cloneable接口
    即覆盖了函数clone(),能被克隆
  • 实现java.io.Serializable接口
    支持序列化,能通过序列化去传输

2. 介绍

结构实现

HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,当链表长度达到8,会转化成红黑树,以提升它的查询、插入效率
image

设计思路

  • Map<K,V>
    Map<K,V>是一种以键值对存储数据的容器,而HashMap则是借助了键值Key的hashcode值来组织存储,使得可以非常快速和高效地地根据键值key进行数据的存取
  • Entry<Key,Value>
    对于键值对<Key,Value>,HashMap内部会将其封装成一个对应的Entry<Key,Value>对象,即Entry<Key,Value>对象是键值对<Key,Value>的组织形式

  • 对于每个对象而言,JVM都会为其生成一个hashcode值。HashMap在存储键值对Entry<Key,Value>的时候,会根据Key的hashcode值,以某种映射关系,决定应当将这对键值对Entry<Key,Value>存储在HashMap中的什么位置上

  • 当通过Key值取数据的时候,然后根据Key值的hashcode,以及内部映射条件,直接定位到Key对应的Value值存放在什么位置,可以非常高效地将Value值取出。

  • 线程不安全的
  • 允许key为null,value为null
  • 遍历时无序
    其底层数据结构是数组称之为哈希桶,每个桶里面放的是链表,链表中的每个节点,就是哈希表中的每个元素。

因其底层哈希桶的数据结构是数组,所以也会涉及到扩容的问题。

当HashMap的容量达到threshold域值时,就会触发扩容。扩容前后,哈希桶的长度一定会是2的次方。
这样在根据key的hash值寻找对应的哈希桶时,可以用位运算替代取余操作,更加高效。

而key的hash值,并不仅仅只是key对象的hashCode()方法的返回值,还会经过扰动函数的扰动,以使hash值更加均衡。
因为hashCode()是int类型,取值范围是40多亿,只要哈希函数映射的比较均匀松散,碰撞几率是很小的。
但就算原本的hashCode()取得很好,每个key的hashCode()不同,但是由于HashMap的哈希桶的长度远比hash取值范围小,默认是16,所以当对hash值以桶的长度取余,以找到存放该key的桶的下标时,由于取余是通过与操作完成的,会忽略hash值的高位。因此只有hashCode()的低位参加运算,发生不同的hash值,但是得到的index相同的情况的几率会大大增加,这种情况称之为hash碰撞。 即,碰撞率会增大。

扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征,并存放在低位,因此在与运算时,相当于高低位一起参与了运算,以减少hash碰撞的概率。(在JDK8之前,扰动函数会扰动四次,JDK8简化了这个操作)

扩容操作时,会new一个新的Node数组作为哈希桶,然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中,相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大,可想而知,在哈希表的容量越大时,性能消耗越明显。

扩容时,如果发生过哈希碰撞,节点数小于8个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置。
因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即low位, 或者扩容后的下标,即high位。 high位= low位+原哈希桶容量
如果追加节点后,链表数量》=8,则转化为红黑树

由迭代器的实现可以看出,遍历HashMap时,顺序是按照哈希桶从低到高,链表从前往后,依次遍历的。属于无序集合。

3 .属性

DEFAULT_INITIAL_CAPACITY

初始容量,必须是2的倍数,默认是16 (1 << 4)

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

MAXIMUM_CAPACITY

最大所能容纳的key-value 个数,最大值是 1073 741 824(1 << 30)

1
static final int MAXIMUM_CAPACITY = 1 << 30;

DEFAULT_LOAD_FACTOR

默认的加载因子

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

TREEIFY_THRESHOLD

树化链表节点的阈值,当某个链表的长度大于或者等于这个长度,则扩大数组容量,或者数化链表

1
static final int TREEIFY_THRESHOLD = 8;

Node<K,V>

Node<K,V> 类是HashMap中的静态内部类,实现Map.Entry<K,V>接口。 定义了key键、value值、next节点,也就是说元素之间构成了单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

//每一个节点的hash值,是将key的hashCode 和 value的hashCode 异或得到的
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置新的value 同时返回旧value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

Node<K,V>[] table

存储数据的Node数组,长度是2的幂

The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two.

1
transient Node<K,V>[] table;

至此,HashMap存储的数据结构也就很清晰了:维护了一个数组,每个数组又维护了一个单向链表。之所以这么设计,考虑到遇到哈希冲突的时候,同index的value值就用单向链表来维护。

size

map中保存的键值对的数量

1
transient int size;

threshold

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

  • 容量*装载因子
  • threshold是HashMap判断size是否需要扩容的阈值:如果key-value的数量等于该值,则调用resize方法,扩大容量(2倍),同时修改threshold的值
1
int threshold;

loadFactor

装载因子

1
final float loadFactor;

4. 构造函数

无参构造函数

HashMap()

Constructs an empty {@code HashMap} with the default initial capacity

1
2
3
public HashMap() {  
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

DEFAULT_LOAD_FACTOR

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

指定初始化容量的构造函数

HashMap(int initialCapacity)

Constructs an empty {@code HashMap} with the specified initial capacity and the default load factor (0.75).

并不是指定的初始容量是多少,初始化之后的HashMap的容量就是多大,tableSizeFor()方法会把初始化的容量变成是2的次方数

1
2
3
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

指定初始化容量 以及 加载因子

HashMap(int initialCapacity, float loadFactor)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public HashMap(int initialCapacity, float loadFactor) {
//边界处理
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量最大不能超过2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加载因子不能为负数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置阈值 1.>= 初始化容量 2. 是2的n次方
this.threshold = tableSizeFor(initialCapacity);
}

tableSizeFor(int cap)

  • 根据期望容量cap,返回2的n次方形式的 哈希桶的实际容量 length
  • 返回值一般会大于等于cap
1
2
3
4
5
6
7
8
9
10
11
static final int tableSizeFor(int cap) {
//经过下面的 或 和位移 运算, n最终各位都是1。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判断n是否越界,返回 2的n次方作为 table(哈希桶)的阈值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
  1. 给定的cap减1
1
int n = cap - 1

如果cap本来就是2的幂次方,经过后续的未操作的,cap将会变成2 * cap,是不符合我们预期的

  1. n无符号右移1位
1
n |= n >>> 1
  • 即n二进制最高位的1右移一位,导致的结果是n二进制的高2位值为1
  • 目前n的高1~2位均为1
  1. n继续无符号右移2位
1
n |= n >>> 2
  • 导致n二进制表示高3~4位经过运算值均为1
  • 目前n的高1~4位均为1
  1. n继续无符号右移4位
1
n |= n >>> 4
  • 导致n二进制表示高5~8位经过运算值均为1;
  • 目前n的高1~8位均为1。
  1. n继续无符号右移8位。
1
n |= n >>> 8
  • n | (n >>> 8),导致n二进制表示高9~16位经过运算值均为1
  • 目前n的高1~16位均为1
  1. n继续无符号右移16位。
1
n |= n >>> 16
  • 导致n二进制表示高17~32位经过运算值均为1
  • 目前n的高1~32位均为1

可以看出,无论给定cap(cap < MAXIMUM_CAPACITY )的值是多少,经过以上运算,其值的二进制所有位都会是1。再将其加1,这时候这个值一定是2的幂次方。当然如果经过运算值大于MAXIMUM_CAPACITY,直接选用MAXIMUM_CAPACITY。
这里可以举个栗子,假设给定的cap的值为20。

int n = cap - 1; —> n = 19(二进制表示:0001 0011)

n |= n >>> 1;

1
2
3
n             ->  0001 0011
n >>> 1 -> 0000 1001
n |= n >>> 1 -> 0001 1011

n |= n >>> 2;

1
2
3
n             ->  0001 1011
n >>> 2 -> 0000 1101
n |= n >>> 2 -> 0001 1111此时n所有位均为1,后续的位操作均不再改变n的值。

1
n + 1        ->  0010 0000 (32)

最终,tableSizeFor(20)的结果为32(2^5)。
至此tableSizeFor保证cap为2的幂次方

为什么cap要保持为2的幂次方?

  • index怎么算
    HashMap中存储数据table的index是由key的Hash值决定的
  • Hash怎么算
    在JDK1.8中,HashMap中key的Hash值由Hash(key)方法(后面会详细分析)计算得来
    在HashMap存储数据的时候,我们期望数据能够均匀分布,以避免哈希冲突。自然而然我们就会想到去用%取余的操作来实现我们这一构想
  • 优化
    取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作
1
2
3
4
5
index = e.hash & (newCap - 1) 

等同于:

index = e.hash % newCap

采用二进制位操作&,相对于%,能够提高运算效率

参数是map 的构造函数

将另一个map m 里的所有元素加入表中

HashMap(Map<? extends K, ? extends V> m)

1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

  • 将另一个Map的所有元素加入表中,参数evict初始化时为false,其他情况为true
  • 用get() put()
  1. 判断表是否为空
    1.1 为空表,计算阈值
    1.2 非空表,判断是否需要扩容
  2. 遍历 m 依次将元素加入当前表中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();//m的元素数量
if (s > 0) {//元素数量大于0
//如果当前表是空的
if (table == null) { // pre-size
//根据m的元素数量和当前表的加载因子,计算出阈值
float ft = ((float)s / loadFactor) + 1.0F;
//修正阈值的边界
//不能超过MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果新的阈值大于当前阈值
if (t > threshold)
//返回一个>=新的阈值且满足2的n次方的阈值
threshold = tableSizeFor(t);
}
//如果当前元素表不是空的
else if (s > threshold)
resize();
//遍历 m 依次将元素加入当前表中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

resize()

时机

当前的HashMap的大小大于阀值时,HashMap会对此HashMap的容量进行扩充,即对内部的Entry[] table 数组进行扩充

要求

HashMap对容量(Entry[] table数组长度) 有两点要求:

  1. 容量的大小应当是 2的N次幂
  2. 当容量大小超过阀值时,容量扩充为当前的一倍

步骤

容量扩充分为以下几个步骤:

  1. 确定新的阈值和容量
    1.1 旧容量>0
    没有超过最大容量,则新表容量、门限为旧表2倍
    1.2 旧容量=0,旧门限>0
    旧表门限值赋值给新表容量,新表阈值=容量 * 负载因子
    1.3 旧容量=0,旧门限=0
    则新的容量和门限为默认的容量(16)和门限值(12)
  2. 将当前哈希桶中的所有节点转移到新的哈希桶中
    旧的链表不空,且链表中有元素
    2.1 链表中就一个元素(没有发生哈希碰撞)
    直接将这个元素放置在新的哈希桶里
    2.2 发生过哈希碰撞 ,且节点数超过8个
    转化成了红黑树
    2.3 发生过哈希碰撞,节点数小于8个
    • 根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置
    • 因为扩容是容量翻倍,原链表上的每个节点,现在可能存放在原来的下标low位; 或者扩容后的下标high位
    • high位= low位+原哈希桶容量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //1.1 -------------------------------------------
if (oldCap >= MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
//修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return oldTab;//返回当前哈希桶,不再扩容
}
// 没超过最大值,就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}//表是空的,但有阈值。代表是初始化时指定了容量、阈值的情况
else if (oldThr > 0) // 1.2 -----------------------
newCap = oldThr;
else {// 1.3----------------------------------------
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//根据新表容量 和 加载因子 求出新的阈值
//进行越界修复
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //更新哈希桶引用
//2.-----------------------------------------
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果当前桶中有元素,则将链表赋值给e
oldTab[j] = null;//将原哈希桶置空以便GC
if (e.next == null) //2.1--------------------
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//2.2-----------------------
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //2.3------------------------------------
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) {
//给头尾节点指针赋值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}//高位索引
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}//循环直到链表结束
} while ((e = next) != null);
//将低位链表存放在原index处,
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

5. 增加—put

添加一个元素

put(K key, V value)

Associates the specified value with the specified key in this map.If the map previously contained a mapping for the key, the old value is replaced.

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

hash(K,V) 方法

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower.

  • HashMap中table的index是由Key的哈希值决定的
  • 而上面我们提到index的运算规则是e.hash & (newCap - 1)。由于newCap是2的幂次方,那么newCap - 1的高位应该全部为0。如果e.hash值只用自身的hashcode的话,那么index只会和e.hash低位做&操作。这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会增加哈希冲突的风险
  • HashMap并没有直接使用key的hashcode(),在计算key的哈希值的时候,用其自身hashcode值与其低16位做异或操作
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

@param
hash: hash for key
key :the key
value: the value to put
onlyIfAbsent: if true, don’t change existing value
evict: if false, the table is in creation mode.
return:previous value, or null if none

流程图和步骤参考自美团点评
对步骤语序逻辑有所调整

流程图

流程图

步骤

  1. 判断键值对数组table[i]是否为空或为null
    如果当前哈希表是空的,代表是初始化,则执行resize()进行扩容
  2. 根据键值key计算hash值得到插入的数组索引i
    • 如果table[i]==null,直接新建节点添加(index 是利用 哈希值 & 哈希桶的长度-1,替代模运算)转向⑥
    • 如果table[i]不为空,转向③
  3. 发生了哈希冲突
    判断table[i]的首个元素是否和key一样,相同指的是hashCode以及equals
    • 如果相同直接覆盖value
    • 否则转向④
  4. 判断table[i] 是否为treeNode,即table[i] 是否是红黑树
    • 如果是红黑树,则直接在树中插入键值对
    • 否则转向⑤
  5. 遍历table[i],判断链表长度是否大于8
    • 大于8的话把链表转换为红黑树,在红黑树中执行插入操作
    • 否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可
  6. 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容

源码

在构造函数中最多也只是设置了initialCapacity、loadFactor的值,并没有初始化table,table的初始化工作是在put方法中进行的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
inal V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.----------------------------------------空表?
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.----------------------------------------数组索引
if ((p = tab[i = (n - 1) & hash]) == null)
//3.----------------------------------------
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果哈希值相等,key也相等,则是覆盖value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4.----------------------------------------
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//5.----------------------------------------
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到尾部,追加新节点到尾部
p.next = newNode(hash, key, value, null);
//如果追加节点后,链表数量>=8,则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key相同则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null,说明有需要覆盖的节点
if (e != null) { // existing mapping for key
//则覆盖节点值,并返回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//这是一个空实现的函数,用作LinkedHashMap重写使用
afterNodeAccess(e);
return oldValue;
}
}
//6.------------------------------------
++modCount;
if (++size > threshold)
resize();
//这是一个空实现的函数,用作LinkedHashMap重写使用
afterNodeInsertion(evict);
return null;
}

6. 删除—remove

remove(key)

执行逻辑:
1)根据key得到key的hash值
2)根据key 和hash值定位需要remove的Node
3) 将Node从对应的链表移除,然后再将Node 前后的节点对接起来
4)返回被移除 的Node
5)key-value的数量减一,修改次数加一

##

小总结:

  • 运算尽量都用位运算代替,更高效
  • 对于扩容导致需要新建数组存放更多元素时,除了要将老数组中的元素迁移过来,也记得将老数组中的引用置null,以便GC
  • 取下标 是用 哈希值 与运算 (桶的长度-1) i = (n - 1) & hash。 由于桶的长度是2的n次方,这么做其实是等于 一个模运算。但是效率更高
  • 扩容时,如果发生过哈希碰撞,节点数小于8个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置
  • 因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即low位, 或者扩容后的下标,即high位。 high位= low位+原哈希桶容量
  • 利用哈希值 与运算 旧的容量 ,if ((e.hash & oldCap) == 0),可以得到哈希值去模后,是大于等于oldCap还是小于oldCap,等于0代表小于oldCap,应该存放在低位,否则存放在高位。这里又是一个利用位运算 代替常规运算的高效点
  • 如果追加节点后,链表数量》=8,则转化为红黑树
  • 插入节点操作时,有一些空实现的函数,用作LinkedHashMap重写使用。

参考文章
Java集合干货系列-(三)HashMap源码解析
Java官方文档
美团技术团队Java 8系列之重新认识HashMap
源码分析之 HashMap
[Java基础要义] HashMap的设计原理和实现分析

> >