不積跬步,無以至千里
不積小流,無以成江海

0%

HashMap源码分析

相关概念

数组

数组具有遍历快,增删慢的特点。数组在堆中是一块连续的存储空间,遍历时数组的首地址是知道的(首地址=首地址+元素字节数 * 下标),所以遍历快(数组遍历的时间复杂度为O(1) );增删慢是因为,当在中间插入或删除元素时,会造成该元素后面所有元素地址的改变,所以增删慢(增删的时间复杂度为O(n) )。

链表

链表具有增删快,遍历慢的特点。链表中各元素的内存空间是不连续的,一个节点至少包含节点数据与后继节点的引用,所以在插入删除时,只需修改该位置的前驱节点与后继节点即可,链表在插入删除时的时间复杂度为O(1)。但是在遍历时,get(n)元素时,需要从第一个开始,依次拿到后面元素的地址,进行遍历,直到遍历到第n个元素(时间复杂度为O(n) ),所以效率极低。

HashMap

Hash表是一个数组+链表的结构,这种结构能够保证在遍历与增删的过程中,如果不产生hash碰撞,仅需一次定位就可完成,时间复杂度能保证在O(1)。 在jdk1.7中,只是单纯的数组+链表的结构,但是如果散列表中的hash碰撞过多时,会造成效率的降低,所以在JKD1.8中对这种情况进行了控制,当一个hash值上的链表长度大于8时,该节点上的数据就不再以链表进行存储,而是转成了一个红黑树。

hash碰撞:

hash是指,两个元素通过hash函数计算出的值是一样的,是同一个存储地址。当后面的元素要插入到这个地址时,发现已经被占用了,这时候就产生了hash冲突

hash冲突的解决方法:

开放定址法(查询产生冲突的地址的下一个地址是否被占用,直到寻找到空的地址),再散列法,链地址法等。hashmap采用的就是链地址法,jdk1.7中,当冲突时,在冲突的地址上生成一个链表,将冲突的元素的key,通过equals进行比较,相同即覆盖,不同则添加到链表上,此时如果链表过长,效率就会大大降低,查找和添加操作的时间复杂度都为O(n);但是在jdk1.8中如果链表长度大于8,链表就会转化为红黑树,时间复杂度也降为了O(logn),性能得到了很大的优化。

HashMap的继承图(盗图)


HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ,允许多条记录的值为 null 。HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap 方法使 HashMap 具有线程安全的能力,或者使用ConcurrentHashMap。

HashMap存储结构

源码分析

常量定义

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
//创建 HashMap 时未指定初始容量情况下的默认容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap 默认的负载因子(也叫填充比)
static final float DEFAULT_LOAD_FACTOR = 0.75f; //表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容
//用来确定何时将解决 hash 冲突的链表转变为红黑树,如果主干数组上的链表的长度大于8,链表转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
//用来确定何时将解决 hash 冲突的红黑树转变为链表,hash表扩容后,如果发现某一个红黑树的长度小于6,则会重新退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//当hashmap容量大于64时,链表才能转成红黑树,若是由于数组容量太小(小于64)导致的 hash 冲突太多,则不进行链表转变为红黑树操作,转为利用 resize() 函数对 hashMap 扩容
static final int MIN_TREEIFY_CAPACITY = 64;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//保存Node<K,V>节点的数组
transient Node<K,V>[] table;
//由 hashMap 中 Node<K,V> 节点构成的 set
transient Set<Map.Entry<K,V>> entrySet;
//Map中当前存储的元素数量
transient int size;
//阈值,用于判断是否需要扩容(threshold = 容量*负载因子)
int threshold;
//HashMap加载因子实际的大小
final float loadFactor;
//HashMap发生结构性变化的次数(注意 value 的覆盖不属于结构性变化)
transient int modCount;

构造方法

HashMap的构造方法有4种,主要涉及到的参数有,指定初始容量,指定填充比和用来初始化的Map

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
//构造函数1 指定初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
//指定的初始容量非负
if (initialCapacity < 0)
throw new IllegalArgumentException(Illegal initial capacity: +
initialCapacity);
//如果指定的初始容量大于最大容量,置为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充比为正
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(Illegal load factor: +
loadFactor);
/* tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂,若指定初始容量为9,则实际 hashMap 容量为16*/
 //注意此种方法创建的 hashMap 初始容量的值存在 threshold 中
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
}
//tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;// >>> 代表无符号右移
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//构造函数2 指定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//构造函数3 无参构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//构造函数4 用m的元素初始化散列映射 指定集合 转化为iHashMap
public HashMap(Map<!--? extends K, ? extends V--> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

数组里面每个地方都存了Key-Value这样的实例,在Java7叫Entry在Java8中叫Node。数组和链表组合构成的数据结构大概如下(偷图):


因为他本身所有的位置都为null,在put插入的时候会根据key的hash去计算一个index值。
就比如我put(”帅丙“,520),我插入了为”帅丙“的元素,这个时候我们会通过哈希函数计算出插入的位置,计算出来index是2那结果如下(偷图)。
hash(“帅丙”)= 2

我们都知道数组长度是有限的,在有限的长度里面我们使用哈希,哈希本身就存在概率性,就是”帅丙“和”丙帅“我们都去hash有一定的概率会一样,就像上面的情况我再次哈希”丙帅“极端情况也会hash到一个值上,那就形成了链表(偷图)。

每一个节点都会保存自身的hash、key、value、以及下个节点,我看看Node的源码。

下图是一位大神级别画的图,自己就不再造轮子了。客官请看

HashMap的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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
static final int hash(Object key) {
int h;
/*key 的 hash 值的计算是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
/*把Map<? extends K, ? extends V> m 中的元素插入到 hashMap 中,若 evict 为 false,代表是在创建 hashMap 时调用了这个函数,例如利用上述构造函数3创建 hashMap;若 evict 为true,代表是在创建 hashMap 后才调用这个函数,例如上述的 putAll 函数。*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
/*如果是在创建 hashMap 时调用的这个函数则 table 一定为空*/
if (table == null) { // pre-size
//根据待插入的map 的 size 计算要创建的 hashMap 的容量。
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//把要创建的 hashMap 的容量存在 threshold 中
if (t > threshold)
threshold = tableSizeFor(t);
}
//判断待插入的map 的 size,若size 大于threshold,则先进行resize()
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//实际也是调用 putVal 函数进行元素的插入
putVal(hash(key), key, value, false, evict);
}
}
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断数组是否为空,长度是否为0,是则进行扩容数组初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过hash算法找到数组下标得到数组元素,如果table的在(n-1)&hash的值为空则新建(注意确定插入位置所用的计算方法为 (n - 1) & hash,由于 n 一定是2的幂次,这个操作相当于hash % n )
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
////说明待插入位置存在元素
else {
Node<K,V> e; K k;
// 比较原来元素与待插入元素的 hash 值和 key 值,hash相等同时key相等,则直接覆盖(检查第一个Node,p是不是要找的值)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 该数组元素在链表长度>8后形成红黑树结构的对象,p为树结构已存在的对象
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 该数组元素hash相等,key不等,同时链表长度<8.进行遍历寻找元素,有就覆盖无则新建
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;//将p中的next赋值给p,即将链表中的下一个node赋值给p,
}
}
// 新值覆盖旧值
if (e != null) { // existing mapping for key //这个判断中代码作用为:如果添加的元素产生了hash冲突,那么调用put方法时,会将他在链表中他的上一个元素的值返回
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
// 判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// put方法中调用的putTreeVal函数
/*读懂这个函数要注意理解 hash 冲突发生的几种情况
1、两节点 key 值相同(hash值一定相同),导致冲突
2、两节点 key 值不同,由于 hash 函数的局限性导致hash 值相同,冲突
3、两节点 key 值不同,hash 值不同,但 hash 值对数组长度取模后相同,冲突
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点开始查找合适的插入位置(与二叉搜索树查找过程相同)
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1; //dir小于0,接下来查找当前节点左孩子
else if (ph < h)
dir = 1; // dir大于0,接下来查找当前节点右孩子
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//进入这个else if 代表 hash 值相同,key 相同
return p;
/*要进入下面这个else if,代表有以下几个含义:
1、当前节点与待插入节点 key 不同, hash 值相同
       2、k是不可比较的,即k并未实现 comparable<K> 接口
              (若 k 实现了comparable<K> 接口,comparableClassFor(k)返回的是k的 class,而不是 null)
  或者 compareComparables(kc, k, pk) 返回值为 0
              (pk 为空 或者 按照 k.compareTo(pk) 返回值为0,
              返回值为0可能是由于 k的compareTo 方法实现不当引起的,compareTo 判定相等,而上个 else if 中 equals 判定不等)*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在以当前节点为根的整个树上搜索是否存在待插入节点(只会搜索一次)
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
//若树中存在待插入节点,直接返回
return q;
}
// 既然k是不可比较的,那我自己指定一个比较方式
dir = tieBreakOrder(k, pk);
}

TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//找到了待插入的位置,xp 为待插入节点的父节点
          //注意TreeNode节点中既存在树状关系,也存在链式关系,并且是双端链表
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入节点后进行二叉树的平衡操作
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
static int tieBreakOrder(Object a, Object b) {
int d;
//System.identityHashCode()实际是利用对象 a,b 的内存地址进行比较
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
//put方法的treeifyBin()函数,链表转化为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果表为空或者表的长度小于树化的容量,resize()扩容而不是树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd是转换为树节点后桶中的头节点 tl记录上一个遍历的节点
TreeNode<K,V> hd = null, tl = null;
do {
//将hash位置处的数组中的每个节点包装成树节点,p记录当前遍历的节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
//循环将桶中每个节点替换为树节点,最终结果就是链表转换为双向链表,prev指向前一个节点,next指向后一个节点
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//将双向链表转化为红黑树
hd.treeify(tab);
}
}

基本过程如下:

  1. 检查数组是否为空,执行resize()扩充;在实例化HashMap时,并不会进行初始化数组
  2. 通过hash值计算数组索引,获取该索引位的首节点。
  3. 如果首节点为null(没发生碰撞),则创建新的数组元素,直接添加节点到该索引位(bucket)。
  4. 如果首节点不为null(发生碰撞),那么有3种情况
    ① key和首节点的key相同,覆盖old value(保证key的唯一性);否则执行②或③
    ② 如果首节点是红黑树节点(TreeNode),将键值对添加到红黑树。
    ③ 如果首节点是链表,进行遍历寻找元素,有就覆盖无则新建,将键值对添加到链表。添加之后会判断链表长度是否到达TREEIFY_THRESHOLD - 1这个阈值,“尝试”将链表转换成红黑树。
  5. 最后判断当前元素个数是否大于threshold,扩充数组。

HashMap的get(),取值过程

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
public V get(Object key) {
Node<K,V> e;
//实际上是根据输入节点的 hash 值和 key 值利用getNode 方法进行查找
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; //Entry对象数组
Node<K,V> first, e; //在tab数组中经过散列的第一个位置
int n; K k;
/*找到插入的第一个Node,方法是hash值和n-1相与,tab[(n - 1) & hash]*/
//也就是说在一条链上的hash值相同的
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 永远检查第一个node是不是要找的Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) //判断条件是hash值要相同,key值要相同
return first;
/*检查first后面的node*/
if ((e = first.next) != null) {
if (first instanceof TreeNode) // 树查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
/*遍历后面的链表,找到key值和hash值都相同的Node*/
do {
if (e.hash == hash && // 遍历链表
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

get方法中调用到的getTreeNode函数

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
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//首先进行hash 值的比较,若不同令当前节点变为它的左孩子或者右孩子
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
//hash 值相同,进行 key值的比较
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
//执行到这儿,意味着hash 值相同,key 值不同
//若k 是可比较的并且k.compareTo(pk) 返回结果不为0可进入下面elseif
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
/*若 k 是不可比较的 或者 k.compareTo(pk) 返回结果为0则在整棵树中进行查找,先找右子树,右子树没有再找左子树*/
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}

在HashMap 1.8中,无论是存元素还是取元素,都是优先判断bucket上第一个元素是否匹配,而在1.7中则是直接遍历查找。
基本过程如下:

  1. 根据key计算hash;
  2. 检查数组是否为空,为空返回null;
  3. 根据hash计算bucket位置,如果bucket第一个元素是目标元素,直接返回。否则执行4;
  4. 如果bucket上元素大于1并且是树结构,则执行树查找。否则执行5;
  5. 如果是链表结构,则遍历寻找目标

HashMap的remove(),删除操作

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
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}

return e;
}

删除操作,先计算指定key的hash值,然后计算出table中的存储位置,判断当前位置是否Entry实体存在,如果没有直接返回,若当前位置有Entry实体存在,则开始遍历列表。定义了三个Entry引用,分别为pre, e ,next。 在循环遍历的过程中,首先判断pre 和 e 是否相等,若相等表明,table的当前位置只有一个元素,直接将table[i] = next = null 。若形成了pre -> e -> next 的连接关系,判断e的key是否和指定的key 相等,若相等则让pre -> next ,e 失去引用。

HashMap的resize(),扩容机制

构造hash表时,如果不指明初始大小,默认大小为16(即Node数组大小16),如果Node[]数组中的元素达到(填充比Node.length)重新调整HashMap大小 变为原来2倍大小,扩容很耗时
HashMap扩容可以分为三种情况:
第一种:使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 16
0.75 = 12。
第二种:指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold,接着threshold = 当前的容量(threshold) * DEFAULT_LOAD_FACTOR。
第三种:HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍。
这边也可以引申到一个问题HashMap是先插入还是先扩容:HashMap初始化后首次插入数据时,先发生resize扩容再插入数据,之后每当插入的数据个数达到threshold时就会发生resize,此时是先插入数据再resize。

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
82
83
84
85
86
87
88
89
90
91
92
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //原表,首次初始化后table为Null
int oldCap = (oldTab == null) ? 0 : oldTab.length; //原表大小,默认构造器的情况下为0
int oldThr = threshold;//(threshold)阈值, 为 oldCap × load_factor
int newCap, newThr = 0; //记录新表的大小和阈值
//旧表容量大于0,表示被初始化过,需要执行的是扩容操作
if (oldCap > 0) {//table扩容过
//如果旧表容量大于容量最大值,那么阈值为Interger的最大值,即提升阈值,不再进行扩容,返回旧表
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否则,扩容为原先容量的1倍,阈值也扩容为原来的一倍 即现在新表table的容量乘以2,threshold的值也乘以2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//旧表容量为0,阈值大于0,则用阈值大小作为容量
else if (oldThr > 0) // initial capacity was placed in threshold
//使用带有初始容量的构造器时,table容量为初始化得到的threshold
newCap = oldThr;
//否则,表的容量为默认初始容量16,阈值为默认初始容量16*加载因子0.75
else { //默认构造器下进行扩容 // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新表阈值为0,则利用新容量*加载因子计算
if (newThr == 0) {
//使用带有初始容量的构造器在此处进行扩容
float ft = (float)newCap * loadFactor; //新表长度乘以加载因子
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新的阈值赋给HashMap的阈值成员变量
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
/*下面开始构造新表,初始化表中的数据*/
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//把新表赋值给table
if (oldTab != null) {//原表不是空要把原表中数据移动到新表中
/*遍历原来的旧表*/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //// 当前index没有发生hash冲突,直接对2取模,即移位运算hash &(2^n -1)
// 扩容都是按照2的幂次方扩容,因此newCap = 2^n
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 当前index对应的节点为红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//桶中存放的是链表
else { // preserve order 保证顺序
// 把当前index对应的链表分成两个链表,减少扩容的迁移量,根据变化的最高位的不同,也就是0或者1,将链表拆分开
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//记录下一个结点
//最高位为0,则将节点加入loTail.next
if ((e.hash & oldCap) == 0) {
//扩容后不需要移动的链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//最高位为1,则将节点加入hiTail.next
else {// 扩容后需要移动的链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//在新数组的位置与原数组的位置相同,新数组的桶直接指向LoHead
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//在新数组的位置是原数组的位置+旧数组长度,新数组的桶直接指向hiHead
hiTail.next = null;
if (hiTail == null)
// 扩容长度为当前index位置+旧的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

相关问题

加载因子(默认0.75):为什么需要使用加载因子,为什么需要扩容呢?

因为如果填充比很大,说明利用的空间很多,如果一直不进行扩容的话,链表就会越来越长,这样查找的效率很低,因为链表的长度很大(当然最新版本使用了红黑树后会改进很多),扩容之后,将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置,这样就减少了每个链表的长度,增加查找效率

JDK1.8使用红黑树的改进

在Java jdk8中对HashMap的源码进行了优化,在jdk7中,HashMap处理“碰撞”的时候,都是采用链表来存储,当碰撞的结点很多时,查询时间是O(n)。
在jdk8中,HashMap处理“碰撞”增加了红黑树这种数据结构,当碰撞结点较少时,采用链表存储,当较大时(>8个),采用红黑树(特点是查询时间是O(logn))存储(有一个阀值控制,大于阀值(8个),将链表存储转换成红黑树存储)

如果某HashMap中的记录过大的话(当前是TREEIFY_THRESHOLD = 8),HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好,是O(logn),而不是糟糕的O(n)。
它是如何工作的?
前面产生冲突的那些key对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个hashmap的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,你就并别指望能获得性能提升了。

Entry节点在插入链表的时候,是如何插入的?

java8之前是头插法,就是说新来的值会取代原有的值,原有的值就顺推到链表中去,就像上面的例子一样。
但是,在java8之后,都是所用尾部插入了。
为啥改为尾部插入呢?
解决1.7中多线程循环链表的bug
先举个例子吧,我们现在往一个容量大小为2的put两个值,负载因子是0.75是不是我们在put第二个的时候就会进行resize?
2*0.75 = 1 所以插入第二个就要resize了
现在我们要在容量为2的容器里面用不同线程插入A,B,C,假如我们在resize之前打个短点,那意味着数据都插入了但是还没resize那扩容前可能是这样的。
我们可以看到链表的指向A->B->C
Tip:A的下一个指针是指向B的

因为resize的赋值方式,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。
就可能出现下面的情况,大家发现问题没有?
B的下一个指针指向了A

一旦几个线程都调整完成,就可能出现环形链表

如果这个时候去取值,悲剧就出现了——Infinite Loop(无限循环)。
因为java8之后链表有红黑树的部分,大家可以看到代码已经多了很多if else的逻辑判断了,红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。
使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。
就是说原本是A->B,在扩容后那个链表还是A->B

Java7在多线程操作HashMap时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。

那是不是意味着Java8就可以把HashMap用在多线程中呢?

即使不会出现死循环,但是通过源码看到put/get方法都没有加同步锁,多线程情况最容易出现的就是:无法保证上一秒put的值,下一秒get的时候还是原值,所以线程安全还是无法保证。

HashMap的默认初始化长度是多少?原因?

初始化大小是16
我们在创建HashMap的时候,阿里巴巴规范插件会提醒我们最好赋初值,而且最好是2的幂。
这样是为了位运算的方便,位与运算比算数计算的效率高了很多,之所以选择16,是为了服务将Key映射到index的算法。

那为啥用16不用别的呢?

因为在使用不是2的幂的数字的时候,Length-1的值是所有二进制位全为1,这种情况下,index的结果等同于HashCode后几位的值。
只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。
这是为了实现均匀分布。

为啥我们重写equals方法的时候需要重写hashCode方法呢?

因为在java中,所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode,这两个方法都是用来比较两个对象是否相等的。
在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,显然我们new了2个对象内存地址肯定不一样
对于值对象,==比较的是两个对象的值
对于引用对象,比较的是两个对象的地址
大家是否还记得我说的HashMap是通过key的hashCode去寻找index的,那index一样就形成链表了,也就是说”帅丙“和”丙帅“的index都可能是2,在一个链表上的。
我们去get的时候,他就是根据key去hash然后计算出index,找到了2,那我怎么找到具体的”帅丙“还是”丙帅“呢?
equals!是的,所以如果我们对equals方法进行了重写,建议一定要对hashCode方法重写,以保证相同的对象返回相同的hash值,不同的对象返回不同的hash值。
不然一个链表的对象,你哪里知道你要找的是哪个,到时候发现hashCode都一样

怎么处理HashMap在线程安全的场景么?

我们一般都会使用HashTable或者ConcurrentHashMap,但是因为前者的并发度的原因基本上没啥使用场景了,所以存在线程不安全的场景我们都使用的是ConcurrentHashMap。
HashTable我看过他的源码,很简单粗暴,直接在方法上锁,并发度很低,最多同时允许一个线程访问,ConcurrentHashMap就好很多了,1.7和1.8有较大的不同,不过并发度都比前者好太多了。

什么时候resize?

有两个因素:

  • Capacity:HashMap当前长度。
  • LoadFactor:负载因子,默认值0.75f。
    举个例子:就比如当前的容量大小为100,当你存进第76个的时候,判断发现需要进行resize了,那就进行扩容,但是HashMap的扩容也不是简单的扩大点容量这么简单的。

扩容?它是怎么扩容的呢?

分为两步

  • 扩容:创建一个新的Entry空数组,长度是原数组的2倍。
  • ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。

为什么要重新Hash呢,直接复制过去不香么?

是因为长度扩大以后,Hash的规则也随之改变。
Hash的公式—> index = HashCode(Key) & (Length - 1)
原来长度(Length)是8你位运算出来的值是2 ,新的长度是16你位运算出来的值明显不一样了。

欣赏此文?求鼓励,求支持!