Java Hashmap

Posted on

概述

本文翻译自 JDK 1.8 HashMap 的文档。

术语

英文 中文
Hash 哈希
Key 键
Value 值
Bucket 桶
Capacity 容量
Load Factor 负载因子
Iteration 迭代
Initial Capacity 初始容量
Rehashing 重哈希

HashMap

HashMap 的说明

java.util

public class HashMap

extends java.util.AbstractMap

implements java.util.Map, java.lang.Cloneable, java.io.Serializable

基于哈希表的 Map 接口实现。本实现提供了所有可选的 map 操作，允许 null 值和 null 键。（HashMap 类大致相当于 Hashtable，除了它是非同步的并且允许 null)。这个类不保证 map 的顺序，特别的，它也不保证该顺序随着时间保持不变。

假设哈希函数能使元素正确地分散在桶中，本实现将提供常量时间性能的基本操作（get 和 put）。迭代集合时所需的时间与哈希表的“容量”（桶的数量）加上哈希表的大小（键-值对数量）成比例。因此非常重要的一点是，如果迭代的性能非常重要，那么初始容量不应设得太高（或负载因子太低）。

一个 HashMap 实例有两个参数影响其性能：初始容量和负载因子。容量指的是哈希表中桶的数量，初始容量也就是创建哈希表时的容量。负荷因子是用来衡量哈希表容量自动增长之前允许表中数据有多满。当哈希表中的 Entry 的数量超过负载因子与当前容量的乘积时,哈希表将会被重哈希（也就是内部数据结构会被重建），以使哈希表有大约两倍数量的桶。

作为一般规则，默认的负载因子（.75）提供了一个良好的时间和空间成本之间的权衡。更高的值会减少的空间开销，但会增加查找成本（影响大多数 HashMap 类的操作，包括 get 和 put）。设置初始容量时，应当考虑 map 中预期的 Entry 数量和负载因子。如果初始容量大于最大的 Entry 数量除以负载因子，将不会发生重哈希。

如果需要将非常多的键值对存储在 HashMap 实例中，创建一个足够大容量的哈希表将会使存储过程效率更高，相比于扩大哈希表时自动执行的重哈希。需要注意的是使用许多相同 hashCode() 结果的键必然会减缓哈希表的性能。为了减小影响，当键是 Comparable 时，本类将对键使用比较顺序以帮助减少默认顺序造成的不良影响。

注意，本实现是非同步的。如果多个线程并发访问一个哈希表，并且至少有一个线程改变 map 结构，则必须在外部程序中实现同步。（结构改动是指增加或删除一个或多个映射；仅仅改变表中已有的键对应的值并不算结构改动。）这通常是由某个包含了 map 的对象的同步来实现的。

如果不存在这样的对象，应当使用 Collections.synchronizedMap 方法 “封装” map。最好是在创建时完成，以避免对 map 非同步的访问：

Map m = Collections.synchronizedMap(new HashMap(...));

本类所有的“集合视图方法”返回的迭代器都是 “fail-fast” 的。迭代器创建后，如果 map 发生了结构改动（除了迭代器自己的 remove 方法的其他任何方式），迭代器将抛出 ConcurrentModificationException 异常。因此，面对并发修改，迭代器会干净利落地产生失败，而不用冒着未来不确定的时间发生不确定的行为的风险。

注意,迭代器的 fail-fast 行为是无法保证的，一般来说，发生未同步的并发修改时，任何保证都是不可能的。fail-fast 迭代器将尽量抛出 ConcurrentModificationException。因此，编写一个正确性依赖于这个异常的程序，是完全错误的：fail-fast 行为应该只用来检测 bug。

本类属于 Java Collections Framework。

Since: 1.2

See Also: Object.hashCode(), Collection, Map, TreeMap, Hashtable

Type parameters:

  • <K> - 此 map 中维护的键的类型
  • <V> - 映射中值的类型

Implementation Notes

本实现的一些注意点

本 map 通常作为桶式哈希表，但当桶内的数据太多时，它们将会被转换成 TreeNode 桶，与 java.util.TreeMap 的结构类似。大部分方法会尽量使用普通的桶，但如果可用时，会切换到 TreeNode 方法（只需要简单地通过检查结点的 instanceof 结果）。TreeNode 桶可以像其它结点一样遍历和使用，但是额外支持数量过多时更快地查找。但是，由于正常使用时绝大多数的桶不会数量过多，因此检查树型桶的工作会推迟到表方法时。

树型桶（即桶内的元素都是 TreeNode）主要是按 hashCode 排序，但是在冲突的情况下（两个元素属于同样的 “class C implements Comparable” 类型），元素的 compareTo 方法将会用来排序。（我们谨慎地通过反射来检查泛型类型以验证这种情况，见方法 comparableClassFor）。当键有不同的哈希或者可以排序时，为了在最坏的情况下提供 O(logn)的操作，树型桶带来的复杂性增加是值得的。因此，当 hashCode() 方法的返回值分散较差，或许多键的 hashCode 相同，不管是意外还是恶意的，只要它们是可比较的，性能可以优雅地降级。（如果这种情况没有发生，相比于不采取任何预防措施，我们可能会损失时间或空间。但是唯一已知的这种情况源自较差的用户编程实践，因此这点损失也不会有太大的区别。）

因为 TreeNode 大约是正常结点的两倍大，因此，我们仅会在有足够多的结点时才会使用它们（见 TREEIFY_THRESHOLD）。当它们变得太小时（由于移除或重新调整大小），它们会被转换回普通的桶。在使用分散度很好的 hashCode 时，树型桶很少会被使用。理想的随机 hashCode 条件下，桶中结点的频度符合泊松分布（http://en.wikipedia.org/wiki/Poisson_distribution），在默认的负载因子为 0.75 时，泊松分布参数的平均值为 0.5，虽然由于调整粒度会有一个较大的方差。如果忽略方差，表大小 k 的期望值是 (exp(-0.5) * pow(0.5, k) / factorial(k))。最初几个的值是：

  • 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
  • 更大: 小于 1/10000000

一般情况下，树型桶的根是它的第一个结点。但是，有时（目前仅当执行 Iterator.remove 时），根可能会在其它地方，但是会在父结点链接时（TreeNode.root() 方法），恢复正常。

当桶中的表被转换成树，或者被分裂，或者被转换回普通的桶时，我们会保持访问和遍历的相对顺序（如 Node.next）不变，以更好地保持局部性，并且在调用 iterator.remove 时稍微简化对分裂和遍历的处理。当在插入时使用比较器时，为了保持总体顺序，我们会比较类和 identityHashCode。

类似“并发编程”的“基于SSA”的编程风格有助于避免复杂的指针操作时的对齐错误。

初始值

类中的一些初始值说明

  • DEFAULT_INITIAL_CAPACITY

1 << 4, 也就是16，默认的初始容量，必须是 2 的幂

  • MAXIMUM_CAPACITY

1 << 30，最大容量

  • DEFAULT_LOAD_FACTOR

0.75，默认的负载因子

  • TREEIFY_THRESHOLD

8，桶中元素个数的阈值，当超过这个值时，桶会被转换成树

  • UNTREEIFY_THRESHOLD

6，桶中元素个数的阈值，当小于这个值时，桶中的树结构会被转换回正常的结构。这个值必须小于 TREEIFY_THRESHOLD，并且最大为 6。

  • MIN_TREEIFY_CAPACITY

64，可以被转换成树的最小的容量。如果容量小于这个值，当桶中元素过多时，表会被扩大，而不是转换成树。这个值至少为 4 * TREEIFY_THRESHOLD。