Java Hashtable

Hash Table是一种以$O(1)$时间复杂度实现数据查找的数据结构。本文将从数据结构、put过程、线程安全等维度，介绍Java生态中的哈希表

数据结构

虽然哈希表的基础是数组，但为了应对复杂的哈希冲突，Java（特别是 JDK 1.8+ 的 HashMap）采用了一种混合存储结构

View Mermaid diagram code

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(桶): 桶是哈希表中的一个存储单元，用于存储键值对。每个桶可以包含一个或多个节点（Node<K,V>）

术语	解释
Capacity (容量)	数组（Buckets）的长度。在 Java HashMap 中，它始终保持为$2^n$。
Load Factor (负载因子)	默认为 0.75，当元素数量达到 Capacity * 0.75 时，触发扩容。
Hash Collision (哈希冲突)	不同的 Key 计算出相同的 Index
Rehashing (再哈希/扩容)	扩容时创建两倍容量的新数组，并将旧数据重新计算位置放入新数组的过程。

put元素的过程

1. 计算哈希值：调用对象的 hashCode() 方法，计算哈希值，以 String s 为例，其哈希值计算公式为$hashCode=s[0]\ast {31}^{n-1}+s[1]\ast {31}^{n-2}+...+s[n-1]$；
2. 计算索引：按照 index = hashCode & (Capacity-1) 得出Bucket索引，若Bucket上无元素则直接放入数组槽位，否则进入冲突处理逻辑
3. 冲突处理
   1. 树节点 (TreeNode): 如果当前 Bucket 的结构已经是红黑树，则调用 putTreeVal 方法，以$O(\log n)$的复杂度插入。
   2. 链表 (LinkedList): 遍历链表到末尾插入新节点 (JDK 1.8+)
      • 树化 (Treeification): 插入后，如果链表长度达到 TREEIFY_THRESHOLD（8）且数组长度达到 MIN_TREEIFY_CAPACITY (64)，系统会将该链表转化为红黑树。

为什么阈值是 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 的三次方) 等价于右移三位

$01100100>>3=(00001100)\mathrm{\_}2=12$即为商

而01100100的后三位$(100)\mathrm{\_}2=4$即为余数

已知$n=2^m$，商为hash二进制数右移 m 位，而余数为hash的后 m 位

要求hash % n，即求hash的后 m 位，而n-1的二进制表示恰为 m 个 1，可推得hash & (n-1)等与hash % n

$$\begin{array}{rl}& 2=(10{)}_{2}2-1=(1{)}_2\\ & 4=(100{)}_{2}4-1=(11{)}_2\\ & 8=(1000{)}_{2}8-1=(111{)}_2\\ & ......\\ & \mathrm{归}\mathrm{纳}\mathrm{得}\mathrm{到}:\\ & 2^m=(1000...0{)}_2\mathrm{最}\mathrm{高}\mathrm{位}\mathrm{为}1，\mathrm{其}\mathrm{后}\mathrm{有}m\mathrm{个}\mathrm{零}\\ & 2^m-1=(111..1{)}_2\mathrm{共}\mathrm{有}m\mathrm{个}1\end{array}$$

例题验证

(n-1) & hash，不妨设hash = 45367，二进制为 0100 1010 1111 0111，求hash % 8

45367 % 8 = 45367 & 7

$$\begin{array}{rl}& 8=(1000{)}_{2}7=(111{)}_{2}hash=(0100101011110111{)}_2\\ & 45367\mathrm{\%}8=7\\ & (0100101011110111{)}_2\mathrm{\&}(0000000000000111{)}_2=(111{)}_2=7\end{array}$$

为什么 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 = 69609650index = 2index = 2hashCode % 16 == hashCode & (bucketsLen - 1) is true----------------------------------------[INPUT = 47]hashCode = 69609650index = 34index = 18hashCode % 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

算法分析：哈希表的大小为何是素数
哈希函数除数的选取为什么是质数？哈希冲突解决方法,闭散列&开散列