HashMap

哈希表（hash table） 也叫散列表，是一种非常重要的数据结构。

应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，

关注博主不迷路，获取更多干货资源

我画的visio原图链接，有兴趣的同学可以在这个图上自己改

1
2
3
链接：https://pan.baidu.com/s/12Rx9pp2kBje2E46eayuRfw 
提取码：6666 
复制这段内容后打开百度网盘手机App，操作更方便哦--来自百度网盘超级会员V4的分享

1 基础

1.1 数组、链表和散列表

1.1.1 数组

优势：内存连续，查询效率高

劣势：插入效率低。大小固定，不可动态存储。

1.1.2 链表

优势：插入效率高

劣势：查询效率低

1.1.3 散列表

散列表：数组+链表

1.2 什么是哈希

Hash也称散列、哈希。基本原理是把任意长度的输入，通过Hash算法变成固定长度的输出.

这个映射的规则就是哈希算法，原始数据映射后的二进制串就是哈希值.

1.2.1 哈希的特点

1.从hash值不可以反向推出原始数据

2.输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的hash值。

3.hash算法的执行效率要高效，长的文本也要快速算出哈希值。

4.hash算法的冲突概率要小。

2 HashMap原理分析

2.1 HashMap存储原理

2.2 PutVal方法原理

2.3 Resize方法原理

3 手撕源码

3.1 常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 缺省数组容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大数组容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 缺省负载因子:(数组元素个数达到 容量*负载因子 时扩容)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 树化阈值
static final int TREEIFY_THRESHOLD = 8;

// 链化阈值
static final int UNTREEIFY_THRESHOLD = 6;

// HashMap中的个数达到64，并且链表长度达到8，才进行树化。(两个条件缺一不可)
static final int MIN_TREEIFY_CAPACITY = 64;

3.2 变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 整个哈希表，第一次put的时候才初始化(懒加载)
transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

//当前哈希表中的元素个数
transient int size;

//结构修改次数(插入、删除会引发结构变化，修改不会)
transient int modCount;

// 扩容阈值(哈希表中的元素超过这个时触发扩容，(capacity * load factor))
int threshold;

// 负载因子
final float loadFactor;

3.3 put方法

3.3.1 put方法

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

3.3.2 hash方法

可以看到key为null的值都放在数组索引0的位置，也就是HashMap可以存key为null的数据，但是这个数据只有一个。

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

3.3.3 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
56
57
58
59
60
61
62
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab:引用当前hashMap的散列表
    // p:当前散列表的元素
    // n:散列表数组的长度
    // i:路由寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, i;   
    // 延迟初始化逻辑，第一次调用putVal时会初始化hashMap
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 最简单的一种情况，寻址找到的桶位，刚好是null，这个时候，直接将k-v=>node 扔进去就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // e: 不为null的话，找到了一个与当前要插入的key一致的元素
        // k: 表示临时的一个key
        Node<K,V> e; K k;
        // 桶位中的该元素与要插入的元素的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) {            
                // 遍历的这个元素已经是链表的最后一个元素，也没有找到与要插入的元素key相同的node
                if ((e = p.next) == null) {                
                    //将元素插入到链表最后面
                    p.next = newNode(hash, key, value, null);                    
                    //元素个数达到树化阈值，进行树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                    
                        // 这里面会判断整个哈希表元素个数时候达到64(前面变量里的)，所以树化条件有两个。默认链表8个，哈希表64个，缺一不可
                        treeifyBin(tab, hash);
                    break;
                }                
                // 找到了一个与插入的元素的key相同的node
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }        
        // e不等于null，说明找到了与插入元素key相同的元素，替换值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    ++modCount;
    //插入新元素，size自增，如果自增后的值，大于扩容阈值，则触发扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.4 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
final Node<K,V>[] resize() {
    // oldTab:引用扩容前的哈希表
    Node<K,V>[] oldTab = table;
    // oldCap:扩容之前table数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // oldThr:扩容之前的扩容阈值，触发本次扩容的阈值
    int oldThr = threshold;
    // newCap:扩容之后数组的大小
    // newThr:扩容之后，下次再次触发扩容的阈值
    int newCap, newThr = 0;
    // 条件如果成立，说明hashMap中的散列表已经初始化过了，是一次正常扩容
    if (oldCap > 0) {
        // 扩容之前的table数组大小已经达到最大阈值后，则不扩容，且设置扩容条件为int的最大值。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 这里oldCap<<1很关键，是说扩容后的容量是扩容前的2倍， newCap小于数组最大值限制 且 扩容之前的阈值>=16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新的扩容阈值翻倍
            newThr = oldThr << 1; // double threshold
    }
    // oldCap == 0，说明hashMap中的散列表还没有初始化，是null
    // 1.new HashMap(initCap,loadFactor);
    // 2.new HashMap(initCap);
    // 3.new HashMap(map);//并且这个map有数据
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap == 0，说明hashMap中的散列表还没有初始化，是null
    //new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr为0时，通过newCap和loadFactor计算出一个newThr
    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;
    // 说明HashMap本次扩容之前，table不为null
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            // 当前遍历的Node节点
            Node<K,V> e;
            // 说明数组的中头节点不为空，至于里面是单个数据还是链表还是红黑树并不知道
            if ((e = oldTab[j]) != null) {
                // 置空，方便JVM GC时回收内存
                oldTab[j] = null;
                // 第一种情况：说明数组的这个桶中是单个元素，没有碰撞，这种情况直接计算出当前元素在新数组中的位置，扔进去就好了
                if (e.next == null)
                    // 寻址put数据即可
                    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;
                    //遍历这个链表，直到某个元素的next指向null(最后一个元素)
                    do {
                        next = e.next;
                        // 以15桶为例： 
                        //      hash -> ....1 1111
                        //      hash -> ....0 1111
                        
                        // 成立说明放在低位链中
                        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;
}

4 为什么选用红黑树

红黑树是一种近乎平衡的二叉查询树

二叉查询树最差的时间复杂度是0(n)，也就是数据是一条链的时候，这个肯定不适合
二叉平衡树的话，查询性能很好 0(logn)，但是几乎每次插入数据，都会破坏平衡性，从而产生自平衡操作，很浪费性能。
红黑树是二叉平衡树的变体，保证了近乎平衡的同时，插入数据不会频繁影响平衡性，不会频繁的进行自平衡操作，不像二叉平衡树那样。

5 HashMap 为什么是线程不安全的

5.1 插入数据的时候

AB线程同时插入，两个计算除了相同的哈希值，对应数组的相同位置，第一个线程写了数据后，第二个线程再写，不就覆盖了。

5.2 扩容的时候

第一步：线程2已经将1和2元素弄好了，这时候挂起

第二步：线程1将弄好。

第三步：线程2找到2节点的next，发现是1，然后把1插进去，就是1指向2，如图中红色箭头，死循环了。

5.3 ……

关注博主不迷路

联系博主

编程 Java
Java HashMap

本博客所有文章除特别声明外，均为原创。版权归博主小马所有。任何团体、机构、媒体、网站、公众号及个人不得转载。如需转载，请联系博主(关于页面)。如其他团体、机构、媒体、网站、博客或个人未经博主允许擅自转载使用，请自负版权等法律责任！