Java HashMap

发表于 更新于 分类于 ， 阅读次数：

基础

我们先大概瞥一眼 JDK 1.7 之前的 HashMap 结构：

HashMap

简而言之，HashMap 是由数组组成的一定数量的桶（bucket）。在进行存储时，使用 key 的 hashcode() 通过 hash 函数计算得到 hash 值，然后通过 **hash 值 % 数组长度**来确定将 Entry(key + value) 放入数组的哪个桶里。

为什么要用 hashcode 来确定位置？

为了高效的定位元素在数组中的位置，以及使放入的元素尽可能均匀的分布在数组中。

正确实现 hashcode() 方法返回的 hash 值可以达到散列分布的目的，同样的键也会返回相同的 hash 值，因此我们使用 hash 信息来确定元素在数组中的下标信息以达到快速访问。

如果 hash 函数足够完美，将能实现数据的均匀分配，此时时间复杂度为 O(1)。但是开发者通常会编写较差的哈希函数，这将导致分布不均。

散列函数也被用于对称、非对称加密算法、签名或摘要（Digest）算法中，比如：MD 加密、SHA 加密

Bad hashmap

Hash 碰撞及解决（Collision）

此时数组将会有很大一部分被浪费，而且含多不同的键将会产生相同的 hash 值**（hash 碰撞）**。

Hash function

负载因子与容量

为了解决这个问题，一方面，我们可以增大哈希值的取值空间来减少冲突的可能性，比如使 hash 表大于所需的总数据量。期望只要有哈希表的 70 % 被占用就足够。存储元素的个数和哈希表桶的数量的比值就叫做负载因子（Load factor）。
$$
\begin{align*}
Load \quad Factor = \frac{Total \quad number \quad of \quad items \quad stored} {Size \quad of \quad the \quad Buckets \quad array}
\end{align*}
$$

负载因子的值通常是可配置的，并在时间和空间成本之间进行权衡，下图是负载因子值调低调高时的影响。

Tradeoff Time And Space

Java 中 HashMap 的默认负载因子是 0.75，也就是说只要哈希表的 75 % 被占用就足够了。

容量（Capacity） 在 Java HashMap 中指桶的数量，也就是负载因子的被除数。

Java HashMap 的默认初始容量为 16，即存储区数组在首次插入时被延迟初始化。

当插入的元素到达一定的阈值，HashMap 将会扩容来重新计算哈希，该阈值的计算公式为：
$$
Threshold = (Current Capacity) * (Load Factor)
$$
以 HashMap 的默认值计算，则为：
$$
Threshold = 16 * 0.75 = 12
$$
也就是说当插入第 13 个元素后会进行扩容为之前的两倍 oldThreshold << 1，此时将发生重新哈希（Rehashing），由于重新哈希处理增加了存储桶的数量，因此降低了负载因子。

Rehashing

为什么 HashMap 加载因子默认是 0.75？

这个跟一个统计学里很重要的原理——泊松分布有关。

泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。

Poisson distribution
等号的左边，P 表示概率，N 表示某种函数关系，t 表示时间，n 表示数量。等号的右边，λ 表示事件的频率。

在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为 0.75 的情况下，节点出现在频率在 Hash 桶（表）中遵循参数平均为 0.5 的泊松分布。忽略方差，即 X = λt，P(λt = k)，其中 λt = 0.5的情况。

所以我们可以知道，其实常数 0.5 是作为参数代入泊松分布来计算的，而加载因子 0.75 是作为一个条件，当 HashMap 长度为length/size ≥ 0.75 时就扩容，在这个条件下，冲突后的拉链长度和概率结果为：

1
2
3
4
5
6
7
8
9
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

计算结果如上述的列表所示，当一个桶中的链表长度达到 8 个元素的时候，概率为 0.00000006，几乎是一个不可能事件。

选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。

寻址

另一方面，为了给冲突元素一个合适的位置存储，我们将解决方案从寻址方向上分为两个大类：

开放式寻址（Open Addressing） 闭合式寻址（Closed Addressing）
通过在哈希表数组本身中搜索另一个空存储桶来处理冲突。 键始终存储在散列到的桶中。在每个桶的基础上使用单独的数据结构来处理冲突。
每个桶中最多存放一个键。 每个桶存储任意键数。
理论最大负载系数为1。 没有理论上的最大负载系数。
哈希表数组的大小必须始终至少与哈希表中键的数量一样大。 性能随着负载系数的增长而降低。

开放式寻址相关技术

  • 线性探测（Linear Probing）
  • 二次方探测（Quadratic Probing）
  • 再哈希（Double hashing）
  • 罗宾汉哈希（Robin Hood hashing）
  • 等

插入和查找扫描阵列的顺序在实现之间有所不同。下面介绍一些常用技术。 （所有索引均以数组长度为模。）

线性探测

如果在存储区 i 中发生冲突，搜索序列将使用下列索引继续：

  • i + 1
  • i + 2
  • i + 3
  • …

由于探测序列在内存中是线性的，因此该方法可实现良好的缓存性能。

二次方探测

通过二次方探测，从存储桶 i 开始的搜索序列如下：

  • i + 12
  • i + 22
  • i + 32
  • …
再哈希

使用二次哈希（另一个哈希函数）双重哈希，h 用于确定搜索序列中步骤的大小。如果 h2(key) = j，则从存储区 i 开始的搜索序列如下：

  • i + 1 × j
  • i + 2 × j
  • i + 3 × j

（如果 j 恰好等于数组长度的倍数，则使用 1 代替。）

Comparison of Probing Techniques

闭合式寻址相关技术

  • 使用链表单独存储 hash 相同的键值（拉链法）
  • 使用动态数组单独存储 hash 相同的键值
  • 使用自平衡二叉树

Java HashMap 是结合第一种和第三种的实现。

HashMap

HashMap

HashMap JDK 1.8

先总体了解下 HashMap 作为集合类的特性：

  • HashMap 的键值都不能存储基本类型

    要存储基本类型提高性能，可以使用 Eclipse Collection 的原始类型集合类。

  • 支持一个 null 键和多个 null value

  • 键必须唯一，重复的键值将被后面的值替代

  • 使用哈希技术存储索引，所以不保证插入顺序

  • 非线程安全，需自己保证同步

    可以使用 Collections.synchronizedMap(new HashMap(...)); 包裹，或使用 HashTable，ConcurrentHashMap，后者性能更高

  • 快速失败机制

    在 Java 非线程安全的集合类中，遍历集合中，对集合做额外的操作比如调用新增、删除会立即停止当前操作并抛出 ConcurrentModificationException，在 HashMap 中使用 modCount 记录修改次数，如果遍历中该记录和开始时不相同，则报错。

    可以使用 Iterator 接口安全的移除元素，一般集合会实现安全的移除操作。但是多线程环境下得保证 Iterator 实现类的线程安全。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    final HashMap<String, String> hashMap = new HashMap<>(20, 0.75f);
    final Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        if (iterator.next().getKey().equals("test")) {
            iterator.remove(); // ok!
        }
    }
    // java 8 removeIf
    hashMap.entrySet().removeIf(stringStringEntry -> stringStringEntry.getKey().equals("test"));

  • 标记了 Serializeable 和 Cloneable 接口

数组桶

在代码中，桶数组用如下变量表示：

1
transient Node<K,V>[] table;

这里需要注意几点：

  • 桶数组并没有在构造方法中初始化，而是在第一次使用时才会分配内存，比如 put、compute、merge 等。

  • 当分配内存时，长度总是 2 的幂次方。

    为什么选择 2 的幂次方？

    由于为了达到高效处理性能，很多操作都是通过位运算完成。比如其中的 hash 方法，计算桶索引等，后面会详细说明。

  • 如果初始化时传入的桶的容量 capacity 不是 2 的幂次方，将会使用该位运算算法增加到最近的 2 次幂。

单链表

每个桶内部由链表组成，在代码中为类 Node<K, V> 的实例，此类是 HashMap 类的静态内部类，并且实现 Map.Entry<K, V> 接口，此节点的表示形式为：

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;			// 使用 hash 定位桶
        final K key;				// 节点存放的 key
        V value;						// 节点存放的 值
        Node<K,V> next;     // 指向链表的下一个节点
}

HashMap 如何计算桶索引？

之前我们提到计算索引是使用哈希函数计算的 hash 值和桶数组长度求余，但是求余的效率并没有直接按位运算的高。同样我们需要借助一些位运算的技巧，这里 n 为桶数组的长度：

1
2
3
4
5
6
7
index = hash(key) & (n-1)  // 相当于求 hash(key) % n，当 n 为 2 的次幂且不为 0 时成立

// hash 函数求 hash 值  
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

注意，为什么这里 hash 函数需要将高位数据移位到低位进行异或运算呢？这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。

计算桶索引并不只是发生在 put 方法时，在调用 get、contains、remove 时都会调用 hash 方法重新计算 hash 值并在计算桶索引。

为什么桶内不使用 ArrayList 或 LinkedList？

HashMap 内部使用单向链表来维护哈希冲突的元素，但为什么不用数组或双向链表，这其实是一个平衡后的考虑：

  • ArrayList 使用较少的空间，检索速度快，但是最坏的情况下插入和删除元素的时间复杂度可能为 O(n)
  • LinkedList 双向链表使用更多空间维护前后节点信息，但是插入或删除元素的时间复杂度为 O(1)

使用单向链表的好处在于，其既可以使空间相对较少，也能保证删除和插入的时间复杂度为 O(1)。但是如果链表过长，最坏的可能是所有元素都放入一个桶里，此时时间复杂度将变为 O(n)。为了优化这一点，JDK 1.8 使用了红黑树来优化链表过长的情况。

当桶数组的长度超过 MIN_TREEIFY_CAPACITY 且桶中的元素超过 TREEIFY_THRESHOLD 值时，链表转为红黑树。

当桶中元素减少至 UNTREEIFY_THRESHOLD 时，红黑树退回到链表。

为什么桶内元素过长时用红黑树？

Red Black Tree

因为当大量哈希冲突的时候会导致节点链表越来越长从而降低 HashMap 性能。而红黑树为自平衡二叉搜索树，重新平衡并不完美，但保证在 O(logN) 时间内搜索，其中 n 是树的节点数。插入和删除操作，以及树的重排和重新着色，也在 O(logN) 时间内执行。 因此在数据量大的且桶中冲突较大的散列表中红黑树比单向链表更有优势。

**本质上这是个安全问题。**因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个很长的链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。

为什么选择红黑树而不是二叉树或绝对平衡二叉树呢？
首先，二叉树在极端情况下依然会形成链表。例如 1,2,3,4 的 hashCode 相同时，二叉树退化成链表；
再是，绝对平衡就好像有强迫症一样把精力消耗在如何达到平衡上，因此造成不必要的性能开销；
而红黑树它是一棵自平衡树但不是绝对平衡树，优点有以下：

  1. 树属于折半查找，于较长的链表相比查询效率要高
  2. 自平衡树解决了二叉树的计算情况问题（二叉树退化成链表）
  3. 非绝对平衡树比绝对平衡树在增删节点时要高效一些

因此红黑树是综合性能较强的树型数据结构。

LinkedHashMap

linked-hash-map-uml

我们知道 HashMap 使用 hash 函数定位桶，桶内部使用单向链表存储冲突元素，不能保证插入的顺序。LinkedHashMap 继承了 HashMap，在原有的数据结构基础上，将所有桶内元素通过双向链表链接起来，该链表定义了迭代的顺序，默认是数据插入的顺序，也可以配置为访问顺序。转换为红黑树时也维护链表。

如果将键重新插入映射中，则插入顺序不会受到影响。

LinkedHashMap

该实现提供了顺序保证，但是并没有增加时间复杂度，和 HashMap 一样还是 O(1)。TreeMap 由于使用了红黑树来提供顺序保证，所以时间复杂度为 O(logN)。

构建

Insert Order LinkedHashMap

我们可以使用其它 Map 来生成一个 LinkedHashMap 的拷贝，而不用管之前的实现。很适合一种以无序输入开始，最后保留该顺序的副本操作。

1
2
3
4
void foo(Map m) {
    Map copy = new LinkedHashMap(m);
     ...
}

Access Order LinkedHashMap

还提供了一个特殊的构造函数来创建一个迭代顺序为上次访问顺序的 LinkedHashMap。访问顺序从最近最少访问到最近最多访问。

1
2
3
4
5
6
7
8
9
10
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)
  
构造一个具有指定初始容量、加载因子和排序模式的空 LinkedHashMap 实例。
  
参数:
initialCapacity - 初始化桶容量
loadFactor - 负载因子
accessOrder - 排序模式 - true 为访问顺序 access-order, false 为插入顺序 insertion-order

这种 Map 非常适合构建 LRU (Least recently used) 缓存。而且提供了一个可重写移除旧元素的 protected 的方法：

1
2
3
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

使用该方法很容易构建一个首先丢弃最近最少使用的项目的 LRU 缓存：

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
public class LRUCache {

    private int capacity;
    private Map<Integer, Integer> cache;

    public LRUCache(final int capacity) {
        this.capacity = capacity;
        // 使用特殊的构造方法，传入 true 为访问顺序，最近最多访问在前
        this.cache = new java.util.LinkedHashMap<Integer, Integer> (capacity, 0.75f, true) {
            // 定义put后的移除规则，大于容量就删除eldest
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        } else
            return -1;
    }

    public void set(int key, int value) {
        cache.put(key, value);
    }
}

并发性

和 HashMap 一样，LinkedHashMap 的实现也不是同步的，非线程安全。因此，如果您打算从多个线程访问它，并且这些线程中至少有一个可能会在结构上改变它，那么必须从外部进行同步。最容易的实现为：

1
Map m = Collections.synchronizedMap(new LinkedHashMap());

与 HashMap 的区别在于需要进行结构修改。在按访问顺序（access-ordered）链接的哈希映射中，仅调用 get API 时会导致结构修改。除此之外，还有诸如 put 和 remove 之类的操作。

和 TreeMap 比较

以下是 TreeMap、HashMap 和 LinkedHashMap 之间的重要区别。

No. 关键点 TreeMap HashMap LinkedHashMap
1 元素的顺序 插入到 TreeMap 中的元素根据其键的自然顺序进行排序，或者通过在 Map 创建时提供的 Comparator 进行排序，具体取决于使用的构造函数。 HashMap 不保证 Map 的顺序，也不保证顺序随时间保持不变。 LinkedHashMap 默认遵循元素的插入顺序，并维护插入元素的顺序。
2 内部实现 TreeMap 的内部实现不允许存储 null 键，但允许 null 值。 HashMap 允许存储一个 null 键以及多个 null 值。 LinkedHashmap 的内部实现与 HashMap 相似，因此允许存储一个 null 键和多个 null 值。
3 时间复杂度 TreeMap 的 get、put 和 remove 操作的时间复杂度都是 O(logN)，比 HashMap 大。 HashMap 在 get、put 和 remove 操作的情况下具有 O(1) 的复杂性。 LinkedHashMap 具有与 HashMap 相同的复杂度，即 O(1)。
4 继承 TreeMap 实现了 Collection 框架的 SortedMap 接口，它是 Map 的子代。TreeMap 内部实现了红黑树（一种自平衡二叉搜索树）。 HashMap 实现了简单的 Map 接口，并在内部使用散列来存储和检索其元素。 LinkedHashMap 扩展了 HashMap 并在内部像 HashMap 一样使用散列。
5 索引性能 与 HashMap 和 LinkedHashMap 相比，TreeMap 维护其元素的顺序，因此性能指标较低，并且需要更多内存。 HashMap 不维护其元素的任何插入顺序，因此与 TreeMap 相比更快，也不根据其值对其元素进行排序，因此也比 LinkedHashMap 更快。 LinkedHashMap 比 TreeMap 快，但比 HashMap 慢。
6 比较 TreeMap 中的元素通过使用 compareTo() 方法进行比较，其中也可以提供自定义实现。 HashMap 使用 Object 类的 compare() 方法进行元素比较。 LinkedHashMap 也使用 Object 类的 compare() 方法进行元素比较。

参考资料

  1. hash-tables-open-vs-closed-addressing 开放寻址和闭合寻址比较
  2. hash-tables-open-addressing 介绍开放式寻址
  3. hash-tables hash table 实现