Toc
  1. 概述
  2. HashMap 的数据结构
    1. 扩容机制
  3. 均匀分布
  4. equals 方法和 hashCode 方法
  5. Hashtable
  6. ConcurrentHashMap
Toc
0 results found
HashMap 解析
2020/01/05 Development Java HashMap

在 Java 和 Android 的开发中,我相信没有人没用过 HashMap 了吧。这几乎是 Java 中最重要的类之一,作为 Key-Value 存储类型的典范,我们在学会使用的同时,也必须要明白 HashMap 内部的实现原理,同时也必须知道它的一些衍生类,以及它们的用法。

概述

话不多说,先来看一下 HashMap 在官方文档里的定义:

HashMap 是 Map 接口基于哈希表的实现。这个实现提供了所有可用的对 map 的操作,而且还允许插入 null 值和 null 键。

HashMap 与 Hashtable 类差不多,但 HashMap 是异步的,并且允许 null 值 / 键。这个类无法保证 map 内元素的顺序;更特别的是,它也无法保证能一直按照某个顺序排列。

Map 接口有三个比较重要的具体实现类:HashMapWeakHashMapTreeMap。HashMap 还有一个重要的子类 LinkedHashMap,它们几个都是非线程安全的类。

我们可以通过一张图简单了解一下它们之间的关系:

可以看到,刚才官方文档中提到的 Hashtable,也是 Map 的一个实现类,它的官方描述中有这么一段:

不像 collection 的实现那样,Hashtable 是同步的。如果不要求线程安全,那你可以使用 HashMap 来替代 Hashtable;如果你对线程安全要求非常高,那推荐你使用 java.util.concurrent.ConcurrentHashMap 来替代 Hashtable。

后面我们会讨论 HashtableConcurrentHashMap

HashMap 的数据结构

HashMap 的数据结构是我们非常常用的数据结构,就是由 数组和链表组合构成 的数据结构。如下图所示:

数组的每个位置都存储了一个 key-value 这样的实例,在 Java 7 中叫 Entry,在 Java 8 中叫 Node。这个数组每个元素原本都是 null,在 put 插入数据的时候会根据 key 值的 hash 去计算一个 index 值。

比如我调用put("debugLife", 42),这个时候会通过哈希函数计算出插入的位置,比如说 index 为 2 吧,那结果就如下图所示:

那么,只用一个数组就好了呀,为啥还要用到链表?

原因很简单,数组长度有限,在有限的长度里使用哈希,会有很大概率出现不同的 key 的计算出的 index 结果相同。比如我调用 put("lifeDebug, 24) 计算出的 index 也为 2,就会出现下面的情况:

上面 index 为 2 的两对 key-value 形成了一个链表。这点我们可以通过查看 Node 的代码来佐证:

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node next;
...
}

那么问题来了,如果两次计算的 index 相同,那新的 Node 在插入的时候,是怎么插入的?

在 Java 8 之前是 头插法,也即新来的 Node 会取代原来的 Node,原有值就被推到链表中去,像上面的图一样。

但是从 Java 8 之后,就采用 尾部插入 了。为什么呢?这个要先从 HashMap 的 扩容机制 说起。

扩容机制

刚才上面提到了,数组的长度是有限的,当数据多次插入,达到一定的数量之后,就会进行 扩容(resize)。扩容的因素有两个:

  • Capacity:HashMap 当前的容量
  • LoadFactor:负载因子,默认值是0.75f
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

负载因子可以理解为,如果当前容量是 100,存 75 个还没事,但存第 76 个的时候,就要进行扩容。我们来看看代码:

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (++size > threshold)
resize();
}

// 扩容的阈值(容量 * 负载因子)
int threshold;

// 默认的容量,必须是 2 的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 如果构造函数未指定的话,负载因子就是 0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;

而扩容也并不是简单地扩大点容量就完事了,我们来简单看一下 resize() 的代码:

// 初始化或者扩容为原来的 2 倍。
// 如果内容为 null,分配默认容量大小的区域。
// 如果不是,因为我们使用了『2 次幂扩展』,所有的元素要么待在原来的 index,要么就在新 table 里偏移『2 次幂』个位置。
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 数据量已经到最大值 1 << 30 了,就将阈值设置为 Integer.MAX_VALUE 吧,也不用扩容了,还扩啥扩
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的容量是旧容量 * 2,新的阈值也是旧的阈值 * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
// 数据量为 0,但是旧阈值大于 0,新的容量就是旧的阈值
else if (oldThr > 0)
newCap = oldThr;
// 数据量为 0,旧阈值等于 0,新的容量就是默认容量,新的阈值就是默认容量 * 默认负载因子
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 经过上面的处理,新的阈值还是 0 的话,就进行对比:
// 如果:新的容量小于最大容量 且 用户设置的阈值小于最大容量的话,新的阈值就是用户设置的阈值
// 否则:新的阈值就是 Integer.MAX_VALUE
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 设置新的阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 先申请一个长度为之前 2 倍的新数组
Node[] newTab = (Node[])new Node[newCap];
// 清空原有数组
table = newTab;
if (oldTab != null) {
// 开始循环处理旧数组
for (int j = 0; j < oldCap; ++j) {
Node e;
// 如果旧数组[j] 元素不为 null
if ((e = oldTab[j]) != null) {
// 把旧数组 [j] 置为 null
oldTab[j] = null;
// 如果旧数组 [j] 的 next 无 Node,也即该 index 上只有它自己
if (e.next == null)
// e.hash & (newCap - 1) 是在计算该元素的 index
newTab[e.hash & (newCap - 1)] = e;
// 如果旧数组[j] 是红黑树节点,就调用它的 split 方法,将其子节点复制到新数组中
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 保留之前数据的顺序
else {
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
// 获取该节点的 next
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

可以看得出来,扩容基本上分为两步:

  1. 将数组的容量扩展为原来的 2 倍
  2. 重新计算所有 Node 的 hash 值,也即 rehash,并插入到新数组中

那么,为什么要 rehash?直接扩容不就完事了?

这样做是不行的,因为数组的容量扩大后,计算 index 的规则也发生了变化

index 的计算规则是index = key.hash & (capacity - 1),之前 capacity 16,变成了 32 的话,值明显就不一样了哇。

好,回到刚才提到的头插尾插。

我们来举个例子,如果现在我们采用头插法,HashMap 的容量是 2,负载因子是 0.75,那么在插入第二个元素的时候,就要准备扩容了。

现在我们往这个容量是 2 的数组里用 不同线程 插入 C、B、A 三个 Entry(头插法是 Java8 之前的哦,要叫 Entry 的哦),那么,在数据插入之后,扩容之前,数据结构可能是下面这样:

我们可以看到链表的指向是 A->B->C,因为使用的是头插法,同一 index 时,新元素总是会被放在链表头的位置

resize()之后,旧数组中同一个 index 上的链表,其 Entry 可能会被分配到其他的 index 上,也即出现下面的情况:

那么待 3 个线程都调整完毕后,就有可能出现下面的情况:

出现了!无限循环! 因为 HashMap 是线程不安全的啊!

而尾插法就不会出现这样的问题。使用头插时会改变链表上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。也就是说原本是 A->B,在扩容后那个链表还是 A->B:

总结起来就是:

  1. Java 7 在多线程操作 HashMap 时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。
  2. Java 8 在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。

但这并不意味着在 Java 8 中可以把 HashMap 用于多线程。从源码的 put/get 方法中,没有任何同步机制,也就是说,无法保证你某个线程 put 进去的值,再 get 的时候还是原值,所以,还是无法保证线程安全。如果要线程安全,请使用 Hashtable 或者 ConcurrentHashMap

均匀分布

从上面的代码里,我们看到了,HashMap 默认初始化长度是1 << 4,也就是 16。那么为什么是 16 呢?我们来看一下。

HashMap 使用了位运算来得到『16』这个数字,我们都知道,位运算比算数运算的效率要高很多,之所以选择 16 这个数字,是为了服务将 key 映射到 index 的这个算法(前面提到过):

index = key.hash & (capacity - 1)

比如我们有个 key 为wtf,它的 hashCode 值是118057,转换为二进制是11100110100101001,使用 capacity 的默认值 16,capacity - 1 是 15,转换为二进制是1111,那么套入 index 计算公式的话,就是:

index = 0b11100110100101001 & 0b1111
index = 9

至于为什么要使用 16,而不是 14、19、25,是因为使用 2 次幂数字的时候,减去 1,转换为二进制全为 1,这种情况下,&出来的结果等同于 hashCode 后几位的值。这种位运算的速度可比取余的方法性能高多了。同时,只要 hashcode 本身分布均匀,index 的分布就是均匀的。

那么,为什么 8 和 32 也是 2 次幂,偏偏选择了 16?其实 8 和 32 也都可以,可能只是作者认为这个数字比较符合常用吧。

另外,还有个小知识点:Hashmap 中的链表大小超过 8 个时会 自动转化为红黑树 ,当删除小于 6 时 重新变为链表 。这是因为根据 ** 泊松分布 ,在负载因子默认为 0.75 的时候,单个 hash 槽内元素个数为 8 的 概率小于百万分之一 **,所以将 7 作为一个分水岭,等于 7 的时候不转换,大于等于 8 的时候才进行转换,小于等于 6 的时候就化为链表。

equals 方法和 hashCode 方法

我们有时为了对比两个对象是否相等,会重写 equals() 方法,那么,我们是不是也需要重写 hashCode() 方法呢?

答案是,如果你的对象要放在 HashMap 中的话,需要。

在 Java 中,所有的对象都继承自 Object 类,Obejct 类中有两个方法 equals()hashCode(),用于比较两个对象是否相等。当我们 ** 未重写 equals()** 时,比较的是两个对象的内存地址,如果是new 了两个对象的话,那肯定不同。

刚才我们提到过,HashMap 是通过 hashCode 来计算 index 的,当我们去 get 的时候,很可能会拿到一个在链表上的值,那么如何确定是链表上的哪个值呢?是了,通过equals(),我们来看看它的代码部分:

public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
Node[] tab; Node 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 TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
// 就是这里啦,对比 hash 和 equals
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

所以,如果我们对 equals() 方法进行了重写,那最好也对 hashCode() 方法进行重写,以保证相同的对象返回相同的 hash 值,不同的对象返回不同的 hash 值。

Hashtable

这个 Map 的派生类是为了在 put/get 达到一定的线程安全,才出现的。它的解决方案比较粗暴,直接在 put/get 方法上加 synchronized 关键字,锁住方法。由此可见,并发度会比较低:

public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}

所以,这个类必定会渐渐地退出舞台,在茫茫历史长河中被慢慢淹没。

ConcurrentHashMap

这个必须要单独来一篇 ConcurrentHashMap 的文章 了。因为 ConcurrentHashMap 内部的原理比 HashMap 要复杂得多,如果赋在这下面,这篇就太长了。

打赏
支付宝
微信
本文作者:CodingRabbit
版权声明:本文首发于CodingRabbit的博客,转载请注明出处!