深入 Java 中的 HashMap (一)

文章目录
  1. 1. 简介 HashMap
  2. 2. 深入 HashMap
  3. 3. 参考文献

任何一个傻瓜都能写出计算机能理解的程序,而优秀的程序员却能写出别人能读懂的程序。

引言来自 ThoughtWorks 的首席科学家、《重构》等经典书籍的作者 Martin Fowler。

个人觉得,要写出别人能读懂的程序,不仅要知其然,也要知其所以然。好,这期就来谈谈我们 Android 乃至 Java 开发中使用再频繁不过的的 HashMap (本篇分析基于 JDK 1.8),做到会用,且知道为什么这么用,及其内部的工作机理。

简介 HashMap

Java 为数据结构中的映射,定义了一个接口 java.util.Map,其主要有 4 个常用的实现类,分为 HashMap、Hashtable、LinkedHashMap 和 TreeMap。我们着重来看 HashMap。

HashMap 是我们开发中使用频率最高的、用于映射(键值对)处理的数据类型。

1.其根据键的 hashCode 值存储数据,大多数情况下,可以直接定位到它的值,故具有很快的访问速度,但遍历顺序却是不确定的

2.其最多只允许一条记录的键为 null,但允许多条记录的值为 null;

3.其为非线程安全的,任一时刻,可以有多个线程同时访问 HashMap,或许会导致数据的不一致。不过,若要满足线程安全,可以调用 Collections 的 synchronizedMap 方法,使得 HashMap 获取线程安全的能力,此外,还可以使用 ConcurrentHashMap。

借此,顺带扩展提一下 Hashtable。

Hashtable 是遗留类,很多映射的常用功能与 HashMap 类似。其与 HashMap 不同的是它继承自 Dictionary 类,且是线程安全的,任一时刻,只有一个线程能访问 Hashtable,并发性不如 ConcurrentHashMap,是由于 ConcurrentHashMap 有着分段锁的机制。

注意的是,建议少使用或不使用 Hashtable,不要求线程安全的场合,可以替换成使用 HashMap;要求线程安全的场合,可以替换成使用 ConcurrentHashMap。此外,映射中的 key 须为不可变对象,即对象在创建后,它的哈希值不变,以免 Map 对象定位不到准确的映射位置。

深入 HashMap

Demo 地址:HashMapSample

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class HashMapSample {

public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("Java", 1);
map.put("C++", 2);
map.put("Python", 3);
map.put("JavaScript", 4);
map.put("C", 5);
map.put("PHP", 6);
map.put("Golang", 7);
map.put("Ruby", 8);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}

}

输出结果为:

1
2
3
4
5
6
7
8
Golang: 7
Java: 1
C++: 2
C: 5
JavaScript: 4
PHP: 6
Ruby: 8
Python: 3

有了直观的感受后,进一步,先来看 HashMap 的存储结构。

存储结构

HashMap 是数组 + 链表 + 红黑树( JDK 1.8 新增红黑树) 实现的,如下图所示:

顺带提一下以上几个概念:

数组:存储空间是连续的,占用内存严重,空间复杂度很大。但是,其二分查找时间复杂度,为 O(nlogn);其特点为寻址容易,插入和删除困难

链表:存储空间是离散的,占用内存较宽松,空间复杂度很小。但是,其二分查询的时间复杂度很大;其特点为寻址困难,插入和删除容易

红黑树:一种自平衡二叉查找树,典型的用途是实现关联数组。其是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的;它可以在 O(nlogn) 时间内做查找、插入和删除,这里的 n 是树中元素的数目。

接下来,看源码,注意到其中一个重要的字段,就是 Node[] table,即哈希桶数组,其是一个 JDK 1.8 中新增 Node 的数组,源码如下:

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
35
36
static class Node<K, V> implements Map.Entry<K, V> {

final int hash; // 定位数组索引位置
final K key;
V value;
HashMap.Node<K, V> next; // 链表的下一个 node

Node(int hash, K key, V value, HashMap.Node<K, V> next) {
// ...
}

public final K getKey() {
return key;
}

public final V getValue() {
return value;
}

public final String toString() {
return key + "=" + value;
}

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
// ...
}

public final boolean equals(Object o) {
// ...
}

}

Node 是 HashMap 的一个内部类,实现了 Map.Entry 接口,也就是一个映射(键值对)。上图中,每个橙色圆点就是一个 Node 对象。

紧接着,来看 HashMap 默认构造器中几个重要的参数

1
2
3
4
int threshold; // 容纳的 key-value 对极限 
final float loadFactor; // 负载因子
int modCount;
int size;

Node[] table 的初始化长度 length 默认为 16。

loadFactor 为负载因子,默认值为 0.75;

threshold 为 HashMap 所能容纳的最大数据量的 Node (键值对) 个数。

1
threshold = length * loadFactor

亦即在数组长度一定的情况下,负载因子越大,所能容纳的键值对个数越多。

threshold 即在此 loadFactor 和 length (数组长度) 下所允许的最大元素数目,超过这个数目就得重新 resize (扩容),扩容后的 HashMap 容量为之前容量的 2 倍

需要注意的是,默认的负载因子 0.75 是对空间和时间效率的一个平衡选择。除非在时间和空间较特殊的情况下,若内存空间很多而又对时间效率要求很高时,可以降低负载因子 loadFactor 的值;相反,若内存空间紧张而对时间效率要求不高时,可以增加负载因子 loadFactor 的值,其值可以大于 1。

modCount 字段用来记录 HashMap 内部结构发生变化的次数,主用于迭代的快速失败。注意的是,内部结构发生变化即结构的变动,如 put 新键值对。但是,某个 key 对应的 value 值被覆盖不属于结构变化。

size 即 HashMap 中实际存在的键值对数量。然而,注意勿和 table 的长度 length、容纳最大键值对数量 threshold 的区别。

紧接着,来看存储过程的核心方法 put(),进去源码如下:

1
2
3
4
public V put(K key, V value) {
// hash key 的 hashCode()
return putVal(hash(key), key, value, false, true);
}

进入 putVal() 如下:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict)
{

HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
// 判断键值对数组 table[i] 是否为空或为 null 值,是则调用 resize() 扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 判断键值 key 计算 hash 值所得到插入的数组索引 i
if ((p = tab[i = (n - 1) & hash]) == null)
// 新建节点添加
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
// 判断 table[i] 的首个元素,其 hashCode 及 equals 是否和 key 一致
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 覆盖 value
e = p;
// 判断 table[i] 是否为红黑树
else if (p instanceof HashMap.TreeNode)
// 树中插入键值对
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历 table[i]
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断链表长度是否大于 8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 将链表转化为红黑树,在其中执行插入操作
treeifyBin(tab, hash);
break;
}
// key 已存在,则直接覆盖 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入成功后,判断实际存在的键值对数量 size 是否超过了最大容量限度 threshold
if (++size > threshold)
// 扩容
resize();
afterNodeInsertion(evict);
return null;
}

再来看其读取结构。

读取结构

1
2
3
4
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

进入 getNode() 方法内部:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
final HashMap.Node<K, V> getNode(int hash, Object key) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> first, e;
int n;
K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 第一个节点,直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断第一个节点是否是红黑树
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

总结即从 HashMap 中 get 元素时,先计算 key 的 hashCode,找到数组中对应位置的某一元素,再通过 key 的 equals 方法在对应位置的链表中找到需要的元素。

至此,深入 Java 中的 HashMap (一) 对 HashMap 的简介,以及重点谈到的 put() 和 get() 两个方法,到此结束。(二)将重点从扩容机制和线程安全性角度来谈,未完待续。

本人才疏学浅,如有疏漏错误之处,望读者中有识之士不吝赐教,谢谢。

1
Email: [email protected] / WeChat: Wolverine623

您也可以关注我个人的微信公众号码农六哥第一时间获得博客的更新通知,或后台留言与我交流

参考文献

1.https://tech.meituan.com/java-hashmap.html

2.https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html