专栏首页洁癖是一只狗HashMap在JDK1.8中的优化

HashMap在JDK1.8中的优化

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

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

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

  1. 开放地址法
  2. 在哈希函数法
  3. 链地址法

开放地址法,就是当发生冲突的时候,如果哈希表没有满,说明哈希表必然还有空位置,那么可以把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的整数次幂

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

本文分享自微信公众号 - 洁癖是一只狗(rookie-dog),作者:洁癖汪

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HashMap源码

    在put源码中,且有一段循环遍历就是为了防止存在相同的 key 值,若发现两个 hash 值(key)相同时,HashMap 的处理方式是用新 value 替换...

    小土豆Yuki
  • 简单的Python 使用(一)

    Python的设计具有很强的可读性,相比其他语言经常使用英文关键字,其他语言的一些标点符号,它具有比其他语言更有特色语法结构。

    小土豆Yuki
  • Mysql基础篇--面试锁机制

    数据库锁就是一种保证数据一致性而使各种共享资源在被并发访问,并发访问人有序所设计的一种规则。

    小土豆Yuki
  • HashMap常见问题(更新中)

    对每个hash值,将他的高低十六位进行异或操作,让低十六位同时保持了高低十六位的特征。同时也可以避免一些hash值后续出现冲突。

    宇宙之一粟
  • 【数据科学】9个针对初学者的数据科学公开课

    如果你想自学,网络是一个非常好的地方,这里有太多的资源,有大神 Devendra Desale就挑选出了网络公开课中优秀的数据科学课程推荐给大家。 关于这些课程...

    陆勤_数据人网
  • 使用 ebpf 深入分析容器网络 dup 包问题

    大家好,我是杨玉玺,2011年至今一直从事底层网络研发,先后就职于阿里云、金山云从事 VPC 虚拟化网络研发,对高性能网络优化,复杂网络问题排查有非常丰富的经验...

    灵雀云
  • 使用 Vue3 重构 Vue2 项目(长文)

    2020年9月18日,vue3正式版发布了,前几天把文档整体读了一遍,感触很深,可以解决我项目中的一些痛点,于是就决定重构之前那个vue2的开源项目。

    coder_koala
  • PostgreSQL中删除的数据能否恢复

    问题的提出 有人问PostgreSQL数据库中刚刚删除的数据能否被恢复? 或更进一步,如果如要在一个事务中做了一系列的更新、删除、插入的操作后,把这个事务提交之...

    沃趣科技
  • 机器人操作系统(ROS)在线实训平台学习实验指南

          在高校开设ROS相关课程已经积累了一年多的经验,由于自动化类专业在课程安排中不同于计算机相关专业,通常没有Linux相关的课程基础,直接上手ROS较...

    zhangrelay
  • 分布式架构设计篇(九)-柔性事务之Saga详解

    ​ Saga模型起源于1987年 Hector Garcia-Molina,Kenneth Salem 发表的论文《Sagas》,是分布式事务相关概念...

    林淮川

扫码关注云+社区

领取腾讯云代金券