简介
整体流程
如何初始化的呢？
首先先过一下HashMap的大体流程。就从方法的初始化开始吧。我们有四种方式去构造HashMap，这几种方式基本是负载因子和初始容量的组合，一般我们都是构造一个默认容量和默认负载因子的HashMap；如果我们用指定初始容量的方式构造HashMap，那么程序会做一次计算上的转换，将入参容量转换为与入参最近的2的幂等数，比如指定了初始容量为17，那么计算的结果是32。
如何放入元素的？
初始好后就可以往里面添加元素了。HashMap的底层是用一个Node类型的数组存放数据的，那么这个数据放在哪个地方呢？所以会有一个关键的寻址算法去确定这个事情。如果是第一次添加数据，那么还要先出发一个扩容操作，然后才能添加数据。在添加数据时可以分为以下几个情况：
- 找到了一个位置且这个位置没有数据，直接将这个数据的Node放进去
- 找到了一个位置，但这个位置有数据，具体又分为一下几个情况
- 新值与旧值的key和value值相等，不新增数据直接返回
- 找到了一个位置，但这个位置上是一棵树，将元素放入的树种
- 找到了一个位置，但这个位置上是一个链表，就遍历这个链表，如果遍历到了和要添加数据的hash值与key相等的数据，就返回；否则就继续遍历，知道遍历到第8此，此时会看Node数组中元素的数量是否小于64，是的话会触发扩容，否的话会直接将链表转为树后再存放元素
如何访问元素的？
查找数据时，也是要根据寻址算法找到具体的位置，然后根据这个位置的数据类型走执行不同的逻辑
- 如果当前位置就1个Node，直接返回这个Node的value值
- 如果当前位置的Node的next节点为一棵树，则从树中查找元素
- 如果当前位置的Node的next节点为一个链表，就遍历这个链表
如何删除无用元素？
删除元素时也会根据寻址算法找到这个元素，然后根据不同的数据类型走不通的逻辑：
- 如果是树，则从树中移除这个元素，同时判断树是否小于6，是的话要将将树转换为链表
- 如果是链表，则将指定索引处的数据改为null，即将删除node的上个node的next节点指向删除node的下个Node
- 如果是一个元素，将这个位置改为Null
重点属性
- DEFAULT_INITIAL_CAPACITY，默认数组容量大小，值为16
- DEFAULT_LOAD_FACTOR，默认负载因子，默认值0.75，决定何时出发扩容操作
- TREEIFY_THRESHOLD = 8，决定何时将链表转换为树
- UNTREEIFY_THRESHOLD = 6，决定何时将树转换为链表
- MIN_TREEIFY_CAPACITY = 64，影响转换树的时机，即当TREEIFY_THRESHOLD>8但是数组中元素数量小于64时，会先触发扩容，而不是将链表直接转换为红黑树
- Node静态内部类，主要属性有hash值，key值，value值以及Next Node的指针
- Node<K,V>[] table，底层数据结构，又来存储数据
- int size，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
|
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
|
关键方法
寻址算法
由于寻址算法贯穿于整个HashMap中，所以我们先了解一下这个算法，这个算法决定了一个数据的位置。
先看一下Hash算法
1
2
3
4
| static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
我们发现key的hash值并不是简单的调用了key.hashCode()方法获取的hash值，而是先计算出这个key的hash值，再用这个值和它右移16位后的结果做“异或”操作进而算出一个新的hash值。那么这里为什么要位移16位呢？这个要和它的寻址算法结合起来看，它的寻址算法是：(table.length - 1) & hash ，即数组长度减1然后和hash值做“与”运算。这种算法在数组长度是2的倍数次幂的时候算出来的结果与key.hashCode() % table.length 的结果是一致的，但是性能却要高很多，这就引出了第一个问题的第一个优势：高性能。又因为hash算法算出来的hash值要与数组长度-1做“与”运算，如果不做>>>16位的话，大概率只有key的低16位参与运算，大大增加了hash碰撞几率。而通过位移16位再做异或运算，让低16位同时具有key的高低16位的部分特征，再和寻址算法结合起来，这样可以大大减少碰撞几率。
总结如下：
hash算法优化：(h = key.hashCode()) ^ (h >>> 16)， 算出hashcode，并与hashcode位移16位后的值进行异或运算，得到新的hash值；
寻址算法优化：(n - 1) & hash， 数组长度减1并和hash值做与运算，得到位置，如果位置为null，直接放进去就行，优势：一是提高了性能，二是减少了hash碰撞。
现在我们模拟一下这个过程：
1
2
3
4
5
| public static void main(String[] args) {
HashMap <String, Integer> hashMap = new HashMap<>(37);
String key = "abc";
hashMap.put(key, 2);
}
|
首先，key的hashCode值是:96354,对应的二进制是0000000000000001 0111100001100010
0000000000000001 0111100001100010
^
0000000000000000 0000000000000001
0000000000000001 0111100001100011 ->对应的10进制：96355
然后寻址算法:
(table.length - 1) & hash(key) ->>>63 & 96355
0000000000000000 0000000000111111
&
0000000000000001 0111100001100011
0000000000000000 0000000000100011 ->>对应的10进制：35
put方法
1
2
3
4
| public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
|
主要是这个方法：
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
| 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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
扩容机制
扩容时，新的数组容量会是旧数组的两倍，假设原数组容量为16，那么新数组的容量为32。扩容后要确定Node在新数组的位置，所以我们需要遍历旧数组，根据旧数组中索引的数据类型又分为三种情况
索引处只有一个Node
此时要重新计算这个Node在新数组中的位置，计算的公式为：hash & (newCap - 1)。由于扩容的大小是2的次幂，所以这里很容易计算它在新数组中的位置，要么位置不变，要么是一个新位置。
索引处是一棵树
拆分树中元素，如果树中元素小于等于6，则将树转为链表。
索引处是一个链表
遍历链表中的每个Node，然后根据(e.hash & oldCap) == 0算法来判断改Node的位置是否要调整。具体来说，如果结果==0为真，则该Node的位置是不表的；否则会移动到原位置加上旧容量的位置，这样可以保证元素在扩容后的分布仍然均匀，从而保持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
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
| 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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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;
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)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
get方法
根据key值获取value值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| final Node<K,V> getNode(Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
if (first.hash == hash &&
((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;
}
|
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
34
35
36
37
38
39
40
41
| final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
|
几个简单的概念：
位移符号:
>>, 带符号的位移,整数位移高位补0，负数位移高位补1
>>>,无符号的位移符，高位都是补0
异或：参与运算的两个值，如果相同bit位的值相同，则结果为0，不同，则结果为1
与：两个相同的bit位同时为1，则结果为1，否则为0
或：两个相同的bit位同时为0，则结果为0，否则为1
.jpg)
%20(%E5%B0%8F).jpg)
