HashMap源码分析

HashMap简介

基于哈希表实现,每一个元素key-value存储,内部实现是数据上挂载单链表,容量不足时(超过了阈值,阈值是通过负载因子计算的),会自动扩展(以2倍方式扩容)。
1. 允许key value值为null

  1. 线程不安全

  2. 实现Serializable,支持序列化

  3. 实现了Cloneable,支持被克隆

  4. key-value方式存储

  5. 自动扩容,根据负载因子计算,为当前容量的2倍

HashMap源码解读

存储数据结构

如下图:(图是copy自网络,无法找到源头,只能先借用啦(^▽^))
《HashMap源码分析》

HashMap类结构

《HashMap源码分析》

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

继承抽象类AbstractMap,实现了序列化Serializable接口,cloneable接口,Map接口
HashMap 重要的常量属性
  • 默认桶的大小

  • 默认桶的最大值

  • 负载因子

  • 链表转成红黑树的阈值

  • 红黑树转成链表的阈值

  • 由链表转换成红黑树的容量的最小阈值

  • 扩容阈值

构造方法(一共有四种构造方法)
  • 默认构造(负载因子为默认大小)

  • 指定大小的,指定负载因子的构造方法

  • 指定大小的构造方法(负载因子为默认)

  • 包含Map的构造方法

单链表的实现

每一个节点是一个Entry对象,每一个node节点都存储有key value,节点的hash值,以及下一个节点的node,实现Map.Entry接口。需要注意到node对象重写了equals方法,当出现hash冲突的时候会通过equals比较是否相同

计算hashMap容量

计算hashMap容量的大小,也就是桶的大小,说到这,先补充一下知识点

初始化时,会首先判断初始容量是否小于0,如果小于0,会抛出异常。接着,判断初始容量是否大于最大的容量(即2^31),如果大于,将初始容量设置为最大初始容量。紧接着,判断加载因子:如果小于等于0,或者不是一个数字,都会抛出异常。等这些校验完成之后,会将HashMap的加载因子和扩容的阈值设置上。这里需要注意一下,threshold(阈值)=capacity*loadFactor。

这个方法,是计算桶的大小,根据给定的cap,进行无符号右移,将移动的值与之前的值取非,如下计算逻辑:
例如输入30,求该桶的大小?

求hash值和桶的索引值

接下来重点分析一下求hash值和桶的索引值,这俩个是HashMap最核心的地方,他可以保证哈希表中的元素均匀地散列。

根据key计算hash值,只计算hash值的几位,使用位操作是计算效率很高。目前不去深究为什么这么设计,我们只要知道,这样设计的目的是为了让hash值分布的更加均匀即可。

求桶的索引值,是key的hash &(tab.length – 1)

在上面的tableSizeFor方法,计算出的桶的大小是2的整数次幂,为什么桶的大小一定是2的整数次幂呢?
首先,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率;
其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。

get 方法

getNode的2个参数,key的hash值和key,首先判断table是否为null,并且table的length大于0,根据key的hash & table表的长度 – 1,计算到表的索引值,判断在此索引值对应的桶是否存在,如果存在在判断key是否相等或者key的值是否相等。如果找到则返回对应的node,否则继续判断next节点是否存在,并且节点的属性是否为TreeNode,如果为红黑树,则通过树快速查找并返回,否则循环链表,查找key对应的节点。

put方法

put 方法有2个参数,key和value, putVal有四个参数
hash:表示key的hash值
key:待存储的key值
value:待存储的value值,从这个方法可以知道,HashMap底层存储的是key-value的键值对,不只是存储了value
onlyIfAbsent:这个参数表示,是否需要替换相同的value值,如果为true,表示不替换已经存在的value
evict:如果为false,表示数组是新增模式
我们看到put时所传入的参数put(hash(key), key, value, false, true),可以得到相应的含义.

  • 如果table桶为null,或者大小为0,如果为空,则调用resize()方法,对HashMap进行扩容,这次扩容的结果就是HashMap的初始化一个长度为16的数组。获取到数组的长度n

  • hash方法,当key=null时,也是有hash值的,是0,所以,HashMap的key是可以为null的,对比HashTable源码我们可以知道,HashTable的key直接进行了hashCode,如果key为null时,会抛出异常,所以HashTable的key不可以是null

  • 接着,根据长度-1和hash值进行按位与运算,算出hash值对应于数组中的位置,如果没有值,则创建一个new node,存储到桶的该索引处

  • 如果hash冲突,首先判断hash值是否相等,如果不相等,则判断key的值equals是否相等,如果相等,则标记已找到e

  • 如果节点类型为TreeNode,则使用红黑树创建,并标记已找到e

  • 若3,4未符合,则循环单链表,找到则标记为e

  • 如果标记e不为null,则表示找到冲突的节点,使用afterNodeAccess更新节点

  • modCount 增加1
  • 如果桶的++size > threshold,则自动扩展桶的大小,重新分配元素分配

  • 使用afterNodeInsertion 增加node
下一篇文章将重点分析resize()

参考资料

https://blog.csdn.net/ns_code/article/details/36034955
https://www.jianshu.com/p/7dcff1fd05ad

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注