内部结构
通过查看源码可以知道，HashMap内部的基本结构是数组+链表的形式。
put()方法
通过源码得知调用put方法，最终会调用putVal方法
get()方法
|
|
总结
- 扩容时机：当哈希表中的结点数超出了加载因子与当前容量的乘积时
- HashMap中元素的索引并不恒定不变，当进行扩容时，索引可能会发生偏移，偏移量为2的n次方
HashMap原理浅析
1
2
3
4
5
6
7
8
9
10
//基本结构，为Node数组
transient Node<K,V>[] table;
//Node类为数组中的结点，其中next用来指向和该结点具有相同hash值的结点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// putVal方法具有返回值，会返回之前在这个结点的值，若之前该结点无值，则返回null
// onlyIfAbsent若为true，则不替换之前的值，否则替换
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为空，进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
**// (n - 1) & hash代表在table中的索引
// 当长度为2的n次方时，就相当于对lenght求模，进行位运算则可以提高效率
// 另外一个是可以降低出现hash冲突的概率，使得元素均匀分布
// 如果该结点没有存放值，则直接进行存放**
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 该结点已有值
else {
Node<K,V> e; K k;
// key值和hash值均相等，则会进行替换
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);
//1.8之前是插在头部的，
//如果数量大于8，则转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
afterNodeAccess(e);
return oldValue;
}
}
// 修改次数+1
++modCount;
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
return null;
}