java集合框架Map之HashMap底层原理解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) , 当HashMap中的table数组(桶)的长度 >= 阈值的时候就会自动触发扩容机制

哈希表(hash table)

哈希表也称为散列表 , 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。也就是说关键字为K的元素存储到数组的位置K , 这也就意味着给定一个关键字K , 仅通过查找数组的第K个位置就可以找到该元素 , 这也称为直接寻址 ,这个映射函数叫做散列函数,存放记录的数组叫做散列表。


使用散列的查找算法分为两步 , 第一步是用散列函数将被查找的键转换为数组的一个索引 , 在理想情况下 , 每个键经过散列函数计算之后都会转换为不同的索引值 , 并且对应一个表中的地址(数组中的一个位置 , 也是内存中的一个地址) , 如下图所示 :


fda444e7151e602a8f5d0beb0769678d_984f312d3ecda1fbccbb0ab9bc653c71.png


当然 , 这是理想的情况 , 不理想的情况就是多个key经过散列函数计算之后转换为的键是相同的 , 这个时候就会涉及到一个问题 : hash碰撞(如下图所示) , 所以散列算法的第二步也就是一个处理碰撞冲突的过程 , 解决hash冲突的算法有: 拉线法和线性探测法


a90abfe4fa28e14cf9e9f86cf580fcd9_0fbc0092ac13abac898237549f30f46b.png


线性探测法

线性探测法也叫开放定址法 , 把数组比作几套房子 , 当你正要付定金的时候 , 房子刚好被别人买了 , 这个时候怎么办呢?那就只能再找其他房子了 , 线性探测法也是类似的道理 , 如果当前散列地址有值了 , 那么就去寻找下一个空的散列地址 , 只要散列表足够大 , 那么就会有空的散列地址 , 如上图所示 , 在存放键为d的元素的时候发生了hash碰撞 , 那么就可以使用线性探测法 , 一直去判断 , 直到下标为3的时候发现可以存入元素 , 那么就将键为d的元素存到了下标为3的位置


拉线法

拉线法也叫拉链法 , 在hashMap中为了解决hash碰撞就用了拉链法 , 也就是JDK1.7的HashMap实现使用了数组+链表 , 而JDK1.8的实现中为了更快的检索拉出来的这个"链表"中的内容增加了红黑树 , 大致原理就是如下图所示


597774ed6879f230ba20f253fb383b0b_81d9197407c7d40332154d7651c941e9.png


键为d , f的散列值出现了hash碰撞 , 这个时候就是用链表来存储重复的元素 , 如果需要根据键a找对应的值 , 那么时间复杂度为O(1) , 直接就可以找到 , 但是如果有多个key的hash值计算之后都为2 , 那么数组下标为2的位置的链表就会比较长 , 我们知道 , 链表的遍历是比较慢的 , 所以为了解决遍历链表慢的问题 , JDK1.8进行了优化 , 引入了红黑树来解决查询慢的问题 , 在HashMap中 , 这个数组又可以称为桶


散列函数

在散列的查找算法中 , 面对的第一个问题就是散列函数的计算 , 及把键转换为散列值(数组的索引)的计算 , 也就是说如果现在有一个长度为M的数组 , 那么就需要一个函数来将任意键转换为该数组范围内([0 , M-1])整数的索引, 而这个散列函数通常有以下特点:


尽可能的避免hash碰撞


计算简单且快速


将键值(key value) 均匀的分布在散列表


除留余数法

哈希函数的实现有好多种 , 其中比较常用的一种就是除留余数法 , 及使用key的哈希值取模一个素数 , 公式表达为 : H(key)=key MOD p (p<=m) , 但是素数的选择是非常重要的 , 尽可能的选择奇数并且接近m(因为偶数发生hash冲突的概率很大 , 接近m是因为这样计算出来的索引值分布更加均匀) , HashMap使用的就是类似的方法 , 在HashMap初始化或者扩容时 , 元素索引的计算为 : hash & (newCap - 1) , 这样就满足了最佳素数的选择条件 , 只不过HashMap的作者为了提高运算效率 , 没有使用% , 而选择了位运算 , 但是选择位运算数组的长度必须是2的N次方


解释一下: 为什么数组的长度必须是2的N次方

9为key , 4为数组的长度


使用除留余数法在平时的取余中我们是这样运算的 : 9 / 4 = 2…1 ,商为2余数为1 , 所以索引为1 , 换成位运算就是 : 9对应的二进制为: 1001 , 4为2的2次方 , 所以如果一个数除以2的N次方 , 那么我们就是要得到最后这个数最后N位二进制的值


9 (1001) / 2的2次方 = 2…1 等于 (1001 后两位 = 0001 = 1)


因为size为二的幂次方,size-1的二进制一定为111···11这种全是1的数,这样进行与操作就能提取到后N位,所以位运算取余公式是 key MOD p = 9 / (4(2的2次方) -1) 替换为位运算 hash & (size - 1) = 1001 & 0011 = 0001 = 0001 = 1


9为key , 3为数组的长度


如果数组的长度不为2的N次方 , 带入公式 key MOD p = 9 / (3 - 1) 替换为位运算 hash & (size - 1) = 1001 & 0010= 0000 = 0 , 由此可见无法达到预期的效果


java规范

而对于键的类型它可以有几种 , 比如整数 , 浮点数 , 字符串 , 所以散列函数和键的类型有关 , 严格一点来说就是 : 对于每种类型的键 , 都需要一个与之对应的散列函数 , 如果键是一个整数 , 那么可以直接使用这个数 , 如果是一个字符串 , 比如名称 , 那么就需要把这个字符串转换为一个数 , 如果这个键有多个部分 , 比如邮件地址 , 那么就需要把这些部分结合起来 , 对于常见类型的的键 , 可以使用java默认的实现


所以hash函数由于每种数据类型都需要相应的散列函数 , 所以java就令所有数据类型都继承了一个能够返回32比特整数的hashCode()方法


整数类型hashCode()实现

public static int hashCode(int value) {
    return value;
}

字符串hashCode()实现

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

浮点型hashCode()实现

public static int floatToIntBits(float value) {
    int result = floatToRawIntBits(value);
    // Check for NaN based on values of bit fields, maximum
    // exponent and nonzero significand.
    if ( ((result & FloatConsts.EXP_BIT_MASK) ==
          FloatConsts.EXP_BIT_MASK) &&
         (result & FloatConsts.SIGNIF_BIT_MASK) != 0)
        result = 0x7fc00000;
    return result;
}

但是我们需要的是一个[0,M-1]的索引 , 而不是32比特的整数 , 所以在java中是这样计算hash值的

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先把key的hashCode值赋值给h , 然后将h右移16位 , 然后进行^异或运算 , 由此可以引申两个问题


1.为什么要右移16位?

右移16位其实是为了减少hash碰撞 , int类型占4字节 , 也就是32位 , 无符号右移16位 , 高位补0 , 这个时候可以同时保留高16位和低16位的特征 , 或许举个例子就很好明白


如果现在有一个数的hash值为 11110001 数组默认长度为16 , 现在有两个值 : 241 193


241 % 15 换算为2进制 11110001 & 00001111 = 00000001


193 % 15 换算为2进制 11000001 & 00001111 = 00000001


这样这两个数据计算之后索引相同 , 因为HashMap使用的是拉链法 , 所以计算出索引容易一样 ,这就可能导致某个索引下的链表比较长 , 值的分布不均匀 , 但是右移16位 , 就可以使高位的数据也加入到取余计算 , 从而使值的分布更加均匀


2.为什么使用^运算 , 而不是用&或者是|

因为异或可以保证两个值的特性 , 位运算中与(&)运算的结果更加的偏向0 , 而|运算的结果更加偏向1


所以我们可以看出 右移是为了保持低16位与高16位的特征 , 而^运算可以使结果不会偏向0或者1 , 增加了散列程度 , 使数据分布的更加均匀

4.HashMap容量与扩容机制

4.1 HashMap默认扩容因子

/**


The load factor used when none specified in constructor.

/

static final float DEFAULT_LOAD_FACTOR = 0.75f;

扩容因子是用来计算扩容阈值用的

4.2 HashMap默认容量

/*

The default initial capacity - MUST be a power of two.

*/

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

3.HashMap的阈值

HashMap的阈值计算公式 : 阈值(threshold) = 扩容因子(loadFactor) * 容量(capacity)


如果扩容因子和容量都是默认的话 , 那么阈值就是 0.75f * 16 = 12

如果当HaspMap中table(也成为桶)的长度大于等于阈值时就会触发扩容机制


4.为什么HashMap的默认负载因子是0.75,而不是0.5或者是整数1呢?

阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制,它会保证容量(capacity)的值永远都是2的幂

为了保证负载因子x容量的结果是一个整数,这个值是0.75(4/3)比较合理,因为这个数和任何2的次幂乘积结果都是整数


理论上来讲,负载因子越大,导致哈希冲突的概率也就越大,负载因子越小,费的空间也就越大,这是一个无法避免的利弊关系,所以通过一个简单的数学推理,可以测算出这个数值在0.75左右是比较合理的


5.为什么容量的值永远都是2的幂

HashMap是根据key的hash值通过公式tab[i = (n - 1) & hash] 计算得出key在桶中的位置 , 这里n是HashMap的容量 , 因为永远都是2的幂 , 所以n-1通过二进制表示永远都末位连续1的形式表示 , 例如 00001111 , 00000011 , 当(n - 1)和hash做与运算的时候会保留末位的x位的1 , 这样做的好处在于 :

&位运算的效率比%取模运算的效率高(但是有一个前提 : n也就是HashMap的容量要保证是2的幂)

能保证索引值在容器范围内(n - 1) & hash 运算的值分布比较均匀 , 可以减少hash冲突

那么如果我们在构造参数指定容器的大小不为2的幂 ,是不是就打破了以上规则?

不是的 , HashMap的tableSizeFor方法做了处理,能保证n永远都是2次幂。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    //cap-1后,n的二进制最右一位肯定和cap的最右一位不同,即一个为0,一个为1,例如cap=17(00010001),n=cap-1=16(00010000)
    int n = cap - 1;
    //n = (00010000 | 00001000) = 00011000
    n |= n >>> 1;
    //n = (00011000 | 00000110) = 00011110
    n |= n >>> 2;
    //n = (00011110 | 00000001) = 00011111
    n |= n >>> 4;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 8;
    //n = (00011111 | 00000000) = 00011111
    n |= n >>> 16;
    //n = 00011111 = 31
    //n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次方
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

6.HashMap的扩容机制

写数据的时候会发生扩容 , 它内部有一个字段用来记录当前数据量的字段 , 如果数据量字段达到扩容的阈值的话 , 就会触发扩容机制


阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) , 当HashMap中的table数组(桶)的长度 >= 阈值的时候就会自动触发扩容机制


扩容规则是这样的 : 因为table数组的长度必须是2的幂 , 所以扩容其实也就是按照上一次的tableSize左移了1位 , 比如当前table数组的长度是16 , 扩容一次之后就是 16 << 1 = 32 , 也就是说扩容之后的长度是当前长度的两倍 , 但需要记住的是扩容使用的是左移一位(newTableSize = tableSize << 1) 得到的扩容后的容量 ,而不是当前容量 * 2


7.为什么HashMap扩容不直接*2

因为cpu不支持乘法运算 , 所有的乘法运算最终都是到了指令层面转换为假发实现的 , 这样效率很低 , 如果使用位运算的话对于cpu来说简洁又高效


8.HashMap的扩容过程

JDK1.7

先生成新的数组

遍历老数组上每个位置上的链表的每个元素

取每个元素的key , 基于新数组的长度 , 计算出每个元素在新数组中的下标

将元素添加到新数组中

所有元素转移完毕之后 , 将新数租赋值给HashMap对象的table属性


JDK1.8

先生成新数组

遍历老数组中每个位置上的链表或者红黑树

如果是链表 , 则直接将链表中的每个元素重新计算下标 , 并添加到新数组

如果是红黑树 , 则先遍历红黑树 , 计算出每个元素对应在新数组中的下标

统计每个下标的元素个数

如果个数超过了8个 , 那么就重新生成红黑树 , 并将根节点添加到新数组对应的位置

如果个数没有超过8个 , 那么则生成一个链表 , 并将链表的头节点添加到新数组对应的位置

所有元素转移完毕之后 , 将新数租赋值给HashMap对象的table属性


如果感觉博主写的还不错的话 可以来一个一键三连 , 并且同时可以顺便关注一下博主的公众号 : [猿人刘先生] , 下面我把链接贴出来 , 非常感谢大家的阅读与关注 , 希望我们可以不想学习 , 共同进步 !!!


java集合框架Map之HashMap底层原理解析

相关文章
|
2月前
|
存储 安全 Java
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
66 2
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
64 2
|
2月前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
41 3
|
2月前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
59 3
|
2月前
|
存储 缓存 安全
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
33 2
|
2月前
|
存储 安全 Java
Java Map新玩法:深入探讨HashMap和TreeMap的高级特性
【10月更文挑战第19天】Java Map新玩法:深入探讨HashMap和TreeMap的高级特性,包括初始容量与加载因子的优化、高效的遍历方法、线程安全性处理以及TreeMap的自然排序、自定义排序、范围查询等功能,助你提升代码性能与灵活性。
26 2
|
2月前
|
存储
让星星⭐月亮告诉你,HashMap的put方法源码解析及其中两种会触发扩容的场景(足够详尽,有问题欢迎指正~)
`HashMap`的`put`方法通过调用`putVal`实现,主要涉及两个场景下的扩容操作:1. 初始化时,链表数组的初始容量设为16,阈值设为12;2. 当存储的元素个数超过阈值时,链表数组的容量和阈值均翻倍。`putVal`方法处理键值对的插入,包括链表和红黑树的转换,确保高效的数据存取。
59 5
|
24天前
|
存储 Java 开发者
Java中的集合框架深入解析
【10月更文挑战第32天】本文旨在为读者揭开Java集合框架的神秘面纱,通过深入浅出的方式介绍其内部结构与运作机制。我们将从集合框架的设计哲学出发,探讨其如何影响我们的编程实践,并配以代码示例,展示如何在真实场景中应用这些知识。无论你是Java新手还是资深开发者,这篇文章都将为你提供新的视角和实用技巧。
23 0
|
2月前
|
分布式计算 Java 应用服务中间件
NettyIO框架的深度技术解析与实战
【10月更文挑战第13天】Netty是一个异步事件驱动的网络应用程序框架,由JBOSS提供,现已成为Github上的独立项目。
46 0
|
16天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
45 2

推荐镜像

更多