jdk1.8源码填坑计划-5-Map

这里是个开局两张图,内容全靠编系列的下集。

集合

集合

Map接口

Map是个接口,日常都把它归属于集合类中,但是它和Collection接口是同一等级的,这也是集合类的另外一个分支。在Set中,很多Set的实现都是采用了Map的实现来改造来的,所以Map这一数据结构的源码是比较重要的,面试一定会问,感觉这一篇会写挺多东西的。
Map的实现在java.util包中有HashMap LinkedHashMap TreeMap WeakHashMap IdentityHashMap EnumMap Properties 还有临近淘汰的HashTable。要全部写完这些是很困难的,也要花挺多精力的,这里我就捡一些感觉自己觉得神奇的写。

HashMap

hash这个单词就是把…弄碎弄乱的意思,所以这就是散列。对于Java的所有对象都有hashCode,我们利用这一特性设计HashMap。简而言之,对于放入Map集合的对象求一个独特的数值作为其hash值,然后把值存起来,这样下次查找的时候可以根据hashCode直接寻址,马上就找到对应的数据,其查询时间复杂度位O(1)级别。
HashMap利用这种方法来存储,先用key的Hash算法存储在数组中,然后各个数组元素中存放链表来存储hash算法结果相同的键值对,在java1.8中引入了红黑树,当某个链表超度超过8时,转为红黑树来存储,如下图所示。

map

基本构成

图中已经标识了HashMap的基本构成,可以看到HashMap使用一个Node数组来存储数据,Node中包含了next构成链表。特殊情况下,树化(treeify)的时候会转换为treeNode结构。

1
2
3
4
5
6
7
8
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ......
}
transient Node<K,V>[] table;

容量和扩容

我的源码计划最开始的时候就是受这个问题影响开启的,HashMap什么时候扩容,怎么扩容。由于table这个数组是指定容量的,所以需要扩容,什么时候开启扩容取决于HashMap设定的一个初始值

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

这两个值分别定义了table的默认初始容量和默认负载因子。
负载因子loadFactor其实是动态的,是数组中有值的数量 / 数组总容量,所以当设置负载因为为0.75,容量为16时,16*0.75=12 也就是当table中数量超过12,就会对HashMap的table进行扩容(只有扩容没有缩容)。
那么扩容到底扩到多大呢?table数组的容量越大肯定是越稀疏用起来越好,但是过大只会占用不必要的空间,最终HashMap采用的算法是最选择最靠近实际容量的2^n的数作为容量,这样的话扩容就是在原来的容量上乘2。那么为什么偏偏选择这种做法呢?这和对key求hash放入的table坐标有关,这样做也有非常多的好处。

hash和table坐标

不应该叫hash和table坐标,应该叫“根据key计算hash来确定table数组索引位置的原则”。

1
2
3
4
5
6
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// .......
tab[(capacity - 1) & hash] = new Node<>(hash, key, value, null);

取hash的步骤:取key的hashCode、右移16位只要高位、原高位与低位进行异或,取得的值作为hash,这样可以使获得的hash值相对于单纯的hashCode来的更加稀疏。给定一个hash,要确定放到table中的位置最好的方法就是对容量进行取模hash%capacity,但是众所周知,取模运算时出了名的效率差。所以这里就可以看出来设置容量是2^n的好处了,当capacity为2^n时: (capacity-1) & hash = hash%capacity。(这对于大学时经常处理单片机程序的我来说,是经常做的操作,所以没有什么是白白经历的,一定都有用

hash和位置

再看扩容

看了根据key计算hash来确定table数组索引位置的原则之后再来看HashMap的扩容,问题来了:扩容之后,原来的hash不变,但是对应的位置是不是应该重新计算了?很明显,是的,全部都要重新计算。那么怎么重新计算更合理呢?1.8加入了更加巧妙的机制,这个机制还是依赖于HashMap容量为2^n,并且扩容2倍这一特性。扩容之后计算的坐标(newCapacity - 1) & hash要么等于原来的值,要么等于(oldCapacity - 1) & hash + oldCapacity,至于等于哪一个完全取决于hash值再扩容的那一位是为0还是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
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
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;
}
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;
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
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 这里判定新增的那一位是不是0 是0就再原位置的链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 不是0就放入原位置+oldCap的链表
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;
}

a是扩容前的状态,b是扩容后的状态
扩容后位置变化

下图是从16扩容到32发生的变化,取决于hash的在旧的2^n的第n-1位的二进制值 0就不动 1就要移动到原位置+oldCap中去。
扩容后位置变化

是怎么树化的

为什么要树化?

假设hash真的就重复了,超多重复,我们当然都不希望这种事情发生,假设这种事情每次都发生,那HashMap就退化成了LinkedList,查找性能也就很差了。HashMap为了防止table[i]中的数据链表过长影响性能,所以当这个链表过长的时候进行树化处理(JDK1.8加入的)。

凭什么偏偏是8?

为什么是8这个事情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
/* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*/
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

那么为什么符合泊松分布呢?

  • hash重复是小概率时间。
  • 这次的key的hash和上次的key的hash互不影响。
  • key的hash重复的概率是确定的。

显然这事件是符合泊松分布的,但是为何在负载因子为0.75的时候概率是0.5我无法理解,就暂且按照0.5来计算吧。
所以概率公式为 (exp(-0.5) * pow(0.5, k) / (k!)
当k=8时,概率已经足够小,所以很难出现树化的情况,就算出现了,这时候查找为O(logN), 平均3次,好于链表的平均4次,树化是很有意义的。
当k=6时,概率相对比较大,红黑树查找相对于链表查找没有优势,而且树化也需要不少时间,这时候就退化为链表。
所以作者选择了6和8,中间还有一个7,防止了频繁树化频繁链表化。

凭什么又偏偏是红黑树?

我连红黑树是什么都搞不清,就先不写这个了。TreeMap中整个都是采用红黑树来做的,所以放在TreeMap中来写吧。。。我这辈子都搞不清楚这个了。

二叉查找树

假设设置了一个二叉查找树,排好序的,并且不再插入其他值的,那么这个查找的复杂度将近似于折半查找,最好能够O(logN),但是如果这个二叉树只有很少的元素,比如一个,之后插入的元素都比这个元素大或者小,那这个树就会退化为链表,查找性能直接退化为O(N)。正是由于这种缺陷,所以,要找出来一个不那么容易退化为链表的数据结构,于是有人发明了其他的树形结构。
说白了,树本身就是一个链表构成的结构,所以本质上这就是个复杂的多条支链的链表。

avl树

这是一个平衡二叉树,任何节点的两个子树的高度最大差别为1。当一侧的树(左或者右)过长的时候进行左右旋转,右边过长就左旋,左边过长就右旋,另外两种情况可以采用一次左旋和一次右旋来完成,用这种一只变动的方式来完成树的平衡,防止一边过大,出现树退化的情况。

红黑树

人们很快就在计算机中实现了链表这一数据结构,在这的基础上很快实现的异构的链表,也就是树,将树中的元素排序后构建成二叉查找树,又过了几年才发明avl树,又过了7年才提出了红黑色树,所以指望我能在几天内了解清楚红黑树是很难的,我还是放在TreeMap中用专门来了解清楚吧。

————–本来这是个填坑计划,现在看来坑越挖越多了。

遍历

有很多篇博客讲了HashMap的四种遍历方式,有的还把jdk1.8的lambda表达式的遍历算一种,其实不是,这只是一个语法糖而已,不是什么新东西。

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
//1、分别获取key和value的集合
for(String key : map.keySet()){
System.out.println(key);
}
for(Object value : map.values()){
System.out.println(value);
}
  

//2、获取key集合,然后遍历key,根据key得到 value 最坏的做法
Set<String> keySet = map.keySet();
for(String str : keySet){
System.out.println(str+"-"+map.get(str));
}

//3、得到 Entry 集合,然后遍历 Entry 这种最快
Set<Map.Entry<String,Object>> entrySet = map.entrySet();
for(Map.Entry<String,Object> entry : entrySet){
System.out.println(entry.getKey()+"-"+entry.getValue());
}

//4、迭代 这种也可以并且还可以直接增删map里面的东西不会ConcurrentModificationException
Iterator<Map.Entry<String,Object>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<String,Object> mapEntry = iterator.next();
System.out.println(mapEntry.getKey()+"-"+mapEntry.getValue());
}

//5、lambda表达式 这就是个语法糖 编译完是4(我猜的) 尚未证实
map.forEach((k, v) -> System.out.println("key: " + k + " value:" + v));

不该用什么做key

那么我们不该用什么做key,这个问题我从没有思考过,也从没在网络上看到过,只是在看jdk源码,又联想到之前String中所描述的,String是一个不可变对象(immutable objects),想到这一问题,那么我们加入设置了一个可变对象来做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
public class MutableKey {
int i;
int j;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + i;
result = prime * result + j;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof MutableKey)) {
return false;
}
MutableKey other = (MutableKey) obj;
if (i != other.i) {
return false;
}
if (j != other.j) {
return false;
}
return true;
}

按照原来HashMap的说法,一个做key的对象重写了hashCode和equals的,但是这里仍然会有问题,比如i和j的值发生变化,其hash也发生了变化,这时间这个对象已经根据旧的hash存储在了hashMap中,所以拿新的hash去查找的时候,永远都找不到了。。
所以最好的做法就是使用String、Integer等不可变对象做key,假如实在需要自定义的对象来做key,那只能一定要注意重写hash的时候一定要使用final的属性来计算hash!!!例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class ImmutableKey {
private int i;
// i 变成了不可变属性
public Employee(final int i) {
this.i = i;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + i;
return result;
}
//......
}

LinkedHashMap

LinkedHashMap继承了HashMap只是在HashMap的基础上又添加了一些特性,它把所有的Entry做成了一个双向链表,这样就可以按照顺序来输出Map中的内容。相比于HashMap,LinkedHashMap最大的特征就是有序,为了实现有序付出的代价就是这个双向链表在时间和空间上的开销。HashMap中有不少空方法,其实大多都是给LinkedHashMap准备的。

构造方法

LinkedHashMap新增加的关键成员如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;

/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;

/**
* The iteration ordering method for this linked hash map:
* true for access-order
* false for insertion-order.
*
* @serial
*/
final boolean accessOrder;

包含了双向链表的头和尾,还包含了排序方法。
对应的,LinkedHashMap新增的关键构造方法,这里可以配置accessOrder来指定LinkedHashMap的顺序(默认accessOrder为false):

1
2
3
4
5
6
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

双向链表

为了实现双向链表,继承HashMap的基础上添加了head和tail这两个作为链表的头尾;继承HashMap的内部类Entry,添加了before和after这两个属性。

1
2
3
4
5
6
7
8
9
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;

Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
//...
}

LinkedHashMap

LinkedHashMap

(图是抄的,侵删)
上面两张图标注了LinkedHashMap实现双向链表的方式,依靠head和tail记录头尾,依靠before和after来记录前驱节点和后继节点。

FIFO和LRU

很久以前我就知道FIFO,我还知道LIFO,这些都是大学时的基础知识,之前做单片机的编程的时候经常用这些,FPGA中也用到这些,但是我从没用过LRU(Least recently used 最近最少使用),就只在Redis中听说过LRU这种方式。FIFO就是水管,先进来的水先出去,LIFO就是手枪弹夹,后进来的子弹最先被打出去。
简单来说,LRU的原则就是被访问的数据放到链表头部(或者尾部),链表满了就舍弃掉之前没被访问的元素。LRU满足两种场景,数据被访问过那么将来被访问的概率比较大或者数据被访问过那么将来被访问的概率比较小,也就是说当存在热点数据时,LRU效率挺高,当时偶发性周期性的操作时,LRU的效率会很低,并且有固定容量的缓存LRU会出现缓存污染的情况。
LRU

那么LinkedHashMap是如何实现LRU和FIFO的呢?就在于accessOrder,设置为true,就是access-order,否则就是insertion-order。这里的access-order包含两种情况一是插入数据,二是访问数据,都算作access。LinkedHashMap是不会淘汰掉数据的,同时这又是实现了双向链表的,所以当LRU用的时候,完全可以直接用。倘若要做淘汰算法,只需要重写removeEldestEntry方法。

1
2
3
4
5
6
7
8
9
10
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}

@Override
private static final int MAX_ENTRIES = 100;
// 最大只能存100个元素
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}

LinkedHashMap的LRU到底是不是反的?我也解释不清楚,但是我知道设置了accessOrder=true最近被访问的元素就会放在尾部,也就是放在head节点的before,放在tail节点的after,LinkedHashMap的轮询方法是通过head来找的,所以更不容易命中之前的访问过的方法,按这种逻辑来说这确实是LRU。但是也可以重写轮询,从tail节点开始根据before来轮询,这样就变成了MRU(most recently used 最近最多使用),当然这只是一种思路,也没人那么干。
Mybatis的缓存就是个标准的LinkedHashMap实现的LRU,叫做LruCache,可以一看。

总的来说,LinkedHashMap是有序的,可以用访问顺序和插入顺序两种方式,如果不使用迭代轮询,就和HashMap没有多大的差别(而且性能更差),但如果使用轮询,其迭代比HashMap要快。

TreeMap

真的应该改名:jdk1.8源码挖坑系列。也是够够的。我的同事说你怎么叹气比我还多,我回答是欲望啊,没有欲望就不难过了。还是硬着头皮写下去吧。
决定参考《红黑树并没有我们想象的那么难》 来写这个。
TreeMap就是用红黑树来实现的一个Map,所以前面的那个红黑树的坑还是先填好。

又一个红黑树

红黑树
红黑树遵循的规则如下:

  • 性质1. 节点是红色或黑色。
  • 性质2. 根是黑色。
  • 性质3. 所有叶子都是黑色(叶子是NIL节点)。
  • 性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 性质5. 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
1
2
3
4
5
6
7
8
9
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
//......
}

红黑树插入

根据查找二叉树来插入数据非常简单,根据根节点插入即可,大了就往右边找,小了就往左边找。红黑树也是带排序的,所以科研用这一性质,但是为了保证红黑树的性质,需要修改插入的方式:

  • 新插入的节点是红色的。
  • 如果插入的节点的父节点是黑色,那就保持不变。
  • 如果插入的节点的父节点是红色,需要对节点进行变色和旋转来保证红黑树的性质。

红黑树0

所以插入会带来五种不同的情况

  1. N为根节点,直接插入N,然后转成黑。
  2. N的父节点为黑节点,直接插入N。
  3. PU是红色,插入N,需要调整PU为黑色,调整G为红色,调整G为黑色。
    红黑树3
  1. P为红,N为P的左节点,P做右旋,旋转完交换PG的颜色,达到平衡。
    红黑树4
  1. P为红,N为P右节点,N做左旋转,旋转完进入4
    红黑树5

红黑树删除

不写了,太难了,删除不搞了

排序

TreeMap利用红黑树来实现按照key排序,作为TreeMap的key默认使用Object的compare接口,所以TreeMap没办法拿null来作为key。但是如果重写了compare接口就可以这么做了,但是get(null)这种依然会有问题,这就是个很无聊的问题,无非就是getEntryUsingComparator(null)最终输出null,不讨论了。所以TreeMap非要把null放入,那最后只能靠轮询获取到null对应的value。所以不要妄图把null放到TreeMap中,费力不讨好。

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeMap<String, Integer> ts = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if (s1 == null){
return 1;
else {
return s2.charAt(0) - s1.charAt(0);
}
}
});
ts.put("一", 1);
ts.put("二", 2);
ts.put(null, 3);

要不TreeMap就这样吧,不写了

剩下WeakHashMap我先不写了,坑挖的太大,要填不上了,就先不开新坑了,接下来是concurrent包下的东西了。至于HashTable这种被淘汰的物件,我也先不看了。

2019年3月26日
葛祥海

0%