Java集合框架详解(三) HashMap

今天继续对集合框架源码的学习 JDK1.8 今天学习HashMap

相关文章

HashMap

HashMap介绍

HashMap是基于哈希表的 Map 接口的实现,以Entry<k, v>键值对为单位的集合,并且同前面介绍的ArrayListLinkedList一样,它不是线程安全的。
在JDK1.8中,HashMap加入了红黑树结构,红黑树具体我也是才学习到,详细学习请往下看。

类定义

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

HashMap继承了AbstractMap<K,V>类、实现了Map<K,V>, Cloneable, Serializable接口。

数据结构

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
//数组以及链表结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
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
interface Entry<K,V> {

K getKey();

V getValue();

V setValue(V value);

boolean equals(Object o);

int hashCode();

public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}

public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}

public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}

public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}

通过上述代码,能发现HashMap中有一个Node内部类,它实现了Entry接口,含有Key,Value,next属性,到这里我们慢慢可以知道,实际上Node就是HashMap的其中一个信息元素,数据均以键值对的形式保存在Node中,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

//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//加载因子
//如果哈希表中的元素放得太满,就必须进行rehashing(再哈希)。再哈希使哈希表元数增倍,并将原有的对象重
//新导入新的哈希表元中,而原始的哈希表元被删除。load factor(加载因子)决定何时要对哈希表进行再哈希
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//链表节点转换红黑树节点的阈值8
static final int TREEIFY_THRESHOLD = 8;

//红黑树节点转换链表节点的阈值, 6个节点转
static final int UNTREEIFY_THRESHOLD = 6;

//转红黑树时, table的最小长度
static final int MIN_TREEIFY_CAPACITY = 64;

//保存Node<K,V>节点的数组
transient Node<K,V>[] table;

//由HashMap中Node组成的set
transient Set<Map.Entry<K,V>> entrySet;

//HashMap中元素的数量
transient int size;

//hashMap发生结构性变化的次数(不包括value的覆盖)
transient int modCount;

//HashMap 容量
int threshold;

//记录加载因子
final float loadFactor;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}

//返回一个比给定整数大且最接近的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;
}

关于tableSizeFor(int cap)的原理

不得不说,这个算法非常巧妙,能够返回比cap大且最接近2的幂的数。

第一步: n |= n >>> 1; 也就是n变为n与n右移一位之后异或后的值,即

n: 00..01XXXXXXX

n>>>1: 00..001XXXXXX

新n: 00..011XXXXXX 到这里我们看不出什么

第二步: n |= n >>> 2; 也就是n变成n与n右移两位之后异或的值,即

n: 00..011XXXXXX

n>>>2: 00..00011XXXX

新n: 00..01111XXXX

后面相类似。到这个地方我们就能知道,算法把第一个1后面的所有位全部变成了1,最后返回n+1,即比cap大的最小二的幂

我们再看看其他构造方法

1
2
3
4
5
6
7
8
//指定初始容量,采用0.75加载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {//均采用默认值
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

HashMap的一些重要方法

关于hash方法

1
2
3
4
5
6
7
8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;

整个过程本质上就是三步:

拿到key的hashCode值

将hashCode的高位参与运算,重新计算hash值

将计算出来的hash值与(table.length - 1)进行&运算

方法解读:

对于任意给定的对象,只要它的hashCode()返回值相同,那么计算得到的hash值总是相同的。我们首先想到的就是把h>ash值对table长度取模运算,这样一来,元素的分布相对来说是比较均匀的。

但是模运算消耗还是比较大的,我们知道计算机比较快的运算为位运算,因此JDK团队对取模运算进行了优化,使用上面代码2的位与运算来代替模运算。这个方法非常巧妙,它通过 “(table.length -1) & h” 来得到该对象的索引位置,这个优化是基于以下公式:x mod 2^n = x & (2^n - 1)。我们知道HashMap底层数组的长度总是2的n次方,并且取模运算为“h mod table.length”,对应上面的公式,可以得到该运算等同于“h & (table.length - 1)”。这是HashMap在速度上的优化,因为&比%具有更高的效率。

在JDK1.8的实现中,还优化了高位运算的算法,将hashCode的高16位与hashCode进行异或运算,主要是为了在table的length较小的时候,让高位也参与运算,并且不会有太大的开销。

下图是一个简单的例子,table长度为16:

hash

参考文章:Java集合:HashMap详解(JDK 1.8)

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
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//oldTab表示原来的HashMap数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap表示原来的容量
int oldThr = threshold;//表示原来的临界值
int newCap, newThr = 0;//新容量,新临界值
if (oldCap > 0) {//原来的HamhMapf非空,需要扩容
if (oldCap >= MAXIMUM_CAPACITY) {//说明原来的容量已经超过最大容量,无法进行扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//说明可以扩容
newThr = oldThr << 1; // double threshold 两倍扩容
}
else if (oldThr > 0) // initial capacity was placed in threshold 用原来容量的临界值代替新的容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults 一切采用默认值
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;//变为null 垃圾回收
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//找到该结点在数组中所在位置并无冲突情况下写入,e.hash & (newCap - 1)在前面已经解释过,见hash方法的分析
else if (e instanceof TreeNode)//e为树型结点,说明存在以红黑树的结点变量,则调用相关红黑树方法
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 存在冲突,并且不是红黑树类型的hash冲突,即HashMap链表的hash冲突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 因为新数组的长度是原数组的2倍, newTable.length-1 比 oldTable.length-1 多oldCap, 所以 hash & (newTable.length - 1) 等价于 hash & (oldTable.length - 1) + (hash & oldCap == 0 ? 0 : oldCap)
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;
}

put(K key, V value)

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
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
//使用(hashCode的值)以及(hashCode的值无符号右移16位)做异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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是否为空或者length等于0,如果为空或为0则调用resize初始化
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))))//判断p结点的hash和key值是否与传入的结点相同
e = p;//如果相同,则p结点即要查找的结点,赋值给e
else if (p instanceof TreeNode)//若原本为红黑树结点,则调用putTreeVal方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {// p.next为空代表不存在目标节点则新增一个节点插入链表尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //-1是因为循环是从p.next开始的
treeifyBin(tab, hash);//链表上结点超过TREEIFY_THRESHOLD - 1,调用方法转化为红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//如果e结点的hash与key值都与传入的相同,则e为我们要找的结点,跳出循环
break;
p = e; //下一结点p.next
}
}
//之前的代码都是在找待修改或插入的结点e,后面分析如果e不为空(即e已经找到)的结果
if (e != null) { // 如果需要插入的元素e已经找到
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;//将该节点的value覆盖,返回oldValue
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//操作后超过阈值则进行扩容
resize();
afterNodeInsertion(evict);
return null;
}

get(Object key)

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 V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//first为待查结点的hash对应的位置所在的结点
if (first.hash == hash && //
((k = first.key) == key || (key != null && key.equals(k))))//如果hash值以及key都相同,说明是待查结点,无hash冲突
return first;//返回该结点
if ((e = first.next) != null) {//存在hash冲突,分两种情况
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(Object key)

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
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}


// @param matchValue 为true时只有value相同时才删除,false则强制删除
// @param movable 如果为false则不移动其他结点,true会移动
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) {//当hashmap数组不为空并且hash所在位置结点不为空时,说明可以该位置存在结点
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;//当key等于传入的key,并且hash相同,说明没有hash冲突,把所在的结点传给p
else if ((e = p.next) != null) {
if (p instanceof TreeNode)//存在红黑树类型的冲突
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {//存在链表类型的hash冲突
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);//遍历数组,直到找到待删结点或者(e = e.next) != null
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {//如果node不为空说明已经找到了待删结点,以及判断是否强制删除,如果不强制删除则继续判断待删结点的value是否为对应node的value
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总结

  • HashMap(JDK1.8)使用的是数组 + 链表 + 红黑树的形式,相比于JDK1.7的数组 + 链表很大程度上提升了HashMap的性能;
  • HashMap依然不是线程安全的,在并发环境下使用HashMap会导致死循环,可以使用ConcurrenctHashMap(详情等到学习并发的时候详细分析);
  • HashMap扩容是进行2倍扩容(正常情况下),在创建对象的时候,由于扩容是非常消耗性能的操作,所以最好先定义好容量避免多次扩容;
  • 在HashMap所有方法中,这些可能只是冰山一角,在以后的学习中会继续对HashMap源码进行更加深刻的学习;
  • 未完待续