A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 小江哥 于 2017-11-19 16:45 编辑

  HashMap是我们平时用的非常多的集合之一, 那么大家有没有去了解过它的运行原理呢? 这篇文章主要从内部结构, 运行原理, 常用的put方法等来介绍下HashMap
1.HashMap数据结构
JDK1.8之前, HashMap采用的散列表的形式来进行存储数据, 散列表又叫做哈希表, 其实就是数组+链表的一种数据结构
优点: 具备数组的查找迅速的特点, 又具有链表增删快的特点
缺点: 消耗的内存相对来说比较大, 拿空间换取时间
JDK1.8时, 用的就不仅仅是链表结构, 内部会进行判断, 当链表的长度大于8时,会转换成红黑树的结构

2.初始容量大小----initialCapacity
当我们去创建一个HashMap的时候, 它是有一个初始容量为16的大小, 这个容量其实就是那个数组的长度, 这点应该比较好理解,创建数组的时候是不是要指定一个长度? 我们通常将数组每个下标所对应的空间称之为.
并且我们如果调用HashMap的单参数构造, 就能够给默认大小赋值,
但是这个大小必须是2N次方,最大是230次方
  
但是这样引发了两个问题:

2.1 第一个问题: 如果我们传入的值不是2N次方怎么办?
牛气哄哄的Java设计人员已经写好了一个算法, 绝对保证了我们传入的值, 最终会被变为一个大于该值且最小的2N次方数, 这个方法叫tableSizeFor()方法
该方法会在HashMap有参构造中被调用

也许有的同学会感觉苦恼, 不会位运算, 这该如何是好?  不用担心, 有个最简单的方法, 就是将该方法的源码一个复制, 再一个粘贴到我们一个普通的main方法中, 进行一些简单的测试来观察结果即可, 这里举个简单例子传入7, 有兴趣的私下可以尝试其它数值
  
经过tableSizeFor()方法的运算, 如果我们传入的数字是7,那么最终会计算为一个大于7且最小的2N次方, 也就是8, 经过该算法, 那么就绝对能获得2N次方的数了,
那么紧接着第二个问题就来了.

2.2 第二个问题:为什么一定要是2N次方?
要解决这个问题, 先要考虑什么情况下HashMap的效率能达到最高?
(1) 只让往哈希表中的数组中存, 不往链表结构中存, 但是这种方式显然是很不合理. 这种方式的存储和数组结构无异, 并且数组的缺点就是插入和删除效率慢
(2) 再一种方式就是, 让所有的数据Entry均匀的分布在哈希表中, 不会出现仅仅只往某一两个下标所对应的链表中添加数据, 造成某几个链表过长的情况, 这种方式相对的效率就会达到最优, 这也是HashMap中所实现的方式
那么怎么才能让HashMap存入的值更均匀呢?
其实是一个很简单的取模运算,HashMap中, 将每一个Entry的key的哈希值,与HashMap的容量长度进行一次取模运算, 这么一个简单的算法,就能将每一个数据Entry插入的更加均匀, 这个方法的名字叫indexFor(), 下面是源码
看到源码后会不会心里会不会感觉一个很大的我cao? 取模运算呢? 为什么又是位运算?
牛气哄哄的Java设计人员所写的代码, 肯定不会满足于仅仅实现某个功能而是考虑怎么才能让效率更高, 开销更少, 在时间和空间上追求一种最优解, 这个方法的实现其实是一个数学规律
如果一个值x2N次方,  那么另一个值yx的模运算结果等价于y(x - 1)&(按位与)运算!”,
其实就是 y % x == y & (x - 1)
而且,如果这个数不是2N次方,那么进行h & (length - 1)的时候,有些值永远取不到, 也就意味着Entry永远不会添加到数组的某些下标中,这样就造成了Entry分布的不均匀,效率就会降低
而切身为开发人员我们应该知道, 位运算的比普通的数学运算效率要高! 这也就是为什么HashMap的容量一定要是2N次方的原因

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中的keyhash值, 然后计算要插入的下标(并不是按顺序插入, 具体在2.2中有讲解), 此处假设计算结果为1,那么就在下标为1的位置插入数值
当某个下标运算结果后,这个位置已经有值,此时的情况有一个术语叫碰撞, 因为它是一种数组+链表的结构,所以就该链表结构发挥作用,就再往之前的某个下标的Entry前面增加信息(头插入)
为何会将新的数据放在最前面? 这时源于HashMap的设计人员认为,最后插入的数据的被使用概率会比较高!
keyhashCode完全一样时,会覆盖调原来的节点的value,这也就是HashMapkey唯一的特点
HashMap中的size(Entry的个数) 大于threshold(容量大小8 * 加载因子0.75 = 6)时,就会发生Resize的情况,源码中有这几行代码
关于resize()方法前面已经有了简述,这里不再赘述
以上就是HashMap内部的实现原理, 如有错误的地方,欢迎指正!!!



10 个回复

倒序浏览
fanbuer 来自手机 中级黑马 2017-11-15 10:52:37
沙发
不错,很细致,面试中基础高频知识点,赞一个
回复 使用道具 举报
回复 使用道具 举报
gy_yt 来自手机 中级黑马 2017-11-15 10:54:46
板凳
看了,对原理有了进一步的理解
回复 使用道具 举报
咸鱼666 来自手机 中级黑马 2017-11-15 10:55:15
报纸
整理很好,收藏备用
回复 使用道具 举报
孙晓威 来自手机 黑马粉丝团 2017-11-15 11:01:32
地板
文笔幽默,技术扎实!
回复 使用道具 举报
nhm 来自手机 中级黑马 2017-11-15 11:01:46
7#
66666666666666
回复 使用道具 举报
猫先森 来自手机 中级黑马 2017-11-15 11:19:17
8#
此时只能怒刷一波666了
回复 使用道具 举报
从此学好 来自手机 中级黑马 2017-11-15 11:20:30
9#
高频面试问题啊,学习了
回复 使用道具 举报
厉害了学习了很有用
回复 使用道具 举报
Rocket_冷风 来自手机 中级黑马 2017-11-15 16:49:07
11#
很好的笔记,收藏以备用
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马