简介
HashMap在1.8之后通过数组(table)属性使用单向链表 + 红黑树的结构组合提高查找效率,于是我大致的画了下图:
后来写着写着发现我还是太年轻了,有什么比亲手实践更值得让人信服呢?
类图分析(只标注主要属性方法)
Map<K,V>
:键值映射的基础接口,提供常用的键值映射操作方法的抽象Map.Entry<K,V>
:键值对条目(单个键值)抽象接口AbstractMap<K,V>
: 简单实现了Map
接口的部分方法HashMap<K,V>
: 基于Map
接口的哈希实现HashMap.Node<K,V>
:HashMap
键值对条目链表结构的实现类HashMap.TreeNode<K,V>
:HashMap
键值对条目红黑树结构的实现类LinkedHashMap<K,V>
:基于Map
接口的哈希表和链表结构实现,与HashMap
的主要区别在于键值对都是有序的LinkedHashMap.Entry<K,V>
:LinkedHashMap
键值条目链表结构的实现类
属性解析
DEFAULT_INITIAL_CAPACITY
:默认16,默认初始容量,必须为2的幂值MAXIMUM_CAPACITY
:默认1<<30(即2^29),最大容量值,如果有参构造函数容量值比该值高,则使用该值作为容量值DEFAULT_LOAD_FACTOR
:默认0.75f,构造函数中未指定时使用的负载因子TREEIFY_THRESHOLD
:默认8,容器树化阈值,达到阈值(8)后容器将使用红黑树结果存储数据UNTREEIFY_THRESHOLD
:默认6,非树化阈值,应小于TREEIFY_THRESHOLD
。MIN_TREEIFY_CAPACITY
:默认64,表中节点链表结构被树化的最小表容量值,实际会根据容器大小判断是只进行扩容还是进行树化。loadFactor
:哈希表的负载因子threshold
:下一次调整大小的容量阈值(capacity * load factor)modCount
:对该HashMap进行结构修改的次数。结构修改是指更改HashMap中的映射数目或以其他方式修改其内部结构的修改(如重新哈希)。size
:包含的键-值映射数table
:该表(节点Node数组)在首次使用时初始化,并根据需要调整大小,分配后的长度始终是2的幂。entrySet
:用于获取key-value映射集合Set<Map.Entry<K,V>>
,在首次调用entrySet()
方法时被初始化
文章使用的术语掺杂了一些个人根据源码与文档的理解,需了解注意的如下:
- 表(table数组) = 容器
- table.length = 容量 != 映射数目
- table中的节点Node元素 = 桶bin
- table中的键值对节点Node以外的元素都以null填充
方法解析,窥遍HashMap
HashMap
的三个构造函数
- 无参构造函数
1
2
3
4
5
6
7/**
* 使用默认的初始容量(16)和默认的加载因子(0.75)构造一个空的HashMap。
* 注:该方法没有初始化阈值threshold
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
} - 带初始容量的构造函数
1
2
3
4public HashMap(int initialCapacity) {
// 初始化容量initialCapacity、负载因子loadFactor=DEFAULT_LOAD_FACTOR(0.75)、阈值threshold
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} - 带初始容量与f负载因子的构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
* 以特定的容量与负载系数构建一个空的HashMap
*
* @param initialCapacity 初始容量
* @param loadFactor 负载因子
* @throws IllegalArgumentException initialCapacity为负数、负载因子为负数或非数字时抛错
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY; // MAXIMUM_CAPACITY = 1 << 30
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 该方法主要用于设置阈值threshold,返回大于或等于参数容量cap的的2次幂,如cap=9、11、12、15、16时都会返回16,cap=5、6、7、8时返回8
* @param cap 容量参数
* @return 返回大于或等于参数容量cap的的2次幂
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
put(K, V)添加键值
由HashMap
的三个构造函数可以看出构造HashMap
时主要初始化了负载因子loadFactor、table扩容阈值threshold,若是无参构造函数则只初始化阈值,所以一般table的初始化都是在put第一个键值对时初始化的。
1 | /** |
综上,HashMap添加键值对的流程如下:
- 判断table是否为空,空则调用resize()初始化table数组,一般发生在初次添加键值对
- 参数key哈希值hash与数组table长度相与获取到索引值i,根据table[i]节点是否为空执行不同的操作
- 2.1 table[i]节点p为空:在table[i]创建新节点,跳到步骤3
- 2.2 table[i]节点p不为空,根据以下不同的情况执行相应的操作
- 2.2.1 节点p的key、hash与参数的key、hash匹配:即最终操作只需替换原有key的值,将最终节点e设为p,跳到2.2.4
- 2.2.2 节点p是一个红黑树节点(TreeNode)类型:根据参数创建新的红黑树节点TreeNode,根据红黑树规则把新节点插入到p节点所在的红黑树上
- 2.2.3 其它情况(即链表结构,头节点key与参数key不同):创建新节点并链接到链表末尾,若链表节点数大于8个,则调用treeifyBin()根据table.length长度进行不同的操作
- table.length >= 64,将所有的Node链表节点转为TreeNode红黑树节点
- table.length < 64,调用resize()将table.length左移一位(原lengh乘2),即使链表节点数>8依旧保持链表结构
- 2.2.4 设置e节点key新值,返回key旧值
- 节点新增成功后的HashMap相关操作属性更新
实力(例)验证
为了简单直接的显示
HashMap
结构,这个博主直接的把HashMap
实例里的核心属性都print出来了。
table容量<64时,key hashCode相同的节点数>8依旧会保持链表结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35public static void stringKey() throws NoSuchFieldException, IllegalAccessException {
HashMap<String, Integer> map = new HashMap<>(32);
// 9个hashKey相同的字符串集合,map容量<64时会在添加第9个"20kf"进行扩容而不会树化,即32则左移一位为64,集合删除"20kf"则不会扩容仍为32
Set<String> sameHashKeys = Sets.newHashSet("30lG", "31MG", "31Lf", "30kf", "1nlG", "2PLf", "1oLf", "2OlG", "2Okf");
Field thresholdField = HashMap.class.getDeclaredField("threshold");
Field tableField = HashMap.class.getDeclaredField("table");
thresholdField.setAccessible(true);
tableField.setAccessible(true);
Random random = new Random();
IntStream.range(0, 10).forEach(i -> map.put(String.valueOf(i), i));
sameHashKeys.forEach(key -> map.put(key, random.nextInt(25)));
Set<Map.Entry<String, Integer>> sets = map.entrySet();
Map.Entry<String, Integer>[] table = (Map.Entry<String, Integer>[]) tableField.get(map);
long notNullCount = Arrays.stream(table)
.filter(Objects::nonNull)
.count();
Set<Class> nodeClasses = Arrays.stream(table)
.filter(Objects::nonNull)
.map(Object::getClass)
.collect(Collectors.toSet());
// 输出格式化
String tableString = JSONObject.toJSONString(table)
.replaceAll(",null", "")
.replaceAll("null,", "")
.replaceAll("\\{|}|\"", "")
.replaceAll(":", "=")
.replaceAll(",", ", ");
System.out.println("map.size():" + map.size() + ", table.length: " + table.length
+ ", table node count: " + notNullCount + ", entrySet size: " + sets.size());
System.err.println("node classes: " + nodeClasses);
map.remove("30lG");
System.out.println("table: " + JSONObject.toJSONString(table));
System.out.println("evict null table: " + tableString);
System.out.println("entrySet: " + sets);
}控制台输出:
1
2
3
4
5map.size():19, table.length: 64, table node count: 11, entrySet size: 19
node classes: [class java.util.HashMap$Node]
table: [null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,{"31MG":22},{"0":0},{"1":1},{"2":2},{"3":3},{"4":4},{"5":5},{"6":6},{"7":7},{"8":8},{"9":9},null,null,null,null,null,null]
evict null table: [30lG=13, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]
entrySet: [31MG=22, 31Lf=1, 30kf=14, 1nlG=7, 2PLf=13, 1oLf=13, 2OlG=21, 2Okf=16, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]table容量>=64时,key hashCode相同的节点数>8后HashMap会树化
1
HashMap<String, Integer> map = new HashMap<>(33); // 有参容量自动调整为64
控制台输出:
1
2
3
4
5map.size():19, table.length: 64, table node count: 11, entrySet size: 19
node classes: [class java.util.HashMap$TreeNode, class java.util.HashMap$Node]
table: [null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,{"30kf":19},{"0":0},{"1":1},{"2":2},{"3":3},{"4":4},{"5":5},{"6":6},{"7":7},{"8":8},{"9":9},null,null,null,null,null,null]
evict null table: [30kf=19, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]
entrySet: [30kf=19, 31MG=8, 31Lf=16, 1nlG=3, 2PLf=19, 1oLf=20, 2OlG=12, 2Okf=15, 0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9]可以看到”30kf”是该红黑树上的root。
那么问题来了,添加映射会调整结构(即更改节点Node类型),那么删除呢?这个博主有点懒,所以不讲源码给答案:HashMap
删除节点的过程十分简单,获取节点类型->根据节点类型进行相应的删除操作,若节点是树节点结构,则判断该树的节点数是否较少(源码文档标注一般为2~6),较少则把树节点TreeNode转换为普通节点Node,如上例中删除最后4个hashCode相同的节点后(即只剩下5个Node)再打印会发现没有TreeNode了。
调用链:hashmap.remove() -> hashmap.removeNode() -> treeNode.removeTreeNode() -> treeNode.untreeify(map)
reszie()调整table容量
1 | final Node<K,V>[] resize() { |
综上,HashMap.put(K,V)
调用resize()调整大小主要分以下几种情况:
- 扩容:
oldCap = table.length > 0
,resize()结果:table.length = oldCap * 2;
threshold = table.length * loadFactor
- 有参函数初始化:
oldCap = table.length = 0 & oldThr = threshold > 0
,resize()结果:table.length = threshold;
,此处threshold值为跟有参构造函数运算后的threshold值,运算后的threshold值是比构造函数参数threshold大的最小一个2的幂值threshold = table.length * loadFactor
- 无参函数初始化:
oldCap = table.length = 0 & oldThr = threshold = 0
table.length = 16;
threshold = 12
容量调整后会再根据table中的节点结构进行相应的操作:
- 单节点Node无链接:重新哈希
- 树节点TreeNode:将树箱中的节点拆分为较高和较低的树箱,如果拆分后的树箱容量<6,则取消树化;拆分后较低的树箱放在新table[旧table原索引],较高的树箱迁移到新table[原索引+原table.length],详细可看
TreeNode.split()
源码 - 链表结构Node:拆分规则迁移与TreeNode类似,低位链表head node放在新table[原索引],高位链表迁移到新table[原索引+原table.length]
table.length=newCap
和threshold
调整后会创建新的节点数组进行键值对迁移,所以一般建议初始化时配置好容量避免扩容时的迁移损失。
clear()清空映射
clear()只是简单的把table数组的所有元素置为null
1 | public void clear() { |
疑问record & 总结
entrySet()
方法返回的明明是一个new EntrySet()
,为什么却打印出了完整的HashMap
映射?EntrySet
继承了AbstractSet
类并实现了iterator()
方法,AbstractSet
类toString()
方法会调用iterator()
方法获取迭代器,再通过Iterator.next()
进行元素的字符串拼接。EntrySet。iterator()
返回一个实现了Iterator
接口的类EntryIterator
,通过EntryIterator.next()
可以遍历获取HasMap
中的所有Node
,所以即使HashMap
的entrySet属性没有初始化但通过entrySet()
方法依旧可以获取HashMap
的完整映射。hashCode相同的key映射数超过8个并不一定就会转为红黑树结构
HashMap
当同hashCode的节点Node超过8个且table数组容量>=64才会转为红黑树结构,否则容量<64时只会进行扩容保存链表结构,Result.png:resize()进行容量调整并不一定会使每个节点进行重新哈希(rehash),重新哈希只会出现在无链接的单节点上
如有笔误,还请指出