1. 定义
1 | public class HashMap<K,V> extends AbstractMap<K,V> |
- 实现了Cloneable接口
即覆盖了函数clone(),能被克隆 - 实现java.io.Serializable接口
支持序列化,能通过序列化去传输
2. 介绍
结构实现
HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,当链表长度达到8,会转化成红黑树,以提升它的查询、插入效率
设计思路
- Map<K,V>
Map<K,V>是一种以键值对存储数据的容器,而HashMap则是借助了键值Key的hashcode值来组织存储,使得可以非常快速和高效地地根据键值key进行数据的存取 - Entry<Key,Value>
对于键值对<Key,Value>,HashMap内部会将其封装成一个对应的Entry<Key,Value>对象,即Entry<Key,Value>对象是键值对<Key,Value>的组织形式 - 存
对于每个对象而言,JVM都会为其生成一个hashcode值。HashMap在存储键值对Entry<Key,Value>的时候,会根据Key的hashcode值,以某种映射关系,决定应当将这对键值对Entry<Key,Value>存储在HashMap中的什么位置上 - 取
当通过Key值取数据的时候,然后根据Key值的hashcode,以及内部映射条件,直接定位到Key对应的Value值存放在什么位置,可以非常高效地将Value值取出。
- 线程不安全的
- 允许key为null,value为null
- 遍历时无序
其底层数据结构是数组称之为哈希桶,每个桶里面放的是链表,链表中的每个节点,就是哈希表中的每个元素。
因其底层哈希桶的数据结构是数组,所以也会涉及到扩容的问题。
当HashMap的容量达到threshold域值时,就会触发扩容。扩容前后,哈希桶的长度一定会是2的次方。
这样在根据key的hash值寻找对应的哈希桶时,可以用位运算替代取余操作,更加高效。
而key的hash值,并不仅仅只是key对象的hashCode()方法的返回值,还会经过扰动函数的扰动,以使hash值更加均衡。
因为hashCode()是int类型,取值范围是40多亿,只要哈希函数映射的比较均匀松散,碰撞几率是很小的。
但就算原本的hashCode()取得很好,每个key的hashCode()不同,但是由于HashMap的哈希桶的长度远比hash取值范围小,默认是16,所以当对hash值以桶的长度取余,以找到存放该key的桶的下标时,由于取余是通过与操作完成的,会忽略hash值的高位。因此只有hashCode()的低位参加运算,发生不同的hash值,但是得到的index相同的情况的几率会大大增加,这种情况称之为hash碰撞。 即,碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征,并存放在低位,因此在与运算时,相当于高低位一起参与了运算,以减少hash碰撞的概率。(在JDK8之前,扰动函数会扰动四次,JDK8简化了这个操作)
扩容操作时,会new一个新的Node数组作为哈希桶,然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中,相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大,可想而知,在哈希表的容量越大时,性能消耗越明显。
扩容时,如果发生过哈希碰撞,节点数小于8个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置。
因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即low位, 或者扩容后的下标,即high位。 high位= low位+原哈希桶容量
如果追加节点后,链表数量》=8,则转化为红黑树
由迭代器的实现可以看出,遍历HashMap时,顺序是按照哈希桶从低到高,链表从前往后,依次遍历的。属于无序集合。
3 .属性
DEFAULT_INITIAL_CAPACITY
初始容量,必须是2的倍数,默认是16 (1 << 4)
1 | static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 |
MAXIMUM_CAPACITY
最大所能容纳的key-value 个数,最大值是 1073 741 824(1 << 30)
1 | static final int MAXIMUM_CAPACITY = 1 << 30; |
DEFAULT_LOAD_FACTOR
默认的加载因子
1 | static final float DEFAULT_LOAD_FACTOR = 0.75f; |
TREEIFY_THRESHOLD
树化链表节点的阈值,当某个链表的长度大于或者等于这个长度,则扩大数组容量,或者数化链表
1 | static final int TREEIFY_THRESHOLD = 8; |
Node<K,V>
Node<K,V> 类是HashMap中的静态内部类,实现Map.Entry<K,V>接口。 定义了key键、value值、next节点,也就是说元素之间构成了单向链表
1 | static class Node<K,V> implements Map.Entry<K,V> { |
Node<K,V>[] table
存储数据的Node数组,长度是2的幂
The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two.
1 | transient Node<K,V>[] table; |
至此,HashMap存储的数据结构也就很清晰了:维护了一个数组,每个数组又维护了一个单向链表。之所以这么设计,考虑到遇到哈希冲突的时候,同index的value值就用单向链表来维护。
size
map中保存的键值对的数量
1 | transient int size; |
threshold
The next size value at which to resize (capacity * load factor).
- 容量*装载因子
- threshold是HashMap判断size是否需要扩容的阈值:如果key-value的数量等于该值,则调用resize方法,扩大容量(2倍),同时修改threshold的值
1 | int threshold; |
loadFactor
装载因子
1 | final float loadFactor; |
4. 构造函数
无参构造函数
HashMap()
Constructs an empty {@code HashMap} with the default initial capacity
1 | public HashMap() { |
DEFAULT_LOAD_FACTOR
1 | static final float DEFAULT_LOAD_FACTOR = 0.75f; |
指定初始化容量的构造函数
HashMap(int initialCapacity)
Constructs an empty {@code HashMap} with the specified initial capacity and the default load factor (0.75).
并不是指定的初始容量是多少,初始化之后的HashMap的容量就是多大,tableSizeFor()方法会把初始化的容量变成是2的次方数
1 | public HashMap(int initialCapacity) { |
指定初始化容量 以及 加载因子
HashMap(int initialCapacity, float loadFactor)
1 | public HashMap(int initialCapacity, float loadFactor) { |
tableSizeFor(int cap)
- 根据期望容量cap,返回2的n次方形式的 哈希桶的实际容量 length
- 返回值一般会大于等于cap
1 | static final int tableSizeFor(int cap) { |
- 给定的cap减1
1 | int n = cap - 1 |
如果cap本来就是2的幂次方,经过后续的未操作的,cap将会变成2 * cap,是不符合我们预期的
- n无符号右移1位
1 | n |= n >>> 1 |
- 即n二进制最高位的1右移一位,导致的结果是n二进制的高2位值为1
- 目前n的高1~2位均为1
- n继续无符号右移2位
1 | n |= n >>> 2 |
- 导致n二进制表示高3~4位经过运算值均为1
- 目前n的高1~4位均为1
- n继续无符号右移4位
1 | n |= n >>> 4 |
- 导致n二进制表示高5~8位经过运算值均为1;
- 目前n的高1~8位均为1。
- n继续无符号右移8位。
1 | n |= n >>> 8 |
- n | (n >>> 8),导致n二进制表示高9~16位经过运算值均为1
- 目前n的高1~16位均为1
- n继续无符号右移16位。
1 | n |= n >>> 16 |
- 导致n二进制表示高17~32位经过运算值均为1
- 目前n的高1~32位均为1
可以看出,无论给定cap(cap < MAXIMUM_CAPACITY )的值是多少,经过以上运算,其值的二进制所有位都会是1。再将其加1,这时候这个值一定是2的幂次方。当然如果经过运算值大于MAXIMUM_CAPACITY,直接选用MAXIMUM_CAPACITY。
这里可以举个栗子,假设给定的cap的值为20。
int n = cap - 1; —> n = 19(二进制表示:0001 0011)
n |= n >>> 1;
1 | n -> 0001 0011 |
n |= n >>> 2;
1 | n -> 0001 1011 |
…
1 | n + 1 -> 0010 0000 (32) |
最终,tableSizeFor(20)的结果为32(2^5)。
至此tableSizeFor保证cap为2的幂次方
为什么cap要保持为2的幂次方?
- index怎么算
HashMap中存储数据table的index是由key的Hash值决定的 - Hash怎么算
在JDK1.8中,HashMap中key的Hash值由Hash(key)方法(后面会详细分析)计算得来
在HashMap存储数据的时候,我们期望数据能够均匀分布,以避免哈希冲突。自然而然我们就会想到去用%取余的操作来实现我们这一构想 - 优化
取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作
1 | index = e.hash & (newCap - 1) |
采用二进制位操作&,相对于%,能够提高运算效率
参数是map 的构造函数
将另一个map m 里的所有元素加入表中
HashMap(Map<? extends K, ? extends V> m)
1 | public HashMap(Map<? extends K, ? extends V> m) { |
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
- 将另一个Map的所有元素加入表中,参数evict初始化时为false,其他情况为true
- 用get() put()
- 判断表是否为空
1.1 为空表,计算阈值
1.2 非空表,判断是否需要扩容 - 遍历 m 依次将元素加入当前表中
1 | final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { |
resize()
时机
当前的HashMap的大小大于阀值时,HashMap会对此HashMap的容量进行扩充,即对内部的Entry[] table 数组进行扩充
要求
HashMap对容量(Entry[] table数组长度) 有两点要求:
- 容量的大小应当是 2的N次幂
- 当容量大小超过阀值时,容量扩充为当前的一倍
步骤
容量扩充分为以下几个步骤:
- 确定新的阈值和容量
1.1 旧容量>0
没有超过最大容量,则新表容量、门限为旧表2倍
1.2 旧容量=0,旧门限>0
旧表门限值赋值给新表容量,新表阈值=容量 * 负载因子
1.3 旧容量=0,旧门限=0
则新的容量和门限为默认的容量(16)和门限值(12) - 将当前哈希桶中的所有节点转移到新的哈希桶中
旧的链表不空,且链表中有元素
2.1 链表中就一个元素(没有发生哈希碰撞)
直接将这个元素放置在新的哈希桶里
2.2 发生过哈希碰撞 ,且节点数超过8个
转化成了红黑树
2.3 发生过哈希碰撞,节点数小于8个- 根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置
- 因为扩容是容量翻倍,原链表上的每个节点,现在可能存放在原来的下标low位; 或者扩容后的下标high位
- high位= low位+原哈希桶容量
1 | final Node<K,V>[] resize() { |
5. 增加—put
添加一个元素
put(K key, V value)
Associates the specified value with the specified key in this map.If the map previously contained a mapping for the key, the old value is replaced.
1 | public V put(K key, V value) { |
hash(K,V) 方法
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower.
- HashMap中table的index是由Key的哈希值决定的
- 而上面我们提到index的运算规则是e.hash & (newCap - 1)。由于newCap是2的幂次方,那么newCap - 1的高位应该全部为0。如果e.hash值只用自身的hashcode的话,那么index只会和e.hash低位做&操作。这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会增加哈希冲突的风险
- HashMap并没有直接使用key的hashcode(),在计算key的哈希值的时候,用其自身hashcode值与其低16位做异或操作
1 | static final int hash(Object key) { |
。
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
@param
hash: hash for key
key :the key
value: the value to put
onlyIfAbsent: if true, don’t change existing value
evict: if false, the table is in creation mode.
return:previous value, or null if none
流程图和步骤参考自美团点评
对步骤语序逻辑有所调整
流程图
步骤
- 判断键值对数组table[i]是否为空或为null
如果当前哈希表是空的,代表是初始化,则执行resize()进行扩容 - 根据键值key计算hash值得到插入的数组索引i
- 如果table[i]==null,直接新建节点添加(index 是利用 哈希值 & 哈希桶的长度-1,替代模运算)转向⑥
- 如果table[i]不为空,转向③
- 发生了哈希冲突
判断table[i]的首个元素是否和key一样,相同指的是hashCode以及equals- 如果相同直接覆盖value
- 否则转向④
- 判断table[i] 是否为treeNode,即table[i] 是否是红黑树
- 如果是红黑树,则直接在树中插入键值对
- 否则转向⑤
- 遍历table[i],判断链表长度是否大于8
- 大于8的话把链表转换为红黑树,在红黑树中执行插入操作
- 否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可
- 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容
源码
在构造函数中最多也只是设置了initialCapacity、loadFactor的值,并没有初始化table,table的初始化工作是在put方法中进行的
1 | inal V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
6. 删除—remove
remove(key)
执行逻辑:
1)根据key得到key的hash值
2)根据key 和hash值定位需要remove的Node
3) 将Node从对应的链表移除,然后再将Node 前后的节点对接起来
4)返回被移除 的Node
5)key-value的数量减一,修改次数加一
##
小总结:
- 运算尽量都用位运算代替,更高效
- 对于扩容导致需要新建数组存放更多元素时,除了要将老数组中的元素迁移过来,也记得将老数组中的引用置null,以便GC
- 取下标 是用 哈希值 与运算 (桶的长度-1) i = (n - 1) & hash。 由于桶的长度是2的n次方,这么做其实是等于 一个模运算。但是效率更高
- 扩容时,如果发生过哈希碰撞,节点数小于8个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置
- 因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即low位, 或者扩容后的下标,即high位。 high位= low位+原哈希桶容量
- 利用哈希值 与运算 旧的容量 ,if ((e.hash & oldCap) == 0),可以得到哈希值去模后,是大于等于oldCap还是小于oldCap,等于0代表小于oldCap,应该存放在低位,否则存放在高位。这里又是一个利用位运算 代替常规运算的高效点
- 如果追加节点后,链表数量》=8,则转化为红黑树
- 插入节点操作时,有一些空实现的函数,用作LinkedHashMap重写使用。
参考文章
Java集合干货系列-(三)HashMap源码解析
Java官方文档
美团技术团队Java 8系列之重新认识HashMap
源码分析之 HashMap
[Java基础要义] HashMap的设计原理和实现分析