- 1. HashMap的家族定位
-
2. HashMap的数据结构
- 2.1 Hash表的基本概念
- 2.2 Hash冲突
- 2.3 HashMap数据结构
-
3. HashMap的重要变量
- 3.1 常量
- 3.2 变量
- 3.3 辨析size、capacity、threshold
-
4. HashMap重要方法和源码解析
- 4.1 构造方法
- 4.2 resize方法
- 4.3 hash方法
- 4.4 put方法
- 参考文献
1. HashMap的家族定位
接口java.util.Map
有四个常用的实现类,如图是它们之间的类继承关系。
下面我将一一介绍其性能特点。
-
HashMap
:- 最常用的Map实现类,通过使用Hash表结构,提高查找速度;
- 使用键值对作为存储节点,只允许一个key值为
null
,允许多个value值为null
; - 线程不安全,对于线程安全有要求的程序,可以考虑使用:sychronizedMap或者ConcurrentHashMap;
-
HashTable
- 同样使用Hash表结构,提高查找效率;
- 线程安全,但是安全层级低于ConcurrentHashMap,不常用。
-
LinkedHashMap
- 继承自HashMap,使用Hash表结构,提高查找效率;
- 链表插入维持插入顺序。
-
TreeMap
- sortedMap接口的实现类,可使用特定的排序规则对键值对进行排序;
对四种常见的实现类的性能比较如下图所示:
2. HashMap的数据结构
2.1 Hash表的基本概念
Hash表是数据结构和算法
课程中学习到的一种重要的数据结构。主要设计思想是:
- 使用一个长度为
n
的数组存储相关数据。 - 使用
hash函数
实现内容和数组下标的对应,也就是hash函数
的函数值为0~n
之间。-
hash函数
相同的输入参数一定会产生相同函数值,不同内容尽量做到函数值分散。
-
- 在hash函数值对应的下标写入该内容。
- 下次查找某元素的时候,先根据
hash函数
生成下标,然后再随机访问数组,这样查找效率大大提高了。
类似于一个叫贾斯汀·费尔兰德·亨利皮特潘
(复杂内容)的人,在酒店前台
(hash函数)入住酒店的房间编号是1004
(hash函数值/数组下标)。需要找他的人,只需要去酒店前台查询他住在1004
房间,直接去1004
房间找人就可以了,不需要一个一个房间去找。
2.2 Hash冲突
在上面的流程说明中,我们可以发现Hash表的实现关键就在于Hash函数,一个好的hash函数应该保证不同的输入内容尽量分散其函数值。
当存入的数据过多,hash函数性能较差的时候,可能会出现hash冲突
:
-
A
和B
是两个不同的存储内容,但是经过hash函数计算,得到的hash函数值相同,因此两个内容存储在数组的同一位置。 - 例如:
贾斯汀·费尔兰德·亨利皮特潘
和特朗普·懂王·建国同志
两个人在酒店前台分配到的房间号都是1004
,但是房间只有一张床,这时两个人就会发生冲突。
解决冲突主要有两种思路:
- 开放定址法:发生冲突的时候,后到来的元素放弃已被占用的位置,寻找新的插入位置。(再找)
- 链地址法:发生冲突的时候,后到来的元素在原有位置的基础上,使用链表的方式存储。(排队)
- HashMap使用的就是
链地址法
。
- HashMap使用的就是
2.3 HashMap数据结构
-
节点Node
Node是HashMap的一个基本存储单元,从源码中可见Node实现了Map.Entry接口,存放的是键值对。在JDK1.8中的源码中,Node的定义如下所示:static class Node implements Map.Entry { final int hash; //用来定位数组索引位置 final K key; V value; Node next; //链表的下一个node Node(int hash, K key, V value, Node next) { ... } public final K getKey(){ ... } public final V getValue() { ... } public final String toString() { ... } public final int hashCode() { ... } public final V setValue(V newValue) { ... } public final boolean equals(Object o) { ... } }
-
JDK1.7的HashMap数据结构
数组+链表-
如图所示
-
使用链地址方式解决hash冲突。
-
-
JDK1.8的HashMap数据结构
数组+链表+红黑树-
如图所示
-
对红黑树的学习可参考此博客。
-
链表和红黑树的转换根据链表长度阈值判断,阈值为8,即链表长度大于8时,由链表转换为红黑树,小于6时,由红黑树转换为链表。
-
红黑树的引入目的:在链表长度较长的情况下,优化查找效率。
-
3. HashMap的重要变量
3.1 常量
-
DEFAULT_INITIAL_CAPACITY
- 默认的数组初始容量,值为
2^4=16
。 - 如果没有指定初始数组的容量的话,就会使用这个默认值。
- 默认的数组初始容量,值为
-
MAXIMUM_CAPACITY
- 最大的数组容量,值为
2^30
。 - 在扩容的时候,如果扩容后的容量大于这个值,就会使用这个值作为新的容量。
- 之后如果数据再增加,不再进行扩容,而是直接链表存储或者转为红黑树。
- 最大的数组容量,值为
-
DEFAULT_LOAD_FACTOR
- 默认负载因子,值为
0.75
。 - 在HashMap中,扩容的临界值计算公式为:
临界值(threshold) = 负载因子(loadFactor) * 容量(capacity)
- 负载因子可以设置为任意值,但是需要注意的是:
- 负载因子变大,hash冲突的概率就会变大,查找效率就会降低。【牺牲时间】
- 负载因子过小,会导致数组空间利用率低,浪费内存空间。【牺牲空间】
- 默认负载因子,值为
-
TREEIFY_THRESHOLD
- 链表转化为红黑树的阈值,值为
8
。 - 当一个数组节点所带着的链表长度大于8时,链表会转化为红黑树。
- 链表转化为红黑树的阈值,值为
-
UNTREEIFY_THRESHOLD
- 红黑树转化为链表的阈值,值为
6
。 - 当一个数组节点的红黑树节点小于6时,红黑树会转化为链表。
- 红黑树转化为链表的阈值,值为
-
MIN_TREEIFY_CAPACITY
- 转换为红黑树的最小容量,值为
64
。 - 这个变量的意思是,在HashMap不断增加新元素的过程中,如果此时数组中的元素个数小于64,那么就选择扩容。当数组元素个数大于64的时候才会考虑树化。
- 转换为红黑树的最小容量,值为
3.2 变量
-
size
- HashMap中存储的键值对个数。
-
modCount
- 对HashMap进行修改的次数记录,每次增删则加一。
-
threshold
- 扩容的临界值,计算公式为:
threshold = loadFactor * capacity
。其中capacity为数组总长度,通常为了提高阈值,会使用扩容增加capacity,而对于负载因子loadFactor,一般不会修改。
- 扩容的临界值,计算公式为:
-
loadFactor
- 负载因子,用户可自行设置其值,否则等于默认值
0.75
。
- 负载因子,用户可自行设置其值,否则等于默认值
3.3 辨析size、capacity、threshold
size:实际存储的键值对个数
capacity:数组的总长度
threshold:扩容的临界值
treeify_threshold/untreeify_threahold:链表和红黑树相互转化的阈值
4. HashMap重要方法和源码解析
4.1 构造方法
- HashMap()
无参构造,使用默认的初始容量2^4
和负载因子0.75
,构造一个空的HashMap。
// 构造一个空的 HashMap,初始容量为 16,负载因子为默认值 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- HashMap(int initialCapacity)
指定初始容量,使用默认的负载因子0.75
。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性实现容量和负载因子的赋值
}
- HashMap(int initialCapacity, float loadFactor)
指定初始容量和负载因子,构造一个空的HashMap。
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始容量为负数,抛出非负异常
if (initialCapacity MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子不能小于 0,并且必须是数字,否则抛异常
if (loadFactor
- HashMap(Map extends K, ? extends V> m)
构造一个非空的HashMap,将m中的键值对存入HashMap中,默认的负载因子 0.75,使用默认的初始容量2^4
。
public HashMap(Map extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将 Map 中的 key-value 赋值到新的 Map 中去
putMapEntries(m, false);
}
4.2 resize方法
当HashMap中数组的使用量超过阈值的时候,就需要进行扩容。JDK1.8的源码如下所示:
final Node[] resize() {
Node[] oldTab = table;// 当前 table
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 当前table的大小
int oldThr = threshold;// 当前 table 的 threshold
int newCap, newThr = 0;// 新的 table 的大小和阀值暂时初始化为 0
// 下面就是开始计算新的 table 的大小和阀值
// 第一种情况:当前 table 的大小大于 0,则意味着当前的 table 肯定是有数据的
if (oldCap > 0) {//
if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大于最大容量,不再扩容,直接返回原始table
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)//翻倍之后不超过最大容量,原始容量小于最大容量,且大于默认容量,那么容量翻倍,阈值也对应翻倍
newThr = oldThr 0)
newCap = oldThr;//此时的阀值就是数组的大小,所以直接把当前的阀值当做新 table 的数组大小即可。threshold = tableSizeFor(t);
// 第三种情况,这种情况就代表当前的 table 是调用的空参构造来初始化的,所有的数据都是默认值。
else {//初始阈值为0,表示使用默认值,新的 table 也只要使用默认值即可
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阀值是 0,那么就简单计算一遍就行了
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap [] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历当前 table,处理每个下标处的 bucket,将其处理到新的 table 中去
for (int j = 0; j e;
if ((e = oldTab[j]) != null) {
// 释放当前 table 数组的对象引用(for循环后,当前 table 数组不再引用任何对象)
oldTab[j] = null;
// a、只有一个 Node,则直接 rehash 赋值即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// b、当前的 bucket 是红黑树,直接进行红黑树的 rehash 即可
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// c、当前的 bucket 是链表
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
// 遍历链表中的每个 Node,分别判断是否需要进行 rehash 操作
// (e.hash & oldCap) == 0 算法是精髓,充分运用了上文提到的 table 大小为 2 的幂次方这一优势,下文会细讲
do {
next = e.next;
// 根据 e.hash & oldCap 算法来判断节点位置是否需要变更
// 索引不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原 bucket 位置的尾指针不为空(即还有 node )
if (loTail != null) {
// 链表末尾必须置为 null
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 链表末尾必须置为 null
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
为什么要*2扩容?或者说,为什么HashMap的数组大小为2的幂
在理论学习中,Hash表的大小最好是素数,因为素数能够有效降低hash碰撞。但是HashMap并没有采用这种做法。
在上面的源码中,我们可以看到,HashMap在扩容的时候,数组的大小都是原来的两倍,这是因为在计算索引的时候,我们使用的是size-1
的n个全1二进制串和hash值进行与运算,这样可以保证计算出来的索引值一定在0~size-1
之间,不会越界。如图所示:
当HashMap值为2的幂的时候,size-1
为全1二进制字符串,且扩容之后,原本有冲突的两个元素会找到各自的新索引位置。如图所示:
在代码中,这个步骤被进一步简化。如代码片段所示:
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
因为hash值是一个整数,所以hash & oldCap
的结果要么是0,要么是oldCap。所以,hashMap的扩容,实际上是将原来的数组分成两部分,一部分的索引不变,一部分的索引变为原索引+oldCap。这样就保证了原来的两个元素,扩容之后,一定不会在同一个索引位置上。具体解释如图所示:
4.3 hash方法
也就是之前在理论部分所说的hash函数部分,将关键字key的值转换为唯一hash值,JDK1.8源码如下:
static final int hash(Object key) {
int h;
// 高 16 位与低 16 位进行异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode()
函数通常和equals()
函数进行比较,hashCode()
函数是根据对象的内存地址生成一个特定的数,因此,hashCode值相同的对象不一定相同,hashCode值不同的对象一定不相同。
一般判断两个对象是否相等,先使用hashCode()
函数判断内存地址,如果hashCode()
函数值相同,再使用equals()
函数判断内存中的内容,如果hashCode()
函数值不同,就不需要再使用equals()
函数判断了。
这里h先设置成key值的hashCode,然后右移16位,再和原来的h进行异或运算,这样做的目的是为了减少hash碰撞,提高查找效率。
之后如何从hash值映射到数组下标,在JDK1.7的源码如下所示:
static int indexFor(int h, int length) {
return h & (length-1);
}
这里也解释了为什么HashMap的数组大小为2的幂,因为这样可以保证length-1
为全1的二进制串,与操作之后计算出来的索引值一定在0~size-1
之间,不会越界,具体操作如图所示:
4.4 put方法
put方法主要是在HashMap中存储键值对,JDK1.8源码如下所示:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//重点在于putVal方法
}
// 参数 onlyIfAbsent,针对已经存在的value,值为true表示不修改;否则表示会替换原本的value值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
// ① 如果当前 table 为空则进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 计算得到索引 i,算法在上文有提到,然后查看索引处是否有数据
// ② 如果没有数据,则新建一个新的 Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 索引处有数据
else {
Node e; K k;
// ③ 索引处的第一个 Node 的 key 和参数 key 是一致的,所以直接修改 value 值即可(修改的动作放在下面)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 索引处的 bucket 是红黑树,按照红黑树的逻辑进行插入或修改
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// ⑤ 索引处的 bucket 是链表
else {
// 遍历链表上面的所有 Node
for (int binCount = 0; ; ++binCount) {
// 索引处的 Node 为尾链
if ((e = p.next) == null) {
// 直接新建一个 Node 插在尾链处
p.next = newNode(hash, key, value, null);
// 判断是否需要转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 链表转换为红黑树,此方法在上文中也有介绍
treeifyBin(tab, hash);
break;
}
// 当前 Node 的 key 值和参数 key 是一致的,即直接修改 value 值即可(修改的动作放在下面)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到了相同 key 的 Node,所以进行修改 vlaue 值即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 修改 value 值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 修改操作,直接 return 结束掉代码逻辑
return oldValue;
}
}
// 记录结构发生变化的次数
++modCount;
// ⑥ 判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 新增的 Node,返回 null
return null;
}
源代码所抽象出来的具体的put流程可如下图所示:
在JDK1.7中,链表插入使用头插法,而在JDK1.8中,链表插入使用尾插法,
- JDK1.7 使用头插法的原因:考虑到热点数据,后面插入的元素更有可能被最近使用,因此使用头插法。
- 头插法会使链表上 Node 的顺序调转,而尾插法则不会,另外,头插法也会造成环形链死循环等问题,
参考文献
- 知乎专栏-HashMap原理详解,看不懂算我输(附面试题)
- 掘金社区-详解 HashMap 数据结构
- 美团技术团队-Java 8系列之重新认识HashMap
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net