HashMap散列表是Java中用的最广泛的数据结构之一了，因为其查找数据的时间复杂度为常数级的，而且能够保存唯一key，所以使用起来很顺手。
首先分析下它的几个初始属性：1
2
3
4
5
6
7
8
9
10/*结构的核心，一个Node节点类型的数组*/
table
/*map的大小*/
size
/*阈值，数组的占用的位置大于等于这个值就开始扩容了*/
threshold
/*扩容指数*/
loadFactor
/*修改次数，按照注释看，这个值在remove，put操作后都会加1。HashMap的迭代器是fail-fast，用来保证遍历过程中不允许修改map，这个参数在迭代器为fail-fast的类中都存在。*/
modCount;
使用无参构造器初始化HashMap，就会使用默认的数组大小1>>4,扩容指数0.75，阈值就是12
先看看向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
45final 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;//HashMap还没有初始化的话，在这里初始化
if ((p = tab[i = (n - 1) & hash]) == null)//如果当前数组位置没有元素，直接放进下标为i的数组位置
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;//当前node的key已经存在，就直接替换
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) // -1 for 1st量表长度为8的时候就开始红黑树转换了
treeifyBin(tab, hash);//这个方法是将链表转换成红黑树
break;
}
if (e.hash == hash &&//遍历链表发现要插入的元素的key是已经存在了
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key 这里处理key存在的所有情况，更新这个节点
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//插入了新节点，大小加1
if (++size > threshold)//threshold = loadFactor*initialCapacity 阈值
resize();//数组扩容
afterNodeInsertion(evict);
return null;
}
插入过程中如果出现扩容的扩容方法: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
74final 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) {//原先表的长度已经大于等于2的30次方了
threshold = Integer.MAX_VALUE;//则将临界点定为int的最大值,就是2147483647，数组并不扩容
return oldTab;//返回
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//如果当前数组的长度的2倍小于2的30次方，
// 且数组长度大于等于初始化长度16，则新临界点翻倍
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold 老的临界点是大于0，则给数组长度赋为临界点的长度
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //如果数组没有初始化，临界点页没有初始化，那么数组长度和临界点都赋为默认值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//新临界点为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;//将老的数组位置中的node赋给e这个对象，然后将数组的这个位置置空
if (e.next == null)//如果这个e节点只是一个单节点，并不存在后续节点，那么直接计算出它在新数组中的位置，然后赋到新数组中
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果这个节点已经是红黑树节点(红黑树节点是继承了Node类的，所以是它的子类)了
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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) {//后面有两块代码，一块是选出位于老的位置的node --->loHead，一块是选出位于新的位置的node -->hiHead
if (loTail == null)//如何算出老的位置，（e.hash & oldCap) == 0
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;
}
从map中取值的方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; //数组
Node<K,V> first, e; //first是hash值计算出来的数组位置节点
int n; //数组长度
K k;//key
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((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;
}
从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
44final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab;
Node<K,V> p; //当前table中的节点
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))))//数组位置的元素刚好是需要移除的key
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)))) {//value如果匹配，但是key不匹配也是可以删除的
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;
}
总结
HashMap散列表结构用处很广泛，Set数据结构的底层全是利用它实现的，它不存在重复的key，用起来很顺手，去重很方面，而且1.8优化之后的HashMap查找的效率更高了，但是它不是线程安全的。使用线程安全的结构建议使用ConcurrentHashMap，虽然有其他的线程安全的散列表，但是相对应效率低，不建议使用。