jdk1.8 HashMap原理_hashmap1.8扩容机制

哈希表

在学习hashmap前，先了解一下哈希表。

哈希函数：

Hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表。比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。　存储位置 = f(关键字) 这个函数f一般称为哈希函数。

哈希表

哈希表是一种数据结构，主干就是数组，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到。

哈希冲突

如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？
也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。

哈希冲突的解决方案有：

• 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）
• 再散列函数法
• 链地址法
  HashMap即是采用了链地址法，也就是数组+链表的方式

HashMap原理

概述

HashMap在底层数据结构上采用了数组＋链表＋红黑树，会根据key的hashCode值来确定数组的索引(确认放在哪个桶里)。如果发生hash冲突，HashMap会将同一个桶中的数据以链表的形式存储，但是如果发生hash冲突的概率比较高，就会导致同一个桶中的链表长度过长，遍历效率降低，所以在JDK1.8中如果链表长度到达阀值(默认是8)，就会将链表转换成红黑二叉树。

HashMap数据结构

//Node本质上是一个Map.存储着key-value
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;             //保存该桶的hash值
    final K key;                //不可变的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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

有时候两个key的hashCode可能会定位到一个桶中，这时就发生了hash冲突，如果HashMap的hash算法越散列，那么发生hash冲突的概率越低，如果数组越大，那么发生hash冲突的概率也会越低，但是数组越大带来的空间开销越多，但是遍历速度越快，这就要在空间和时间上进行权衡，这就要看看HashMap的扩容机制，在说扩容机制之前先看几个比较重要的字段。

//默认桶16个
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//默认桶最多有2^30个
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认负载因子是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//能容纳最多key_value对的个数
 int threshold;

//一共key_value对个数
int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

threshold=负载因子 * length，也就是说数组长度固定以后， 如果负载因子越大，所能容纳的元素个数越多，如果超过这个值就会进行扩容(默认是扩容为原来的2倍)。
size就是HashMap中键值对的总个数。还有一个字段是modCount，记录是发生内部结构变化的次数，如果put值，但是put的值是覆盖原有的值，这样是不算内部结构变化的。
因为HashMap扩容每次都是扩容为原来的2倍，所以length总是2的次方，这是非常规的设置，常规设置是把桶的大小设置为素数，因为素数发生hash冲突的概率要小于合数，比如：HashTable的默认值设置为11，就是桶的大小为素数的应用(HashTable扩容后不能保证是素数)。HashMap采用这种设置是为了在取模和扩容的时候做出优化。

确定哈希桶数据索引位置

//根据key计算出哈希值
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//jdk1.7的源码，jdk1.8没有这个方法
//利用计算出来的哈希值求出索引位置
static int indexFor(int h, int length) {  
     return h & (length-1);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

为什么算出来的哈希值不是与数组长度取余而是用与运算？
取余也是可以的，但是计算机中直接求余效率不如位移运算。
hash%length==hash&(length-1)的前提是length是2的n次方。
为什么这样能均匀分布减少碰撞呢？
2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
例如：
16->10000 15->1111
32->100000 31->11111
64->1000000 63->111111
所以数组长度-1 的二进制都是1

数组每次扩容都是2的次方，然后再-1，比如：15,31,63.。。它的二进制的低四位，都是1111，那么（数组长度-1）& hash 与hash值进行与运算的时候，结果就只取决于hash值了

异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
与运算：即：两位同时为“1”，结果才为“1”，否则为0
二进制：十进制转二进制

十进制的123转成二进制就是1111011，转成几进制都是一个道理。
二进制转十进制：
例：01001110 = 2^6 + 2^3 + 2^2 + 2^1 = 64 + 8 + 4 + 2 = 78
左移:1<<4 就是2的4次方等于16

HashMap的put方法实现

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
//判断table是否为空，如果是空的就创建一个table，并获取他的长度
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
//如果计算出来的索引位置之前没有放过数据，就直接放入，jdk8没有indexFor方法来计算索引位置，直接在这用(n - 1) & hash
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
//进入这里说明索引位置已经放入过数据了
            Node<K,V> e; K k;
//判断put的数据和之前的数据是否重复
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))   //key的地址或key的equals()只要有一个相等就认为key重复了，就直接覆盖原来key的value
                // 这里赋值的还是旧数据，在下面 if (e != null)这里把value给更新为新数据了
                e = p;
//判断是否是红黑树，如果是红黑树就直接插入树中
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//如果不是红黑树，就遍历每个节点，判断链表长度是否大于8，如果大于就转换为红黑树
                for (int binCount = 0; ; ++binCount) {
                    //判断下一个节点是否为null,如果是直接在链表尾部添加元素
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
//判断索引每个元素的key是否可要插入的key相同，如果相同就直接覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
//如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
//说明没有key相同，因此要插入一个key-value，并记录内部结构变化次数
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
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

1.table[]是否为空，计算索引位置
2.判断table[i]处是否插入过值，没有直接放入数据
3.判断put的数据和之前的数据是否重复,跳出了循环，说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
4.判断是否是红黑树，如果是红黑树就直接插入树中
5.如果不是红黑树，就遍历每个节点，判断链表长度是否大于8，如果大于就转换为红黑树
6.判断下一个节点是否为null,如果是直接在链表尾部添加元素
7.记录结构变化一次并判断是否需要扩容

HashMap的get方法实现

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果表不是空的，并且要查找索引处有值，就判断位于第一个的key是否是要查找的key
        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 {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

扩容机制

我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。

附录

HashMap JDK1.8实现原理:
https://www.cnblogs.com/duodushuduokanbao/p/9492952.html
3分钟轻松理解HashMap原理:
https://www.bilibili.com/video/BV1oE411n7ug?from=search&seid=6070621214765255468
二进制详解:
https://blog.csdn.net/u014535295/article/details/80804777