黑马程序员技术交流社区
标题: [黑马程序员杭州]HashMap设计原理 [打印本页]
作者: 小江哥 时间: 2017-11-15 10:32
标题: [黑马程序员杭州]HashMap设计原理
本帖最后由 小江哥 于 2017-11-19 16:45 编辑
HashMap是我们平时用的非常多的集合之一, 那么大家有没有去了解过它的运行原理呢? 这篇文章主要从内部结构, 运行原理, 常用的put方法等来介绍下HashMap
1.HashMap数据结构
在JDK1.8之前, HashMap采用的散列表的形式来进行存储数据, 散列表又叫做哈希表, 其实就是数组+链表的一种数据结构
优点: 具备数组的查找迅速的特点, 又具有链表增删快的特点
缺点: 消耗的内存相对来说比较大, 拿空间换取时间
而JDK1.8时, 用的就不仅仅是链表结构, 内部会进行判断, 当链表的长度大于8时,会转换成红黑树的结构
2.初始容量大小----initialCapacity
当我们去创建一个HashMap的时候, 它是有一个初始容量为16的大小, 这个容量其实就是那个数组的长度, 这点应该比较好理解,创建数组的时候是不是要指定一个长度? 我们通常将数组每个下标所对应的空间称之为桶.
并且我们如果调用HashMap的单参数构造, 就能够给默认大小赋值,
但是这个大小必须是2的N次方,最大是2的30次方
但是这样引发了两个问题:
2.1 第一个问题: 如果我们传入的值不是2的N次方怎么办?
牛气哄哄的Java设计人员已经写好了一个算法, 绝对保证了我们传入的值, 最终会被变为一个大于该值且最小的2的N次方数, 这个方法叫tableSizeFor()方法
该方法会在HashMap有参构造中被调用
也许有的同学会感觉苦恼, 不会位运算, 这该如何是好? 不用担心, 有个最简单的方法, 就是将该方法的源码一个复制, 再一个粘贴到我们一个普通的main方法中, 进行一些简单的测试来观察结果即可, 这里举个简单例子传入7, 有兴趣的私下可以尝试其它数值
经过tableSizeFor()方法的运算, 如果我们传入的数字是7,那么最终会计算为一个大于7且最小的2的N次方, 也就是8, 经过该算法, 那么就绝对能获得2的N次方的数了,
那么紧接着第二个问题就来了.
2.2 第二个问题:为什么一定要是2的N次方?
要解决这个问题, 先要考虑什么情况下HashMap的效率能达到最高?
(1) 只让往哈希表中的数组中存, 不往链表结构中存, 但是这种方式显然是很不合理. 这种方式的存储和数组结构无异, 并且数组的缺点就是插入和删除效率慢
(2) 再一种方式就是, 让所有的数据Entry均匀的分布在哈希表中, 不会出现仅仅只往某一两个下标所对应的链表中添加数据, 造成某几个链表过长的情况, 这种方式相对的效率就会达到最优, 这也是HashMap中所实现的方式
那么怎么才能让HashMap存入的值更均匀呢?
其实是一个很简单的取模运算,HashMap中, 将每一个Entry的key的哈希值,与HashMap的容量长度进行一次取模运算, 这么一个简单的算法,就能将每一个数据Entry插入的更加均匀, 这个方法的名字叫indexFor(), 下面是源码
看到源码后会不会心里会不会感觉一个很大的我cao? 取模运算呢? 为什么又是位运算?
牛气哄哄的Java设计人员所写的代码, 肯定不会满足于仅仅实现某个功能而是考虑怎么才能让效率更高, 开销更少, 在时间和空间上追求一种最优解, 这个方法的实现其实是一个数学规律
“如果一个值x是2的N次方, 那么另一个值y对x的模运算结果等价于y和(x - 1)的&(按位与)运算!”,
其实就是 y % x == y & (x - 1)
而且，如果这个数不是2的N次方，那么进行h & (length - 1)的时候，有些值永远取不到, 也就意味着Entry永远不会添加到数组的某些下标中，这样就造成了Entry分布的不均匀，效率就会降低
而切身为开发人员我们应该知道, 位运算的比普通的数学运算效率要高! 这也就是为什么HashMap的容量一定要是2的N次方的原因
3.加载因子与扩容----loadFactor And ReSize
3.1 loadFactor
加载因子(loadFactor)有一个默认值0.75, 在构造方法中被赋值， 0.75是Java设计人员考虑空间和时间上的一个最优数值
这个加载因子的主要作用就是判断HashMap什么情况下扩容(Resize)—— 当HashMap中的Entry个数大于容量 * 加载因子时就会进行扩容，将数组的长度变为原来的2倍， 这个扩容条件由成员变量threshold来记录
3.2 Resize
当HashMap存储的Entry个数size > threshold(Resize阈值) = capicity * loadFactor, 但是大家都知道数组是不可变的，所以HashMap中的处理方式是创建了一个新的数组
例如：
HashMap中数组的默认大小为16， 加载因子为0.75， 扩容条件为 16 * 0.75 = 12, 也就是HashMap中的Entry超过12个，就会创建一个新的数组， 这个数的大小为16 * 2 = 32， 然后每个Entry所在位置要进行重新计算
下面是部分源码分析：
Jdk1.7中部分源码：
Jdk1.8中部分源码：
判断是否要Resize和重新计算新的容量及边界值
创建一个新的Node数组
将旧的节点Entry赋值到新的数组中，并重新计算Entry在新数组中的位置
4.put()方法
这里主要简述下HashMap中的put()方法
最终调用的是putval()方法
下面通过画图来描述过程图
当要往Map中存值时(当前集合中的数据小于容量8)， 会将Entry中的key取hash值， 然后计算要插入的下标(并不是按顺序插入， 具体在2.2中有讲解)， 此处假设计算结果为1，那么就在下标为1的位置插入数值
当某个下标运算结果后，这个位置已经有值，此时的情况有一个术语叫碰撞， 因为它是一种数组+链表的结构，所以就该链表结构发挥作用，就再往之前的某个下标的Entry前面增加信息(头插入)。
为何会将新的数据放在最前面？ 这时源于HashMap的设计人员认为，最后插入的数据的被使用概率会比较高！
当key的hashCode完全一样时，会覆盖调原来的节点的value，这也就是HashMap中key唯一的特点
当HashMap中的size(Entry的个数) 大于threshold(容量大小8 * 加载因子0.75 = 6)时，就会发生Resize的情况，源码中有这几行代码
关于resize()方法前面已经有了简述，这里不再赘述
以上就是HashMap内部的实现原理, 如有错误的地方,欢迎指正!!!
作者: fanbuer 时间: 2017-11-15 10:52
不错，很细致，面试中基础高频知识点，赞一个
作者: wxz_hm 时间: 2017-11-15 10:54
厉害。很细致 加油
作者: gy_yt 时间: 2017-11-15 10:54
看了，对原理有了进一步的理解
作者: 咸鱼666 时间: 2017-11-15 10:55
整理很好，收藏备用
作者: 孙晓威 时间: 2017-11-15 11:01
文笔幽默，技术扎实！
作者: nhm 时间: 2017-11-15 11:01
66666666666666
作者: 猫先森 时间: 2017-11-15 11:19
此时只能怒刷一波666了
作者: 从此学好 时间: 2017-11-15 11:20
高频面试问题啊，学习了
作者: 黑马6666 时间: 2017-11-15 13:40
厉害了学习了很有用
作者: Rocket_冷风 时间: 2017-11-15 16:49
很好的笔记，收藏以备用
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |
