详解 HashMap 源码解析(上)
jdk 版本:1.8
数据结构:
HashMap
的底层主要基于数组+链表/红黑树实现,数组优点就是查询块,HashMap
通过计算hash码
获取到数组的下标来查询数据。同样也可以通过hash码
得到数组下标,存放数据。
哈希表为了解决冲突,HashMap
采用了链表法,添加的数据存放在链表中,如果发送冲突,将数据放入链表尾部。
上图左侧部分是一个哈希表,也称为哈希数组(hash table):
table
数组的引用类型是Node节点
,数组中的每个元素都是单链表的头结点,链表主要为了解决上面说的 hash 冲突,Node 节点包含:
hash
hash 值key
键value
值next
next 指针
Node节点
结构如下:
主要属性
size 记录元素个数
threshold 扩容的临界值,等于元素容量*装载因子
TREEIFY_THRESHOLD 8 链表个数增加到
8
会转成红黑树UNTREEIFY_THRESHOLD 6 链表个数减少到
6
会退化成链表loadFactor 装载因子,默认为
0.75
loadFactor 装载因子等于扩容阈值/数组长度,表示元素被填满的程序,越高表示空间利用率越高,但是
hash冲突
的概率增加,链表越长,查询的效率降低。越低hash冲突
减少了,数据查询效率更高。但是示空间利用率越低,很多空间没用又继续扩容。为了均衡查询时间和使用空间,系统默认装载因子为0.75
。
获取哈希数组下标
添加、删除和查找方法,都需要先获取哈希数组的下标位置,首先通过hash算法
算出 hash 值,然后再进行长度取模,就可以获取到元素的数组下标了。
首先是调用hash
方法,计算出hash值
:
先获取 hashCode 值,然后进行高位运算,高位运算后的数据,再进行取模运算的速度更快。
算出hash
值之后,再进行取模运算:
上面的n
是长度,计算的结果就是数组的下标了。
构造方法
HashMap()
设置默认装载因子0.75
,默认容量16
。
HashMap(int initialCapacity)
HashMap(int initialCapacity)
指定初始容量,调用HashMap(int initialCapacity, float loadFactor)
其中loadFactor
为默认的0.75
。
首先做容量的校验,小于零报错,大于最大容量赋值最大值容量。然后做装载因子的校验,小于零或者是非数字就报错。
tableSizeFor
使用右移和或运算,保证容量是 2 的幂次方,传入 2 的幂次方,返回传入的数据。传入不是 2 的幂次方数据,返回大于传入数据并接近 2 的幂次方数。比如:
传入
10
返回16
。传入
21
返回32
。
HashMap(Map<? extends K, ? extends V> m)
将集合m
的数据添加到HashMap
集合中,先设置默认装载因子,然后调用putMapEntries
添加集合元素到HashMap
中,putMapEntries
是遍历数组,添加数据。
总结
本文基于jdk1.8
解析 HashMap 源码,主要介绍了:
HashMap
是基于数组+链表/红黑树结构实现。采用链表法
解决 hash 冲突。Node 节点记录了数据的
key
、hash
、value
以及next
指针。HashMap
主要属性:size 元素个数
table[] 哈希数组
threshold 扩容的阈值
loadFactor 装载因子
TREEIFY_THRESHOLD 8,链表个数为 8 转成红黑树。
UNTREEIFY_THRESHOLD 6 ,链表个数为 6 红黑树转为链表。
添加、删除以及查找元素,首先要先获取数组下标,
HashMap
先调用 hasCode 方法,hashCode()的高 16 位异或低 16 位,大大的增加了运算速度。然后再对数组长度进行取模运算。本质就是取 key 的 hashCode 值、高位运算、取模运算。HashMap
几个构造方法:HashMap()
设置默认装载因子0.75
和默认容量16
。HashMap(int initialCapacity)
设置初始容量,默认装载因子0.75
,容量是一定要是 2 的幂次方,如果不是 2 的幂次方,增加到接近 2 的幂次方数。HashMap(Map<? extends K, ? extends V> m)
主要是遍历添加的集合,添加数据。
参考
感觉不错的话,就点个赞吧!
评论