HashMap在JDK1.8中的优化

小土豆Yuki

发布于 2020-11-11 16:10:59

7960

发布于 2020-11-11 16:10:59

文章被收录于专栏：洁癖是一只狗

HashMap作为常用的Map类，他是基于哈希表实现，继承了AbstractMap并实现了Map接口.

哈希表就是把hash值映射到内存地址，即根据键获取对应的值,并将其存储到内存地址，而HashMap是根据键值的hash值来决定对应值的存储位置，通过这种索引方式，HashMap获取数据的速度非常快。

当然根据hash值，会有多个值的hash值是一样的，这样就会发生Hash冲突，那么如何解决呢，其实有很多方案

开放地址法
在哈希函数法
链地址法

开放地址法，就是当发生冲突的时候，如果哈希表没有满，说明哈希表必然还有空位置，那么可以把key存放到冲突位置的后面，同时会带来查找，扩容等问题，因此不建议使用

在哈希函数法，就是产生地址冲突时，再计算另一个哈希函数地址，知道不冲突为止，这种方法不易产生聚集，但是增加了计算时间，如果我们不考虑计算时间，且对查询元素的要求较高，可以采用这种方式

而HashMap则综合考虑所有因素，采用链地址法，这种方式采用数组和链表的数据结构，当发生哈希冲突的时候，用一个链表结构存储hash值的数据

HashMap重要的属性

从HashMap的源码中,我们发现，HashMap是一个由一个Node数组构成，每个Node包含一个key-value键值对

transient Node<K,V>[] table;

Node类作为HashMap中的一个内部类，除了key,value两个属性，还定义一个next指针,当存在哈希冲突的时候,HashMap会把之前数组中相同的hash值对应的存储的Node指向新增的相同哈希值的Node对象的引用。

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K 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;
        }
}

HashMap还有两个重要的属性，加载因子(loadFactor)和边界值(threshold).在初始化HashMap时,就会涉及到这两个关键初始化参数

int threshold;
final float loadFactor;

loadFactor属性用来间接设置Entry数组的内存大小。他的初始值是0.75。为什么是0.75呢

这是因为使用链表法的哈希表来说,查找一个元素的平均时间是O(1+N),其中N是代表遍历链表的长度,因为加载因子是扩容的参考标准,如果加载因子过大，就会产生更多的哈希冲突，这样导致数组的链表长度增加，影响查询效率,比如,把0.75改成1，这个时候数组的长度为16的时候，才会进行扩容。

Entry数组的Threshold是通过初试容量和LoadFactor计算所得,默认情况下边界值=12，如果HashMap中的Node的数量超过边界值，HashMap就会调用resize方法重新分配table数组,这样会导致HashMap的数组复制，迁移到另外一块内存，从而影响HashMap的效率

HashMap添加元素

在初始化完后，当元素添加到HashMap中的时候，我们会调用put,首先会根据该key的hashCode()返回值,再通过hash()方法计算hashcode值，在通过putval方法中(n-1)&hash决定该Node的存储位置.

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


if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
//通过putVal方法中的(n - 1) & hash决定该Node的存储位置
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

为什么我们不是用对象的hashCode的值呢,比如添加两个对象a和b,如果数组的长度是16,使用（16-1)&a.hashCode和(16-1)&b.hashCode计算hash值,而15的二级制为0000000000000000000000000001111,假设对象a的hashCode为1000010001110001000001111000000,对象b的hashCode为0111011100111000101000010100000我会发现计算结果都是0,这样哈希结果就是不太优秀，不是好算法。

然后我们使用hashCode右移16位,(h>>>16)也就是去int的一半，刚好就可以将改二进制对半切开,并使用位异或运算,(如果两个数对应的位置相反，则为1，否则为0),

这样就能避免上面的情况发生,这就是hash()方法具体实现方法,尽量打乱hashCode真正参与运算低16位.

那为什么要设置成(n-1)&hash,那是因为哈希表习惯将长度设置为2的n次方,这样恰好计算你的索引值在数组table数组索引之内.

元素添加的逻辑

在获取Node位置后，如果存在不在哈希表中,就新增一个Node,并添加哈希表中,整个流程如下

从上面看到，如果链表的长度超过8的时候，链表就会转变成红黑树，因为我们不在担心链表过长导致查询时间复杂度的问题.


 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
//1、判断当table为null或者tab的长度为0时，即table尚未初始化，此时通过resize()方法得到初始化的table
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
//1.1、此处通过（n - 1） & hash 计算出的值作为tab的下标i，并另p表示tab[i]，也就是该链表第一个节点的位置。并判断p是否为null
            tab[i] = newNode(hash, key, value, null);
//1.1.1、当p为null时，表明tab[i]上没有任何元素，那么接下来就new第一个Node节点，调用newNode方法返回新节点赋值给tab[i]
        else {
//2.1下面进入p不为null的情况，有三种情况：p为链表节点；p为红黑树节点；p是链表节点但长度为临界长度TREEIFY_THRESHOLD，再插入任何元素就要变成红黑树了。
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
//2.1.1HashMap中判断key相同的条件是key的hash相同，并且符合equals方法。这里判断了p.key是否和插入的key相等，如果相等，则将p的引用赋给e

                e = p;
            else if (p instanceof TreeNode)
//2.1.2现在开始了第一种情况，p是红黑树节点，那么肯定插入后仍然是红黑树节点，所以我们直接强制转型p后调用TreeNode.putTreeVal方法，返回的引用赋给e
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//2.1.3接下里就是p为链表节点的情形，也就是上述说的另外两类情况：插入后还是链表/插入后转红黑树。另外，上行转型代码也说明了TreeNode是Node的一个子类
                for (int binCount = 0; ; ++binCount) {
//我们需要一个计数器来计算当前链表的元素个数，并遍历链表，binCount就是这个计数器

                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
// 插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度加1，而binCount并不包含新节点，所以判断时要将临界阈值减1
                            treeifyBin(tab, hash);
//当新长度满足转换条件时，调用treeifyBin方法，将该链表转换为红黑树
                        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;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

HashMap获取元素

当hashmap中只存在数组，而数组中没有Node链表时，是HashMap查询数据性能最好的时候，一旦发生大量冲突，就会产生链表，导致要遍历Node节点，从而降低查询数据的性能，

红黑树就是为了解决这个性能问题而引进的，使得查询的平均复杂度减低到了O(log(n)),链表越长，使用红黑树后查询效率提升越明显.

HashMap扩容

在1.7jdk中，HashMap整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表的元素，然后遍历以该元素为头的链表元素，一次遍历元素的hash值，计算在新数组中的下标，进行交换，这样扩容方式将原来哈希冲突的单项链表尾部变成了扩容后的头部。

扩容前

扩容后

而在 JDK 1.8 中，HashMap 对扩容操作做了优化。

HashMap初始化长度是16,扩容之后就是32，而length-1对应就是15和31,而计算存储位置的公式如下.

(n-1)&hash

15：0000 0000 0000 0000 0000 0000 0000 1111 (15的二进制)
31：0000 0000 0000 0000 0000 0000 0001 1111（31的二进制）

我们假设某个元素的的hashcode是52

52：0000 0000 0000 0000 0000 0000 0011 0100 (52的二进制)

(16-1)&52运算结果是4

4：0000 0000 0000 0000 0000 0000 0000 0100

(32-1)&52运算结果是20

20：0000 0000 0000 0000 0000 0000 0001 0100

我发现这个20=4+16，正好就是原位置+原数组的长度,我们在举个例子如下

某个元素的hashcode=100

100：0000 0000 0000 0000 0000 0000 0110 0100(100的二进制)

而(16-1)&100和(32-1)&100的计算结果都是4

4：0000 0000 0000 0000 0000 0000 0000 0100(4的二进制)

发现扩容之后存储位置没有发生变化。

因此证明，扩容之后，元素要么在原位置,要么在原位置加原位置的长度

可以看到，扩容之后元素的位置是否改变，完全取决于紫色框中的运算结果是0还是1,如果是0则新位置和原位置相同，如果是1,新位置=原位置+原数组长度,说明在jdk1.8中扩容并不用重新计算hash值。

为什么初始容量，一般都是2的整数次幂

使用2的整数次幂时候,使用(n-1)&hash计算和hash%n的计算结果一样,而&的运算速度比取模块.且可以保证不超过数组长度
n是2的次幂，则n-1转化为二进制必定是11111...的形式，在和元素的hash值与操作速度快，而且不浪费空间，比如如果长度是15，而n-1=14,而14的二进制是1110.在和元素的hash与操作之后，最后一位总是0，而某些位置永远不会存储元素，浪费空间

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap