实现原理分析
HashMap的底层是红黑树,数组,链表;默认其初始容量为16;当put时首先就会进入到putVal这个函数,到这个函数中首先先判断底层的table是否为空或者长度为0,若是则会扩容到16,然后根据key值计算出table值,若table值为空,则直接加入到这个table位置上;若不是则会判断加入的key和旧的key是否是同一对象或者euqals相同,若是,则不用加了;若不是，先判断是否是为红黑树,如果是,则按照红黑树的逻辑加,若不是则会进入死循环,死循环中如果有key相同就只是替换value,如果不是则尾插到链表末尾,若单个链表超过8个,则会进行树化,在树化这个函数中先判断容量是否超过64,如果是则树化否则扩容。最后判断是否需要扩容。
源码分析
首先会进入put函数
1
2
3
4
5
|
public V put(K key, V value) {
//传入其哈希值和key和value
//(h = key.hashCode()) ^ (h >>> 16) 计算key的hash值,让高位和低位进行异或
return putVal(hash(key), key, value, false, true);
}
|
然后执行putval方法
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
|
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;//辅助变量
//如果底层的table数组为null,或者length = 0,就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值对应的table的索引位置的Node,如果为空,则直接创建一个新的节点,填入key和value,加入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k; // 辅助变量
//如果table的索引位置的key的hash相同和新的key的hash值相同
//并满足(table现有的结点的key和添加的key是同一对象 || equals返回真,就认为不能加这个k-v)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //如果当前的table的已有的Node是红黑树,就按照红黑树的方式处理
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);
//加入后，判断当前链表的个数，是否已经到达八个，到八个，后面就调用treeifyBin方法进行红黑树的转化,不进行树化
//其中树化里面会判断是否超过64,没有就扩容
/* if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在循环中相同就只是替换value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //替换value
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //每次加入一个都加一
if (++size > threshold) //判断是否需要扩容
resize();
afterNodeInsertion(evict);
return null;
}
|
结论总结
HashMap底层维护了Node类型的数组table,默认为null。
当创建对象时,将加载因子初始化为0.75。
当添加key-val时,通过key的哈希值得到在table的索引,然后判断索引是否有元素,如果没有元素直接加入。如果索引处有元素,则判断key值是否相同,若相同,则直接替换value;如果不相同,则会判断是树结构还是链表结构,分别进行相应的处理。如果添加时发现容量不够,则会进行扩容。
第一次添加，则需要扩容table容量为16，临界值为12(16 * 0.75)
以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍，即24，依次类推。
在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化
