万字 HashMap 详解,基础(优雅)永不过时 —— 原理篇

语言: CN / TW / HK

theme: jzman

本文已收录到  GitHub · AndroidFamily,有 Android 进阶知识体系,欢迎 Star。技术和职场问题,请关注公众号 [彭旭锐] 私信我提问。

前言

大家好,我是小彭。

在上一篇文章里,我们聊到了散列表的整体设计思想,在后续几篇文章里,我们将以 Java 语言为例,分析标准库中实现的散列表实现,包括 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。

今天,我们来讨论 Java 标准库中非常典型的散列表结构,也是 “面试八股文” 的标准题库之一 —— HashMap。

提示: 本文源码基于 Java 8 HashMap,并关联分析部分 Java 7 HashMap。


学习路线图:


1. 回顾散列表原理

散列表是基于散列思想实现的 Map 数据结构,将散列思想应用到散列表数据结构上时,就是通过 hash 函数提取键(Key)的特征值(散列值),再将键值对映射到固定的数组下标中,利用数组支持随机访问的特性,实现 O(1) 时间的存储和查询操作。

由于散列表是压缩映射,所以在散列表的设计中存在 2 次散列冲突:

  • 第 1 次 - hash 函数的散列冲突: 这是一般意义上的散列冲突;
  • 第 2 次 - 散列值取余转数组下标: 本质上,将散列值转数组下标也是一次 Hash 算法,也会存在散列冲突。同时,这也说明 HashMap 中同一个桶中节点的散列值不一定是相同的。

散列表示意图

事实上,我们无法避免散列冲突,只能保证散列表不会因为散列冲突而失去正确性。常用的散列冲突解决方法有 2 类:

  • 开放寻址法: 例如 ThreadLocalMap。
  • 分离链表法: 例如 HashMap。

开放寻址法示意图

分离链表法示意图

影响散列表性能的关键在于 “散列冲突的发生概率”,冲突概率越低,时间复杂度越接近于 O(1)。 那么,哪些因素会影响冲突概率呢?主要有 3 个:

  • 因素 1 - 装载因子: 装载因子 (Load Factor) = 散列表中键值对数目 / 散列表的长度。随着散列表中元素越来越多,空闲位置越来越少,就会导致散列冲突的发生概率越来越大,使得散列表操作的平均时间会越来越大;
  • 因素 2 - 采用的冲突解决方法: 开放寻址法的冲突概率天然比分离链表法高,适合于小数据量且装载因子较小的场景;分离链表法对装载因子的容忍度更高,适合于大数据量且大对象(相对于一个指针)的场景;
  • 因素 3 - 散列函数设计: 散列算法随机性和高效性也会影响散列表的性能。如果散列值不够随机,即使散列表整体的装载因子不高,也会使得数据聚集在某一个区域或桶内,依然会影响散列表的性能。

2. HashMap 的特点

2.1 说一下 HashMap 的底层结构?

HashMap 是基于分离链表法解决散列冲突的动态散列表:

  • 在 Java 7 中使用的是 “数组 + 链表”,发生散列冲突的键值对会用头插法添加到单链表中;
  • 在 Java 8 中使用的是 “数组 + 链表 + 红黑树”,发生散列冲突的键值对会用尾插法添加到单链表中。如果链表的长度大于 8 时且散列表容量大于 64,会将链表树化为红黑树。在扩容再散列时,如果红黑树的长度低于 6 则会还原为链表;
  • HashMap 的数组长度保证是 2 的整数幂,默认的数组容量是 16,默认装载因子上限是 0.75,扩容阈值是 12(16*0.75);
  • 在创建 HashMap 对象时,并不会创建底层数组,这是一种懒初始化机制,直到第一次 put 操作才会通过 resize() 扩容操作初始化数组;
  • HashMap 的 Key 和 Value 都支持 null,Key 为 null 的键值对会映射到数组下标为 0 的桶中。

2.2 为什么 HashMap 采用拉链法而不是开放地址法?

我认为 Java 给予 HashMap 的定位是一个相对 “通用” 的散列表容器,它应该在面对各种输入场景中都表现稳定。

开放地址法的散列冲突发生概率天然比分离链表法更高,所以基于开放地址法的散列表不能把装载因子的上限设置得很高。在存储相同的数据量时,开放地址法需要预先申请更大的数组空间,内存利用率也不会高。因此,开放地址法只适合小数据量且装载因子较小的场景。

而分离链表法对于装载因子的容忍度更高,能够适合大数据量且更高的装载因子上限,内存利用率更高。虽然链表节点会多消耗一个指针内存,但在一般的业务场景中可以忽略不计。

我们可以举个反例,在 Java 原生的数据结构中,也存在使用开放地址法的散列表 —— 就是 ThreadlLocal。因为项目中不会大量使用 ThreadLocal 线程局部存储,所以它是一个小规模数据场景,这里使用开放地址法是没问题的。

2.3 为什么 HashMap 在 Java 8 要引入红黑树呢?

因为当散列冲突加剧的时候,在链表中寻找对应元素的时间复杂度是 O(K),K 是链表长度。在极端情况下,当所有数据都映射到相同链表时,时间复杂度会 “退化” 到 O(n)。

而使用红黑树(近似平衡的二叉搜索树)的话,树形结构的时间复杂度与树的高度有关, 查找复杂度是 O(lgK),最坏情况下时间复杂度是 O(lgn),时间复杂度更低。

2.4 为什么 HashMap 使用红黑树而不是平衡二叉树?

这是在查询性能和维护成本上的权衡,红黑树和平衡二叉树的区别在于它们的平衡程度的强弱不同:

平衡二叉树追求的是一种 “完全平衡” 状态:任何结点的左右子树的高度差不会超过 1。优势是树的结点是很平均分配的;

红黑树不追求这种完全平衡状态,而是追求一种 “弱平衡” 状态:整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率,但是能够换取一部分维持树平衡状态的成本。

2.5 为什么经常使用 String 作为 HashMap 的 Key?

  • 1、不可变类 String 可以避免修改后无法定位键值对: 假设 String 是可变类,当我们在 HashMap 中构建起一个以 String 为 Key 的键值对时,此时对 String 进行修改,那么通过修改后的 String 是无法匹配到刚才构建过的键值对的,因为修改后的 hashCode 可能会变化,而不可变类可以规避这个问题。
  • 2、String 能够满足 Java 对于 hashCode() 和 equals() 的通用约定: 既两个对象 equals() 相同,则 hashCode() 相同,如果 hashCode() 相同,则 equals() 不一定相同。这个约定是为了避免两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对,引起矛盾。

2.6 HashMap 的多线程程序中会出现什么问题?

  • 数据覆盖问题:如果两个线程并发执行 put 操作,并且两个数据的 hash 值冲突,就可能出现数据覆盖(线程 A 判断 hash 值位置为 null,还未写入数据时挂起,此时线程 B 正常插入数据。接着线程 A 获得时间片,由于线程 A 不会重新判断该位置是否为空,就会把刚才线程 B 写入的数据覆盖掉)。事实上,这个未同步数据在任意多线程环境中都会存在这个问题。
  • 环形链表问题: 在 HashMap 触发扩容时,并且正好两个线程同时在操作同一个链表时,就可能引起指针混乱,形成环型链条(因为 Java 7 版本采用头插法,在扩容时会翻转链表的顺序,而 Java 8 采用尾插法,再扩容时会保持链表原本的顺序)。

2.7 HashMap 如何实现线程安全?

有 3 种方式:

  • 方式 1 - 使用 hashTable 容器类(过时): hashTable 是线程安全版本的散列表,它会在所有方法上增加 synchronized 关键字,且不支持 null 作为 Key。
  • 方法 2 - 使用 Collections.synchronizedMap 包装类: 原理也是在所有方法上增加 synchronized 关键字;
  • 方法 3 - 使用 ConcurrentHashMap 容器类: 基于 CAS 无锁 + 分段实现的线程安全散列表;

3. HashMap 的属性

在分析 HashMap 的执行流程之前,我们先用一个表格整理 HashMap 的属性:

| 版本 | 数据结构 | 节点实现类 | 属性 | | --- | --- | --- | --- | | Java 7 | 数组 + 链表 | Entry(单链表) | 1、table(数组)
2、size(尺寸)
3、threshold(扩容阈值)
4、loadFactor(装载因子上限)
5、modCount(修改计数)
6、默认数组容量 16
7、最大数组容量 2^30
8、默认负载因子 0.75 | | Java 8 | 数组 + 链表 + 红黑树 | 1、Node(单链表)
2、TreeNode(红黑树) | 9、桶的树化阈值 8
10、桶的还原阈值 6
11、最小树化容量阈值 64 |

HashMap.java

```java public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

// 默认数组容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 疑问 3:为什么最大容量是 2^30 次幂?
// 疑问 4:为什么 HashMap 要求数组的容量是 2 的整数幂?
// 数组最大容量:2^30(高位 0100,低位都是 0)
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子:0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 疑问 5:为什么要设置桶的树化阈值,而不是直接使用数组 + 红黑树?
// (Java 8 新增)桶的树化阈值:8
static final int TREEIFY_THRESHOLD = 8;

// (Java 8 新增)桶的还原阈值:6(在扩容时,当原有的红黑树内数量 <= 6时,则将红黑树还原成链表)
static final int UNTREEIFY_THRESHOLD = 6;

// 疑问 6:为什么要在设置桶的树化阈值后,还要设置树化的最小容量?
// (Java 8 新增)树化的最小容量:64(只有整个散列表的长度满足最小容量要求时才允许链表树化,否则会直接扩容,而不是树化)
static final int MIN_TREEIFY_CAPACITY = 64;

// 底层数组(每个元素是一个单链表或红黑树)
transient Node<K,V>[] table;

// entrySet() 返回值缓存
transient Set<Map.Entry<K,V>> entrySet;

// 有效键值对数量
transient int size;

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

// 装载因子上限
final float loadFactor;

// 修改计数
transient int modCount;

// 链表节点(一个 Node 等于一个键值对)
static class Node<K,V> implements Map.Entry<K,V> {
    // 哈希值(相同链表上 Key 的哈希值相同)
    final int hash;
    // Key(相同链表上 Key 的 equals() 不同)
    final K key;
    // Value(Value 不影响节点位置)
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // Node 的 hashCode 取 Key 和 Value 的 hashCode
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    // 两个 Node 的 Key 和 Value 都相等,才认为相等
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

// (Java 8 新增)红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    // 父节点
    TreeNode<K,V> parent;
    // 左子节点
    TreeNode<K,V> left;
    // 右子节点
    TreeNode<K,V> right;
    // 删除辅助节点
    TreeNode<K,V> prev;
    // 颜色
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    // 返回树的根节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

} ```

LinkedHashMap.java

java static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

相比于线性表,HashMap 的属性可算是上难度了,HashMap 真卷。不出意外的话又有小朋友出来举手提问了🙋🏻‍♀️

  • 🙋🏻‍♀️疑问 1: 为什么字段不声明 private 关键字?(回答过多少次了,把手给我放下)
  • 🙋🏻‍♀️疑问 2: 为什么字段声明 transient 关键字?(回答过多少次了,把手给我放下)
  • 🙋🏻‍♀️疑问 3:为什么最大容量是 2^30?

因为 HashMap 要求散列表的数组容量是 2 的整数幂 ,而 int 类型能够表示的最大 2 的整数幂就是 2^30,即高位第 31 位是 1,低位都是 0。

  • 🙋🏻‍♀️疑问 4:为什么 HashMap 要求数组的容量是 2 的整数幂?

这个问题我们下面再回答。

  • 🙋🏻‍♀️疑问 5:为什么要设置桶的树化阈值,而不是直接使用数组 + 红黑树?

其实,红黑树是 “兜底” 策略,而不一定是最优策略。

首先,红黑树节点本身的内存消耗是链表节点的 2 倍。其次,红黑树在添加和删除数据时需要维护红黑树的性质,会增加旋转等操作。所以,当桶的节点数很低时,并不能体现出红黑树的优势(类似于 Arrays.sort 在子数组长度小于 47 时用插入排序而不是快速排序)。

再结合散列分析的数据统计,在装载因子上限为 0.75 且平均负载因子为 0.5 HashMap 中,桶长度的出现频率符合泊松分布,大部分的桶分布在 0 ~ 3 的长度上,长度大于 8 的桶的出现频率低于千万分之一。

综上所述,为了避免在小桶中使用红黑树,HashMap 在桶的长度大于等于 8 时才会树化为红黑树。并且在扩容再散列时,如果桶的长度小于等于 6,也会还原为链表。

散列冲突数据统计

```bash

装载因子上限为 0.75、平均负载因子为 0.5,且散列函数随机性良好时,不同长度桶的出现频率

0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million # 低于千万分之一 ```

  • 🙋🏻‍♀️疑问 6:为什么要在设置桶的树化阈值后,还要设置树化的最小容量?

这是为了避免无效的树化。

在散列表的容量较低时,添加数据时很容易会触发扩容。此时,一部分原本已经树化的桶会由于长度下降而退还回链表。因此,红黑树为树化操作设置了最小容量要求:如果链表长度达到树化阈值,但散列表整体的长度未达到最小容量要求,那么就直接扩容,而不是在桶上树化。


后续源码分析,见下一篇文章:万字 HashMap 详解,基础(优雅)永不过时 —— 源码篇


本文为稀土掘金技术社区首发签约文章,14天内禁止转载,14天后未获授权禁止转载,侵权必究!

参考资料