java8集合框架(二)-Map的实现类(HashMap,LinkedHashMap)

java8集合框架(二)-Map的实现类(HashMap,LinkedHashMap)

Map在集合中是非常重要的,他保证了一个key最多对应了一个value。Java的工具包中Map的非线程安全的实现类包括了HashMap, TreeMap, WeakHashMap, IdenityHashMap, EnumMap, LinkedHashMap。

Note:本篇源码分析基于jdk1.8版本

HashMap


HashMap是日常中最经常用到的,非线程安全的map实现,它允许使用nullkey和nullvalue,构造函数两个参数initialCapacityloadFactor对效率影响较大。1.8版本的HashMap引入了红黑树,优化了扩容机制。HashMap接受nullkey和nullvalue。

数据结构

HashMap的核心数据结构是数组+链表+红黑树。hash相同的元素会分配的同一个数组索引位,发生hash碰撞则以此索引位置的元素为头节点,组成链表。当链表的长度大于8,会将链表转化为红黑树。

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
//核心容器
transient Node<K,V>[] table;
//元素个数
transient int size;
//修改次数,fail-fast
transient int modCount;
//扩容阈值
int threshold;
//负载因子
final float loadFactor;
//实际存放数据的节点数据结构
static class Node<K,V> implements Map.Entry<K,V> {
//key计算出来的hash值,用来定位数组索引位
final int hash;
final K key;
V value;
//链表的下一个节点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {...}
public final K getKey() { ...}
public final V getValue() {... }
public final String toString() { ... }
public final int hashCode() {...}
public final V setValue(V newValue) {...}
public final boolean equals(Object o) {...}
}

从源码我们得知,节点是一个Map.Entry的实现。保存了元素的映射关系。

初始化

说到初始化,先来看一下HashMap的一个构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
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);
}

HashMap的默认负载因子是0.75,默认的初始容量是16。代码里面的threshold是需要注意的,第一次扩容的时候threshold承载的含义是初始化数组的长度,以后的扩容承载的含义是扩容的阈值。第一次通过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;
}

threshold等于当前容量的2次方。例如当前容量是5<2^3,那么tableSizeFor将会返回2^3=8。JDK1.8的实现使用了位运算,这样能达到最好的性能。非常巧妙,这里不表,有兴趣自己模拟走一遍就明白了。

方法实现-put

HashMap在没有使用的时候table是没有初始化的,也就是null。第一次调用put方法可能触发table的初始化。为什么是可能触发呢?看看HashMap (Map<? extends K, ? extends V> m)的实现就懂了。我们现在分析put的实现。

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

调用put方法实际上是调用了putVal方法,在调用之前,先对key进行了hash计算

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

hash的做法是将key.hashcode计算出来的值的前16位和后16位做异或。可能有人会有疑问,key.hashcode已经实现了hash值的计算了,为什么还要调用hash?这样做的好处在于降低hash碰撞的概率。但是1.8中的hash已经非常简单的处理了,作者也说明了是一种权衡。原因大致有三:一是很多元素的hash已经很分散了,二是使用了树来处理大量的hash碰撞,三是降低系统消耗。

Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. 

继续看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
54
55
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;
//如果tab[i]为空,则新建节点,赋值给tab[i]
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;
//如果已经转化为红黑树了,则交给treeNode处理
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);
//如果碰撞次数大于8次,转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//寻找与给定key相等的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//找到了相等的key
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//更新节点的value
e.value = value;
afterNodeAccess(e);
//返回value原值
return oldValue;
}
}
//增加modCount,用于快速失败
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

说明:

  • 第一次调用时,table==null,所以会进入resize()方法初始化,后面有详细说明。
  • 元素在table的索引位置是由i=(n - 1) & hash确定。
  • table[i]为空就直接将元素挂在该节点。否则挂在以此节点为头节点的链表上。
  • 当链表上的任意节点当满足hashkeykey.equal相等,则更新改节点的value
  • 如果hash碰撞超过TREEIFY_THRESHOLD=8次,则将该链表转化为红黑树,以提高性能。
  • 检测是否需要扩容。

方法实现-get

一般来说,get方法的时间复杂度是O(1)。

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
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) {
//检查头节点
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相等,key相等或者equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

根据上面的步骤总结,hash确定元素的索引,equals确定元素。这里也是面试经常会问的地方。

扩容机制

当存放的元素越来越多,超过threshold,那么就需要就数组扩容。新建一个大数组,然后将小数组的元素复制到大数组。这里也是非线程安全的问题所在。

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
82
83
84
85
86
87
88
final 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) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//newCap是原来的两倍,newThr也是原来的两倍
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
//第一次扩容的时候,构造函数里面计算的threshold赋值给了newCap
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//没有给任何参数,则容量设置为16,阈值设为12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
//第一次扩容的时候,newThr设置为容量*负载因子
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;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
/*
* 因为是2倍扩充,所以原数组中的数据最多会被hash到新数组的
* 同一索引或(同一索引+原数组容量)的位置。这里不理解的见下
* 面的说明。1.8还保证了节点的顺序,loHead和loTail是低位置
* 的新链表,hiHead和HiTail是高位置的新链表。
*/
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) {
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;
}

这里的扩容非常巧妙,我们要解释一下(e.hash & oldCap) == 0的用意。先看一个例子

Hash\Array 0 5 6 7
01000110 01000110&111=110
01101110 01101110&111=110

扩容后

Hash\Array 0 5 6 7 14 ..
01000110 01000110&1111=0110
01101110 01101110&1111=1110=0110+8(oldCap)

可见,判断某一个数组索引下的的链表节点rehash到新数组的索引,只需判断新增的那位bit是0还是1。如果是0则新数组的索引等于原数组,如果是1则新数组的索引等于原数组索引+原数组容量。这就是2倍扩容的优点,也是扩容机制的优化点。

这张图非常直观的表达了扩容的过程,图片引用自Java 8系列之重新认识HashMap

HashMap在多线程下的死循环

了解过Hashmap源码的人都知道,jdk1.7的实现下,HashMap在扩容的时候是有可能造成死循环的,可以点击这里参考。文章分析的非常细致,那么在1.8中是否还会出现死循环呢?根据我的分析,答案是否定的。我们知道1.7中出现死循环的关键在于扩容后,改变了节点的顺序。而1.8中的扩容保证了元素的顺序,所以不会出现死循环。但是HashMap仍然非线程安全,因为它还是会丢失节点。

LinkedHashMap


它不仅继承了HashMap优秀的存储、访问性能,在此基础上还提升了迭代性能。后者的迭代时间与其容量有关,而LinkedHashMap的迭代时间与其节点数量有关,这是两个不同的概念。LinkedHashMap接受nullkey和nullvalue。

举个例子:如果设置容量为10000,向此map插入十个元素。HashMap需要遍历这个length为10000的数组,如果hash碰撞,还需要遍历链表。而LinkedHashMap只需遍历这十个元素。

数据结构

LinkedHashMap继承了HashMap实现类,在其基础上,提升了快速迭代的性能。它的数据结构是数组+(同一数组索引元素之间的)链表+红黑树的HashMap和(所有元素访问/插入顺序的)双向链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
//头指针,指向最老的元素
transient LinkedHashMap.Entry<K,V> head;
//尾指针,指向最新的元素
transient LinkedHashMap.Entry<K,V> tail;
//true:按照访问排序,false:按照插入排序。默认按照插入排序
final boolean accessOrder;
//在HashMap.Node的基础上添加了指向前一个较老元素和后一个较新元素的指针
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

Hook-钩子方法

上面分析HashMap的源码时,我们能看见很多实现为空的方法,这些方法是单独留给LinkedHashMap的钩子方法。其实就是双向链表的增删改操作,大学的数据结构课程都讲过。

HashMap中留下的钩子方法

1
2
3
4
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

LinkedHashMap中的实现

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
//将节点从双向链表中删除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
//插入后可能要删除最老的元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//执行溢出规则
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//访问后要将该元素插入到双向链表尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}

遍历方法

我们知道,map接口定义了三个遍历方法。分别是entrysetkeysetvalues,这里我们只分析entryset的实现

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
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//使用了内部类实现
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { ... }
public final void clear() { ... }
//内部类的迭代器
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
...
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
//这里遍历双向链表
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
//抽象类实现
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() { ... }
public final boolean hasNext() {...}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//迭代链表
current = e;
next = e.after;
return e;
}
public final void remove() {...}
}

应用-实现LRU

我们看到在每次访问和插入的时候都会执行钩子方法,如果按照访问排序,又可以移除最老的元素,不就是LRU的定义吗?

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
package com.collection;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by john on 16/8/27.
* 用LinkedHashMap实现LRU缓存
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
//缓存容量
private int maxElement;
public LRUCache(int maxElement) {
super(maxElement, 0.75f, true);
this.maxElement = maxElement;
}
@Override
//检查是否溢出
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxElement;
}
public static void main(String[] args) {
Map<String, Object> cache = new LRUCache<>(5);
cache.put("1", "java");
cache.put("2", "C#");
cache.put("3", "C");
cache.put("4", "C++");
cache.put("5", "PHP");
cache.put("6", "RUBY");
System.out.println("第一次打印map,期望\"1\"被移除");
cache.entrySet().forEach(System.out::println);
cache.get("4");
System.out.println("第二次打印map,期望\"4\"在最新的位置");
cache.entrySet().forEach(System.out::println);
}
}

总结

HashMap1.8相比于jdk1.7的提升

  • 扩容方面:因为是两倍扩容,1.8的通过位运算,非常巧妙的避免了1.7中对每个元素调用rehash;扩容也是有序的,间接预防了1.7中的死循环问题。
  • Hash散列方面:1.8只将高16位和低16位进行了异或,而1.7中做了大量的异或操作。
  • hash碰撞方面:1.8当碰撞超过8次,将单链表转化为红黑树。这样即使在最坏的情况下也能达到O(lgn)的性能。

LinkedHashMapHashMap

  • LinkedHashMap继承于HashMap
  • LinkedHashMap提供更好的遍历性能
  • LinkedHashMap是有序的,这个有序是指插入/访问顺序。如果要求节点存放有序呢?请看TreeMap

参考

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。