--- title: Java Hashtable date: 2024-01-28 tags: [Algorithm, Java, Collection] cover: https://assets.vluv.space/cover/Dev/Algorithm/hash_table.webp excerpt: "Hash Table是一种以 O(1) 时间复杂度实现数据查找的数据结构。本文将从数据结构、put过程、线程安全等维度，介绍Java生态中的哈希表" --- ## 数据结构 虽然哈希表的基础是数组，但为了应对复杂的哈希冲突，Java（特别是 JDK 1.8+ 的 `HashMap`）采用了一种混合存储结构 ```mermaid graph TD Table[Hash Table Array] --> B1[Bucket 0] Table --> B2[Bucket 1] Table --> B3[Bucket ...] Table --> Bn[Bucket n] B1 --> N1[Node K-V] N1 --> N2[Node K-V] N2 --> N3[Node K-V] B3 --> T1((TreeNode Red)) T1 --> T2((TreeNode Black)) T1 --> T3((TreeNode Black)) ``` > [!SUMMARY]- > > Bucket(桶): 桶是哈希表中的一个存储单元，用于存储键值对。每个桶可以包含一个或多个节点（`{java} Node`） > > | 术语 | 解释 | > | ----------------------------- | ------------------------------------------------------------ | > | **Capacity (容量)** | 数组（Buckets）的长度。在 Java `HashMap` 中，它始终保持为 $2^n$。 | > | **Load Factor (负载因子)** | 默认为 `0.75`，当元素数量达到 `Capacity * 0.75` 时，触发扩容。 | > | **Hash Collision (哈希冲突)** | 不同的 Key 计算出相同的 Index | > | **Rehashing (再哈希/扩容)** | 扩容时创建两倍容量的新数组，并将旧数据重新计算位置放入新数组的过程。 | ## put元素的过程 1. **计算哈希值**：调用对象的 `{java} hashCode()` 方法，计算哈希值，以 `String s` 为例，其哈希值计算公式为 $hashCode = s[0]*31^{n-1} + s[1]*31^{n-2} + ... + s[n-1]$； 2. **计算索引**：按照 `{java} index = hashCode & (Capacity-1)` 得出Bucket索引，若Bucket上无元素则直接放入数组槽位，否则进入冲突处理逻辑 3. **冲突处理** 1. **树节点 (TreeNode)**: 如果当前 Bucket 的结构已经是红黑树，则调用 `putTreeVal` 方法，以 $O(\log n)$ 的复杂度插入。 2. **链表 (LinkedList)**: 遍历链表到末尾插入新节点 (JDK 1.8+) - **树化 (Treeification)**: 插入后，如果链表长度达到 `{java} TREEIFY_THRESHOLD`（8）且数组长度达到 `{java} MIN_TREEIFY_CAPACITY` (64)，系统会将该链表转化为红黑树。 > [!QUESTION]- 为什么阈值是 8 和 64？ > > 回答由Gemini生成 > > 在 JDK 1.8 的源码中，树化的触发条件有两个硬性规定： > 1. **链表长度达到 8** (`TREEIFY_THRESHOLD`) > 2. **数组容量达到 64** (`MIN_TREEIFY_CAPACITY`) > > 如果只满足条件 1 而不满足条件 2，HashMap 会优先选择 **扩容 (resize)** 而不是树化。为什么要设置这两道关卡？ > > #### 1. 为什么优先扩容 (Capacity < 64)？ > **本质原因：治标不如治本。** > > 当数组容量很小（例如 16 或 32）时，出现长链表通常是因为 **桶（Bucket）太少**，导致哈希碰撞概率激增。此时，扩容是更优的选择： > * **扩容效果**: 数组扩大一倍，原链表中的节点会根据 Hash 值的高位重新分配，大概率会被拆分到两个不同的 Bucket 中，链表长度自然缩短。 > * **代价对比**: 维护一颗红黑树的各种左旋、右旋、着色操作，比单纯的数组扩容和链表拆分要复杂得多。 > > 因此，在数组较小时，**扩容是解决冲突的首选方案**。只有当数组已经足够大（>=64），再扩容成本过高且无法有效分散冲突时，才启用红黑树作为“兜底”方案。 > > #### 2. 为什么链表阈值是 8？ > > 这涉及到两个层面的考量：**空间成本** 和 **统计学概率**。 > > **A. 空间与时间的权衡 (Space/Time Trade-off)** > * **TreeNode** (红黑树节点) 的大小大约是 **Node** (链表节点) 的 **2 倍**。 > * 当链表很短时，遍历查找的速度非常快，转化为红黑树带来的性能提升不足以抵消其构建和内存成本。 > * 只有当链表足够长，$O(n)$ 的查找效率变得无法接受时，牺牲空间换取 $O(\log n)$ 的时间才是有意义的。 > > **B. 泊松分布 (Poisson Distribution)** > 这是最核心的数学依据。HashMap 的源码注释中明确解释了这一点： > > > In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution... > > 如果 Hash 函数设计得当，Key 的分布应该符合 **泊松分布**。在负载因子为 0.75 的情况下，一个 Bucket 中出现不同节点数量的概率如下： > > | 节点数量 (k) | 出现概率 (Probability) | > | :--- | :--- | > | 0 | 0.60653066 | > | 1 | 0.30326533 | > | 2 | 0.07581633 | > | ... | ... | > | **8** | **0.00000006** | > > **结论**：在正常情况下，链表长度达到 8 的概率不到 **千万分之一**。 > 如果真的达到了 8，说明发生了严重的哈希冲突（可能是 Hash 算法极差，或者是遭到了 Hash DoS 攻击）。此时，HashMap 为了保证系统不被卡死，被迫将链表转为红黑树。**8 是一个统计学上的“不可能事件”边界。** > > #### 3. 为什么退化阈值是 6 (`UNTREEIFY_THRESHOLD`)？ > 当红黑树中的节点因为删除操作减少到 6 时，会退化回链表。为什么不是 7？ > > **原因：避免“颠簸” (Thrashing)。** > 如果树化阈值是 8，退化阈值是 7。那么当通过 `put` 变成 8（转树），紧接着 `remove` 变成 7（转链表），再 `put` 变成 8... > 频繁的结构转换会极其消耗 CPU 资源。中间留出 2 个节点的缓冲空间（8 -> 6），可以有效防止这种临界区的性能震荡。 > ### Hashtable 快速取模方案 #### 证明 对于二进制的位运算，整除 8(2 的三次方) 等价于右移三位 $0110 0100 >> 3 = (0000 1100)\_2 = 12$ 即为商 而`01100100`的后三位$(100)\_2 = 4$即为余数 已知$n = 2^m$，商为`hash`二进制数右移 m 位，而余数为`hash`的后 m 位 要求`hash % n`，即求`hash`的后 m 位，而`n-1`的二进制表示恰为 m 个 1，可推得`hash & (n-1)`等与`hash % n` $$ \begin{align} \nonumber & 2 = (10)_2 \quad 2 -1 = (1)_2 \\ & 4 = (100)_2 \quad 4 -1 = (11)_2 \\ & 8 = (1000)_2 \quad 8 - 1 = (111)_2 \\ & ...... \\ &归纳得到:\\ & 2^m = (1000...0)_2 最高位为1，其后有m个零\\ & 2^m-1 = (111..1)_2 共有m个1 \end{align} $$ **例题验证** `(n-1) & hash`，不妨设`hash` = 45367，二进制为 0100 1010 1111 0111，求`hash % 8` `45367 % 8 = 45367 & 7` $$ \begin{align} &8 = (1000)_2 \quad7 = (111)_2 \quad hash = \ (0100\ 1010\ 1111\ 0111)_2 \\ &45367 \ \%\ 8 = 7 \\ &(0100 1010 1111 0111)_2 \ \&\ (0000\ 0000\ 0000\ \ 0111)_2 = (111)_2 = 7 \end{align} $$ #### 为什么 java 中哈希表的大小是 2 的幂次方? #### 代码验证 在 JDK 中,`Hashtable`求模的方式为 `hash & (n-1)`,这种方式的前提是 n 为 2 的幂次方,其他情况下未必成立. ```java public class HashTable { public static void main(String[] args) { int bucketsLen = new Scanner(System.in).nextInt(); int hashCode = new String("Hello").hashCode(); System.out.println("hashCode = " + hashCode); int index = hashCode & (bucketsLen - 1); System.out.println("index = " + index); index = hashCode % bucketsLen; System.out.println("index = " + index); String isEqual = (hashCode % bucketsLen) == (hashCode & (bucketsLen - 1)) ? "true" : "false"; System.out.println("hashCode % bucketLen == hashCode & (bucketsLen - 1) is " + isEqual); } } ``` ```powershell [INPUT = 16] [OUTPUT] hashCode = 69609650 index = 2 index = 2 hashCode % 16 == hashCode & (bucketsLen - 1) is true ---------------------------------------- [INPUT = 47] hashCode = 69609650 index = 34 index = 18 hashCode % bucketLen == hashCode & (bucketsLen - 1) is false ``` ## Hashtable vs HashMap vs ConcurrentHashMap | 术语 | 解释 | | ----------------------------- | ---------------------------------------------------------------------------------- | | **Capacity (容量)** | 数组（Buckets）的长度。在 Java `HashMap` 中，它始终保持为 $2^n$。 | | **Load Factor (负载因子)** | 衡量哈希表的拥挤程度，默认为 `0.75`。即当元素数量达到 `容量 * 0.75` 时，触发扩容。 | | **Hash Collision (哈希冲突)** | 不同的 Key 计算出相同的 Index。这是哈希表必须处理的核心问题。 | | **Rehashing (再哈希/扩容)** | 当数组不够用时，创建一个两倍大小的新数组，并将旧数据重新计算位置放入新数组的过程。 | ## Ref [算法分析：哈希表的大小为何是素数](https://blog.csdn.net/zhishengqianjun/article/details/79087525) [哈希函数除数的选取为什么是质数？哈希冲突解决方法,闭散列&开散列](https://blog.csdn.net/lovehang99/article/details/101997405)