HashMap很细的分析令人发指

2023年 10月 12日 49.2k 0

前言

在说HashMap之前,我们先说一说hash冲突。当数据通过hash算法求得hash值的时候,是不可避免的出现相同的hash值,这也叫做hash冲突。通常我们会采用4种方式去应对hash冲突的情况。

  • 开放地址法: 当出现冲突的时候,用这个hash值+增量序列然后对散列表长度取模得到地址,这个增量序列通常有三种方式获取。第一种就是线性探测,当冲突之后,往后一个一个找,直到找到空位。第二种是二次探测,也就是反复横跳着找,比如1,-1,2,-2,3,-3。第三种就是伪随机法 取个伪随机数。
  • 链地址法: HashMap采用的就是这种方式,当冲突的时候,所有hash冲突的数据挂在一条链路上,处理冲突很简单,插入也快,但是查找效率不高。
  • 公共溢出区: 就是字面意思,所有冲突的单独放一起。
  • 再hash法: 也是字面意思,就是不断的hash,直到没有冲突。
  • HashMap的简介

    HashMap是基于映射(键值对)处理的数据数据结构。是程序员使用的频率最高的数据结构之一,在jdk1.8之后引入红黑树,优化底层数据结构。
    传统的数据的数据结构是在内存中申请一段连续的内存空间,查询的时间复杂度为O(1),而插入和删除是O(n),这是因为伴随着数据的移动。

    在Java7中数组+链表的形式,一旦链表过长那么会很影响put和get的效率,所以在Java8之后引入了红黑树+链表来代替链表。

    为什么不一直使用链表?

    我们是很清楚链表的弊端的,就是查询的效率很低,是O(n),当数据量很大的时候是不能接受这样的查询效率的。在JDK1.8之前它的结构大概是这样的

    HashMap1.7结构.png

    所以会一直花费心思在扰动函数上,让hash的更加分散。

    为什么选择红黑树?

    我们通过比较几种树的特性来说为什么选择了红黑树。

    二叉查找树

    我们最常见的就是二叉查找树,它的特点就是左节点永远都比它的父节点小,右节点一定比它的父节点大,比如下图

    二叉树正常.png

    但是它有个很大的问题,就是容易瘸腿,比如下面

    二叉树不正常.png

    当瘸腿的时候,你会发现这和链表没啥区别了。然后就出现了下面这个树。

    平衡二叉树

    这个树的特性就是每一个节点的左子树和右子树的高度差至多等于1,如果大于1就需要进行左旋或者右旋,这样就保证了它的查询的时间复杂度始终保持在O(LogN)。如下图

    image.png

    虽然查询满足了我们的需求,但是它的问题是在插入和删除的时候维护树上面复杂很多,需要频繁的调整树结构来保证查询效率,所以就引申出了红黑树

    红黑树

    相对于平衡二叉树,它的特点如下

    • 根节点是黑色的。
    • 所有的叶子节点都是黑色的,并且不存数据。
    • 任何相邻的节点不能同时为红色,红色节点是被黑色节点隔开的。
    • 每个节点到达它可达的叶子节点的路径,都经过相同数目的黑色节点。

    主要优点就是:它不追求绝对的平衡,插入最多两次旋转,删除最多三次旋转。

    具体的实现我会单独的放到我数据结构专栏,太复杂了。。。

    HashMap什么时机会从链表转为红黑树?什么时候再转回来呢?

    在上面我说了,JDK1.8之后是链表+红黑树来替代的链表,组合的意思就是代表着这两种数据结构是需要切换的,这个时机就是链表长度到达8的时候进行切换,当然这个只是条件之一,还有一个条件是想转换为红黑树,table中,也就是hash表的横向容量必须达到64,否则就会优先resize hash表。等讲完resize的方法的时候再总结一下HashMap中的存储数据的结构。所以就引出一些疑问。

    为什么不在hash冲突的时候直接就使用红黑树呢?

    因为红黑树的空间是链表的两倍,虽然能提升查询效率,但是插入的速度慢了很多,还涉及到平衡树的时候的各种旋转变色,所以链表其实是起到一个缓冲的作用。

    为什么要到达8的时候转为红黑树呢?

    原文注释上说,当hashCode遵循泊松分布的时候,因为hash冲突造成桶的的链表长度等于8的概率只有0.00000006。官方认为这个概率足够低,当需要红黑树介入的时候,你可以想象一下你的数据会是什么样的。

    什么时候从红黑树转为链表呢?

    当红黑树节点小于6的时候就会转回来,为什么是6呢,首先不能是8,因为如果是8的话,你会面临着频繁的链表与红黑树的切换,就让我想起了那句台词,我进来了,我出来了,我又进来了,我又出来了。。。。而选择6不选择7是因为,官方经过大量的验证,发现,当红黑树节点小于6的时候,它的优势就不那么明显了,不足以抵消维护红黑树的开销,之前听过一个大哥这么说的,经过工业严谨的实验证明,6在绝大多数的情况下表现良好。

    所以我们可以看出,作者在链表转为红黑树这里考虑的非常多,就是要让两种结构达到一个均衡点,过于草率的进行结构转换的话,其实非常的影响效率。

    从源码入手解析HashMap工作原理

    接下来我会从源码开始一步一步引申出对HashMap的一些疑问。
    我们先看一下HashMap中比较重要的一些属性,我的注释会解释相关含义

    HashMap中的重要属性介绍,以及一些疑问

    //默认的初始容量,1向左移动4位10000=16
    static final int DEFAULT_INITIAL_CAPACITY = 1 > 16);
    }
    

    看三元表达式的后半部分就可以了。(h = key.hashCode()) ^ (h >>> 16)。用key的hashCode去异或hashcode向右移16位。接着提出几点疑问

    为什么要选择异或运算,而不是与运算和或运算?

    与运算的方式是同为1则为1,否则为0。或运算是有1则为1,否则为0。异或是不同为1,相同为0。这样一对比其实就能发现与运算的结构更向0靠拢,或运算的结果更向1靠拢,而异或运算更加平均。公平起见,选异或。

    为什么要让hashcode异或hashcode右移16位?

    首先我们要知道的是hashcode是int类型,所以占4个字节32位,hash方法可以认为是对key本身的hashcode进行二次加工,这其实和HashMap计算key的位置的方式有关系的,确定位置在putVal的方法中,为了不搞乱,我单独把它拿出来了,如下,看一下它计算位置的方式i = (n - 1) & hash,n就是hash表的长度,用长度-1然后去&hash,看着挺难懂的,其实它就等于hash%n。当然这个前提是n得是2的幂次方。因为基于&的方式去计算,要快于十进制%的计算方式很多。所以这也解释了为什么容量要设置成2的幂次倍,就是采用取模的方式取址,还要提升计算速度!

    再回来说为什么要右移16位。举个例子:你的hashcode是1111110001然后&1111,等于=0001,然后下一个hashcode和上一个只是发生了高位的变化,比如1100110001然后&1111,结果其实还是0001,那就会导致计算出来的地址都一样,类似这种情况那大家不都在一个桶里了吗,当长度较低的时候,只有hashcode的低16位参与运算了,所以没有选择用hash直接计算地址,向右移动16位相当于让高位下来了,然后再去异或hashcode,相当于高低位结合了,也就提升了hash值的散列程度。

    为什么负载因子要设置成0.75?为什么不设置成1呢?

    设置成1的话就代表着,只有table装满了的时候才会去扩容,这时候所有键的hash都需要重新计算,这比较损耗性能,同时,这也会导致冲突的hash比较多。所以既不能频繁的扩容,也不能太晚的扩容,所以0.75是一个很均衡的值,而且0.75也就是四分之三,用table的长度去乘这个负载因子得出来的数就是扩容的阈值,而0.75刚好使得这个阈值是一个整数,因为上面我们提到的,容量是2的幂次倍。

    那么说完为什么容量要设置成2的幂次倍了,我们再说一下它是怎么保证的

    其实就是和构造方法相关了,在这里我就直接写了,对后面看构造函数的源码也是有帮助的,它的构造方法中有个非常关键的方法就是tableSizeFor,这个方法就是重新计算容量的,即便你重新传了初始容量,也要计算得出真实容量,我们看一下源码的实现

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    

    整个过程就是为了找到传入容量最近的大于它的一个2次幂的值,下面是我根据上面的算法写的几个例子

    image.png
    从例子中就可以很清楚的看出来为什么要传入的容量-1去计算。

    接下来,我接着走源码,看看构造方法是怎么样的逻辑

    HashMap的构造方法的工作流程解析

    它的构造方法有四个,我这里只解析其中一个,如下

    //参数位Map的构造函数,看过这个的解析,那么,其他三个一看就明白了
    public HashMap(Map

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论