0%

Java集合框架 —— HashMap

声明:本文使用JDK1.8

HashMap 是我们平时开发过程中使用最多的 Java 集合框架之一,它继承 AbstractMap,实现 Map 接口,是一种 key-value,并允许使用空值和空键。

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

从结构实现来讲,HashMap 是 数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,相比于Java7,Node可以被扩展成TreeNode。

HashMap类加载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//初始容量为16的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量(1073741824)
static final int MAXIMUM_CAPACITY = 1 << 30;
//哈希表在其容量自动增加之前可以达到多满的一种尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表中数据的临界值,如果达到8,就进行resize扩展,如果数组大于64则转换为树.
static final int TREEIFY_THRESHOLD = 8;
//如果链表的数据小于6,则从树转换为链表.
static final int UNTREEIFY_THRESHOLD = 6;
//如果数组的size大于64,则把链表进行转化为树
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
//通过key计算hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对于HashMap初始化的容量是16的原因,可以看这里:漫画:什么是HashMap?,
感觉讲的还是挺详细的。之所以选择 16 这个数字,是服务于从 key 映射到 index 的算法。index = HashCode(Key) & (length - 1), 如果 length 是2的幂的话,则 length - 1 就是全是 1的二进制数,比如 16 - 1 = 1111,这样相当于是坐落在长度为 length 的 hashMap 上的位置只和 HashCode 的后四位有关,这只要给出的 HashCode 算法本身分布均匀,算出的index就是分布均匀的。

可以了解下 漫画:高并发下的HashMap,不过这里的代码比较老。HashMap 在高并发下出现死锁,主要发生在 rehash 时,链表出现环链了。不过在Java8 中,对于链表超过8时,转化为红黑树,这有效的防止这个问题。

tableSizeFor

1
2
3
4
5
6
7
8
9
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;
}

这个方法被调用的地方:

1
2
3
4
5
public HashMap(int initialCapacity, float loadFactor) {
/**省略此处代码...**/
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}

当实例化 HashMap 实例时,如果给定了 初始容量initialCapacity,由于 HashMap 的 capacity 都是 2 的幂,因此这个方法用于找到大于等于 initialCapacity 的最小的2的幂。

Node

Java8中相对之前的版本增加了Node,从代码中可以看出,是一个哈希桶数组,实现Map.Entry接口,是一个键值对。

key 和 index

在 HashMap 中,下标的选择是计算key的hash值,具体公式是:(n - 1 ) & hash 。其中 n 是 hashmap table[] 数组的长度,hash 是当前key的hash值。& 是与运算,两个数都转为二进制,然后从高位开始比较,如果两个数都为1则为1,否则为0。详细的可以看之前的那篇链接。

hasCode 和 equals

HashMap 重写了 hasCode 和 equals,源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCod(value);
}
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;
}

hash

HashMap 的 hash 计算方法。key的hash值高16位不变,低16位与高16位异或作为key的最终hash值。h>>>16 无符号右移16位,高位补0,任何数跟0异或都是其本身,因此key的hash值高16位不变。异或位运算(0 ^ 1 得 1、1 ^ 1 得 0、0 ^ 0 得 0、1 ^ 0 得 1)

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

初始化

HashMap提供三种初始化HashMap:

1
2
3
4
5
6
7
8
9
10
11
12
13
//默认初始化16,加载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//给定容量,加载因子0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用与指定的Map相同的映射构造一个新的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

get相关

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) {//(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 {//遍历链表,得到节点值,通过hash和equals(key)确认所查找元素。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

contains

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}

public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}

put

put函数是想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
public V put(K key, V value) {
return putVal(hash(key), key, value, false, 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空||length为0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;// 分配空间,初始化
//hash所在位置(第i个桶)为null,直接put
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//tab[i]有元素,则需要遍历结点后再添加
Node<K,V> e; K k;
// hash、key均等,说明待插入元素和第一个元素相等,直接更新
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) {//死循环,直到break
if ((e = p.next) == null) {//表尾仍没有key相同节点,新建节点
p.next = newNode(hash, key, value, null);
//若链表数量大于阀值8【9个】,则调用treeifyBin方法,仅当tab.length大于64才将链表改为红黑树
// 如果tab.length<64或table=null,则重构一下链表
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);//binCount>=9则链表转树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;// hash、key均相等,说明此时的节点==待插入节点,更新
p = e;//更新p指向下一个节点
}
}
//当前节点e = p.next不为null,即链表中原本存在了相同key,则返回oldValue
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent值为false,参数主要决定当该键已经存在时,是否执行替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//调用linkedHashMap,move node to last
return oldValue;
}
}
++modCount;
if (++size > threshold)//++size后再检测是否到了阀值
resize();
afterNodeInsertion(evict);//调用linkedHashMap,true则possibly remove eldest
return null;// 原hashMap中不存在相同key的键值对,则在插入键值对后,返回null。
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//当tab长度小于64的时候,只是扩容,而不是转化成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

扩容

先了解一些字段含义:

1
2
3
4
5
6
// HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)
int threshold;
// 加载因子实际大小
final float loadFactor;
int size; //实际存在的键值对数量
transient volatile int modCount; // 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
79
80
81
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //赋值老的Node
int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的Node的大小
int oldThr = threshold; //旧阀值
int newCap, newThr = 0; // 新容量,新阀值
if (oldCap > 0) {
//扩容前的数组大小如果已经达到最大(2^30)了
if (oldCap >= MAXIMUM_CAPACITY) {
///修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
//大于初始容量,旧容量2倍小于最大容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; //2倍
}// oldCap=0 ,oldThr>0,threshold(新的扩容resize临界值)
else if (oldThr > 0)
newCap = oldThr;//新容量=旧阀值(扩容临界值)
else { // oldCap=0 ,oldThr=0,调用默认值来初始化
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16
}
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;
// table初始化,bucket copy到新bucket,分链表和红黑树
if (oldTab != null) { // 不为空则挨个copy,影响效率!!
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//先赋值再判断
oldTab[j] = null;//置null,主动GC
if (e.next == null)
//1.6 的indexFor,计算key;tableSizeFor性能优化
newTab[e.hash & (newCap - 1)] = e;//hash&(length-1)
else if (e instanceof TreeNode) // 红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //链表,preserve order保持顺序
//一个桶中有多个元素,遍历将它们移到新的bucket或原bucket
Node<K,V> loHead = null, loTail = null;//lo原bucket的链表指针
Node<K,V> hiHead = null, hiTail = null;//hi新bucket的链表指针
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) {//原bucket位置的尾指针不为空(即还有node)
loTail.next = null;//链表最后得有个null
newTab[j] = loHead;//链表头指针放在新桶的相同下标(j)处
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

put(K key, V value)的逻辑:

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;

④.判断table[i] 是否为TreeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;

⑤.遍历table[i],判断链表长度是否大于8,大于8的话,同时需要判断 table 数组大小是否大于64,如果只满足前一个条件,只进行扩容;若果两个条件都满足,把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

JDK7和JDK8之后,HashMap 的区别?

  • 1.7中采用数组+链表,1.8采用的是数组+链表/红黑树,即在1.7中链表长度超过一定长度后就改成红黑树存储。
  • 1.7扩容时需要重新计算哈希值和索引位置,1.8并不重新计算哈希值,巧妙地采用和扩容后容量进行&操作来计算新的索引位置。
  • 1.7是采用表头插入法插入链表,1.8采用的是尾部插入法。

在1.7中采用表头插入法,在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题;在1.8中采用尾部插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

Reference

客官,赏一杯coffee嘛~~~~