HashMap

本文主要是用于记录我在阅读Java1.8的 HashMap 源码所做的笔记。对于源码中的注释会进行翻译下来，并且会对其中部分源码进行注释。
这一篇文章主要是介绍 HashMap的静态常量、静态工具方法、属性字段以及比较重要的内部节点类 Node。

介绍

基于哈希 table 实现的 Map 接口。此实现提供所有可选的映射操作，并允许 null 值和 null 键（因为key不允许重复，因此只能有一个键为null）。
（HashMap 类大致相当于 Hashtable，但它是非同步 (unsynchronized) 的并且允许空值。）此类不保证映射的顺序；特别是，它不保证顺序会随时间保持不变。
假设哈希函数能将元素适当地分散到各个桶中，此实现为基本操作（get 和 put）提供常数时间性能。遍历集合视图所需的时间与 HashMap 实例的“容量”（桶的数量）加上其大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子设置得太低）。
HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶的数量，初始容量就是哈希表创建时的容量。负载因子是在哈希表的容量自动增加之前允许其达到的填充程度的度量。当哈希表中的条目数超过负载因子与当前容量的乘积时，哈希表将 重新哈希（rehash）（即重建内部数据结构），使得哈希表的桶数量大约是原来的两倍。
一般来说，默认的负载因子（0.75）在时间和空间成本之间提供了良好的折衷。较高的值减少了空间开销，但增加了查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。
**如果要在HashMap实例中存储许多映射，以足够大的容量创建它将比让它按需执行自动扩容来存储映射更有效。**注意，使用具有相同hashCode()的许多键肯定会降低任何哈希表的性能。为了缓解这一影响，当键是Comparable时，此类可能会使用键之间的比较顺序来帮助解决冲突。
请注意，此实现不是同步 synchronized 的。**如果多个线程同时访问哈希映射，并且至少有一个线程对映射进行了结构修改，则必须在外部进行同步。（结构性修改是添加或删除一个或多个映射的任何操作；仅改变映射已包含的键关联的值不是结构性修改。）**这通常通过同步某个自然封装映射的对象来完成。如果不存在这样的对象，应该使用Collections.synchronizedMap方法将映射“包装”。最好在创建时这样做，以防止意外的非同步访问映射：
Map m = Collections.synchronizedMap(new HashMap(…));
此类的所有“集合视图方法”返回的迭代器都是 fail-fast 的：如果在创建迭代器之后的任何时候，以除了迭代器自己的remove方法之外的任何方式对映射进行结构修改，迭代器将抛出ConcurrentModificationException。因此，面对并发修改，迭代器会迅速且干净地失败，而不是冒着在未来不确定时间出现任意、非确定性的行为的风险。
请注意，迭代器的快速失败行为不能被绝对保证，因为在存在非同步并发修改的情况下，一般而言无法做出任何硬性保证。快速失败迭代器会在最大努力的基础上抛出ConcurrentModificationException。因此，编写依赖此异常来保证其正确性的程序是错误的：迭代器的快速失败行为仅应用于检测bug。（换句话说，不能通过捕获异常来保证并发安全）

HashMap类中实现了Serializable接口，意味着你可以将一个HashMap实例序列化，保存到文件或通过网络发送，之后在需要的时候反序列化回来，恢复成原来的数据结构和内容。这对于需要存储或传输映射数据的场景非常有用。
需要注意的是，序列化和反序列化过程可能会引发安全风险（如对象注入攻击），因此在实现序列化时应当谨慎处理敏感信息，并考虑使用 transient 关键字来排除不需要序列化的成员变量，或实现writeObject和readObject方法以自定义序列化和反序列化逻辑，确保安全。此外，序列化ID (serialVersionUID) 的存在是为了版本控制，确保在序列化类结构变更时，能够兼容旧版本的序列化数据。

实现说明:

**该映射通常表现为一个分箱（桶装）的哈希表，但是当桶变得过大时，它们会被转换为由 TreeNode 构成的桶，这些TreeNode的结构类似于java.util.TreeMap中的节点。**大多数方法尝试使用常规桶，但在适用时会转而调用TreeNode的方法（简单地通过检查是否为节点实例）。树节点桶（即，其元素全为TreeNode的桶）主要按hashCode进行排序，但遇到hashCode相同时，若两个元素属于同一“类C实现Comparable”，则使用它们的compareTo方法进行排序。（我们通过反射保守地检查泛型类型以验证这一点——参见comparableClassFor方法）。尽管增加了树节点的复杂性，但在键具有不同哈希值或可排序的情况下，提供了最坏情况下O(log n)的操作，这是值得的。因此，在hashCode()方法返回分布不良的值，或许多键共享hashCode，但只要它们也是可比较的，性能就会优雅地降级。 （如果这两种情况都不适用，相比于不采取预防措施，我们可能在时间和空间上浪费大约两倍的资源。但已知的情况都源自用户编程实践不良，这些实践已经很慢，以至于这一点几乎没有什么区别。）
**由于TreeNodes大约是常规节点的两倍大小，我们只在桶包含足够多的节点以证明使用时（见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
更多：小于千万分之一
**树桶的根节点通常为它的第一个节点（头结点）。**然而，在某些情况下（当前仅在Iterator.remove期间），根节点可能在别处，但可以通过父链接（TreeNode.root()方法）找回。
所有适用的内部方法都接受一个哈希码作为参数（通常从公共方法提供），使它们能够在彼此调用时不重新计算用户哈希码。大多数内部方法还接受一个"tab"参数，通常为当前表，但在调整大小或转换时可能是新的或旧的。
当桶列表被树化、分割或取消树化时，我们保持它们在相同的相对访问/遍历顺序（即，Node.next字段），以更好地保持局部性，并稍微简化那些在调用iterator.remove时涉及分割和遍历的处理。
在插入时使用比较器时，为了在重新平衡过程中保持总排序（或此处所需接近的程度），我们比较类和identityHashCode 作为平局决断者。
在纯模式与树模式之间使用及转换的复杂性，受到LinkedHashMap子类存在的影响。请参阅下面定义的插入、移除和访问时调用的钩子方法，这些方法允许LinkedHashMap内部在不依赖于这些机制的情况下保持独立。（这也要求将一个映射实例传递给某些可能创建新节点的实用方法。）
并发编程风格的基于SSA（静态单赋值）的编码有助于在所有复杂的指针操作中避免别名错误。

源码解读

静态常量和内部节点类 Node

// 静态常量定义
// DEFAULT_INITIAL_CAPACITY: 默认初始容量，设置为16（即1 << 4），要求是2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// MAXIMUM_CAPACITY: 最大容量，为1 << 30，即1073741824，同样要求是2的幂且不超过这个值。
static final int MAXIMUM_CAPACITY = 1 << 30;
// DEFAULT_LOAD_FACTOR: 默认负载因子，未在构造器中指定时使用，默认值为0.75。负载因子决定了哈希表何时需要进行扩容。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// TREEIFY_THRESHOLD: 当桶（bin）中节点数量达到此阈值（8）时，该桶会从链表转换为红黑树，以提高查找效率。
static final int TREEIFY_THRESHOLD = 8;
// UNTREEIFY_THRESHOLD: 在调整大小操作期间，分裂的桶从树转换回链表的阈值，设为6。
static final int UNTREEIFY_THRESHOLD = 6;
// MIN_TREEIFY_CAPACITY: 桶可以被树化的最小表容量，理论上至少为4 * TREEIFY_THRESHOLD，即至少为32，以避免树化和扩容阈值之间的冲突。源码设置为 64 ，可能是出于性能优化和避免频繁resize操作的考虑。
static final int MIN_TREEIFY_CAPACITY = 64;/**
* 内部类Node
* Node类实现了Map.Entry接口，表示哈希表中的一个条目，包含以下部分：
* 成员变量：
* int hash: 节点关联的哈希值。
* K key: 键。
* V value: 值。
* Node<K,V> next: 指向下一个节点的引用，用于链表或树结构中的链接。
* 
* 构造函数：初始化节点的所有字段。
* getter方法：获取键(getKey)、值(getValue)。
* toString方法：返回键值对的字符串表示。
* hashCode方法：基于键和值计算哈希码，用于确定节点在哈希表中的位置。
* setValue方法：更新节点的值并返回旧值。
* equals方法：比较两个节点是否相等，基于键和值的相等性判断。
*/
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;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;}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) {V oldValue = value;value = newValue;return oldValue;}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;}
}

静态工具方法

/* ---------------- Static utilities（静态工具方法） -------------- *//*** 计算键的哈希码（通过调用key.hashCode()），并采用异或（XOR）操作将哈希码的高位散布到低位。* 由于哈希表采用二的幂次掩码来确定索引，导致仅在当前掩码高位上变化的哈希集合总是会发生碰撞。* （已知的例子包括在小表中存储连续整数的Float键集合。）* 因此，我们应用了一种变换，将高位的影响向下扩散，以改善分布。* 这里存在速度、实用性与位扩散质量之间的权衡。* 由于许多常见的哈希集合已经具有相当合理的分布（所以不需要进一步分散），* 并且我们使用树结构来处理桶内大量的碰撞情况，* 我们仅以最经济的方式对某些位进行移位和异或操作，* 以此减少系统性的哈希损失，同时确保原本因表容量限制而无法在索引计算中利用到的最高位信息也能够被融入进来。*/
// 为什么需要对原始哈希值进行额外的位操作：通过简单而高效的位移和异或，提高哈希值分布的均匀性，从而减少哈希碰撞，尤其是在处理特定类型数据或小表时，能显著提升哈希表的性能。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/*** 根据给定的目标容量返回一个2的幂次大小。* 此方法用于计算哈希表的理想容量，确保容量始终是2的幂，* 这对于高效地使用位运算进行索引计算至关重要。* 取最小的大于cap的2的整数次幂：输入30，输出32*/
static final int tableSizeFor(int cap) {// 初始化n为cap减1，这样如果cap已经是2的幂，最终结果仍会是cap。int n = cap - 1;// 下面的位操作序列用于将n的最低位设置为1，同时将紧邻的每个低位依次置为1，// 直至最高有效位。这样做是为了“向上取整”到最近的2的幂。n |= n >>> 1;  // 将n的右半部分与自身进行或操作，使得右半部分的最低位为1。n |= n >>> 2;  // 再次右移并或操作，将下一部分的最低位也置为1。n |= n >>> 4;  // 继续处理更高位，直至覆盖所有低位。n |= n >>> 8;n |= n >>> 16; // 处理最高有效位，对于32位整数而言。// 最后检查处理后的n值。// 如果n为负数（这在正常情况下不会发生，除非cap非常大，接近Integer.MAX_VALUE），// 则直接返回最小容量1。// 如果n大于最大允许容量MAXIMUM_CAPACITY（通常是2^30），则返回MAXIMUM_CAPACITY。// 否则，返回n+1，因为n此时已经是比目标容量大的最小2的幂次减1，加1后即为目标容量的最小2的幂次覆盖。return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

属性字段 Fields

/* ---------------- Fields -------------- *//*** table，在首次使用时初始化，并根据需要调整大小。当分配时，长度始终是2的幂次方。* （还容忍在某些操作中长度为零的情况，以允许目前不需要的引导机制。）*/
transient Node<K,V>[] table; // 存储键值对的哈希表数组/*** 缓存的 entrySet()。注意 AbstractMap 中的字段用于 keySet() 和 values()。*/
transient Set<Map.Entry<K,V>> entrySet;  // 缓存的 Entry 集合视图/*** 此映射中包含的键值对的数量。*/
transient int size; // map 的大小，即键值对的数量/*** 此 HashMap 结构修改的次数。* 结构性修改是指改变 HashMap 中映射数量或以其他方式修改其内部结构（例如，重新散列）的操作。* 这个字段用于使 HashMap 集合视图上的迭代器快速失败。（参见 ConcurrentModificationException）。*/
transient int modCount;/*** 下一次调整大小时的大小值（容量 * 负载因子）。** @serial*/
// （序列化时的 javadoc 描述是正确的。
// 另外，如果表格数组尚未分配，此字段保存初始数组容量，
// 或者零表示 DEFAULT_INITIAL_CAPACITY。）
int threshold; // 下一个阈值，达到这个值时将进行重新散列/*** 哈希表的负载因子。** @serial*/
final float loadFactor; // 哈希表的负载因子，决定何时进行重新散列

未完待续。。。