HashMap源码剖析JDK1.8

作者: 串串番茄 | 来源:发表于2019-12-18 11:17 被阅读0次

背景

在JDK1.2的 java.util 包中增加了一个 Collection 接口和 Map<K,V> 接口，用于对不同类型的元素进行操作。 Map<K,V> 接口主要用于存储以 Key-Value 形式的元素，其中 HashMap 就是 Map 接口的一个实现类。

名词介绍

比特：二进制数字中的位，信息量的度量单位，为信息量的最小单位。二进制数系统中，每个0或1就是一个位(bit)，位是数据存储的最小单位。其中8bit就称为一个字节（Byte）。

设计猜想

在探究源码之前，首先我们先尝试用自己的逻辑来设计下HashMap<K,V>的数据结构。在我们熟悉的数据结构中有一种hash表的数据结构符合HashMap的存储要求。

[散列表](Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

在设计HashMap中需要关注的几个方面:

数组大小、类型一旦确定，编译、运行时都不可修改，必须对HashMap的数组进行动态扩容。
通过Key计算得到的Hash值，必须保证元素都能正确的被保存，需要考虑hash冲突的影响。

设计思路

通过计算key的hash值，然后对hash值和数组size进行取模运算得到一个数组的索引，将元素A添加到数组中，如果出现索引相同且Value对象不相等，则将元素添加到元素A后面。这里要求数组中的元素必须是一个Node节点，用于添加元素。
如果数组容量已经超过一定范围，对数组进行动态扩容，复制一个新的数组，将旧数组的元素重新计算hash值放入新数组中。
如果链表的长度超过一定范围，则将链表转换成红黑树降低查找的复杂度。

img

根据我们的猜想，我们可以通过HashMap源码进行验证。

源码分析

1.计算Key的hash值

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {}

int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

其中 hash(key) 方法就是计算key的hash值， (h = key.hashCode()) ^ (h >>> 16) 使用高位16位和低16位异或运算得到Hash值，主要为了使hash分布尽可能的均匀。

img

2.初始化数组

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) {
            //............
        }else if (oldThr > 0) // initial capacity was placed in threshold
        //............ 
        else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//............
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

通过resize()方法创建一个初始容量为 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ，负载因子为 static final float DEFAULT_LOAD_FACTOR = 0.75f 的 Node 数组( Node 实现 Map.Entry 接口)。

3.存放元素

3.1数组索引位置上没有元素

计算数组 (n - 1) & hash 位置上是否存在元素，如果该索引位置上没有元素，则直接将新数据插入数据。

这里利用&运算的特性:
这里约定数组大小必须是2的幂函数，这样才能保证n-1&hash值为数组索引值。

hash	1010010101001010101	1010010101001001111
n-1	0000000000000001111	0000000000000001111
(n-1)&hash	0000000000000000101=5	0000000000000001111 =15

精妙之处在于这里利用 & 运算的特性，保证n-1二进制最大位为0，则计算结果就等于数组下标，&相比于传统的取模运算性能更优。

3.2 数组索引位置存在元素

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
// ............
        else {
            Node<K,V> e; K k;
            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) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break; 
                    }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
p = e; }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
} }
//............

这里分3中情况来分析:

如果数组索引位置的元素的key和新元素的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);

如果数组索引位置的元素仍是一个链表节点，则遍历这个节点，如果链表长度大于8则转换成红黑树，否则直接新增一个节点添加到链表的表尾。

 
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
        break; 
    }
    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e; 
}

扩容机制

我们知道集合接口的出现主要是解决数组长度、类型固定的限制。实现机制主要是利用引用类型和数组动态扩容来实现。 HashMap 实现 Map 接口的集合， HashMap 的扩容机制是怎样的呢?

猜想:如果数组容量小于数组容量的75%,我们就实现动态扩容一倍。原先数组上的链表需要重新根据新数组索引号进行分配。

1.发生扩容的触发条件

if (++size > threshold)
    resize();

数组size大于 threshold 时进行扩容。

2.数组扩容操作

 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

这里使用 newCap = oldCap << 1 给新数组进行扩容，同时设置阈值 newThr = oldThr << 1 。

3.遍历旧数组转移至新数组

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;
                            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;
                        } 
                    }
                } 
            }
        }

3.1仅一个元素

 if (e.next == null)
   newTab[e.hash & (newCap - 1)] = e;

旧数组索引位置仅含有一个元素，将旧数组索引的元素转移至新数组相同索引位置上。

3.2元素为红黑树

 else if (e instanceof TreeNode)
    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

旧数组索引位置元素为红黑树时，执行红黑树的方法

3.3元素为链表

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;
}

这里利用了 (e.hash & oldCap) == 0 算法实现链表元素位置控制:

1.如果(e.hash & oldCap) == 0，则数组位置不变
2.如果(e.hash & oldCap) != 0,则数组位置为原位置+OldCap

hash	101011010101010101	101011010101000101
oldcap	000000000000010000	000000000000010000
e.hash & oldCap	000000000000010000=16	000000000000000000=0
新元素位置	Node[i]=Node[i+OldCap.length]	Node[i]=Node[i]

参考链接

HashMap源码分析

Hash表百度百科