Hash

equals 和 hashCode 的约定 Java 规定了 hashCode() 和 equals() 之间的约定： 两个对象用 equals() 判断相等，则它们的 hashCode() 必须相等。 反过来不成立：hashCode() 相等的两个对象，equals() 未必相等（也就是哈希冲突）。 自定义 hashCode() 时必须遵守第 1 条，否则这个对象放进 HashMap、HashSet 之类基于哈希的容器后会出现"明明 equals 相等却查不到"的 bug。第 2 条则说明哈希冲突是被允许的，容器内部（开链法或开放地址法）本来就要处理冲突，具体见 开链法与开放地址法。 Object 默认的 hashCode 是怎么算的 没有重写 hashCode() 的类，用的是 Object 的默认实现，也叫 identity hash code（身份哈希码）。一个常见的误解是"默认哈希值就是对象的内存地址"——这在 HotSpot JVM 里并不准确： 对象在 GC（尤其是分代 GC 的 minor GC）过程中会被移动到不同的内存区域，如果哈希值直接绑定内存地址，对象移动后哈希值就变了，这会破坏"同一个对象的 hashCode 在生命周期内不能变"的规定。 所以 HotSpot 实际上是单独生成、缓存一个哈希值（存在对象头里），和地址无关。生成算法由 JVM 参数 -XX:hashCode=N 控制，N 有 0~6 几种取值，比如 0 是全局的 Park-Miller 随机数生成器，1 是基于地址计算，4 是直接用地址，其余是自增计数器等方案；默认值是 5，用的是 Marsaglia’s xorshift 算法，基于每个线程私有的状态做一次异或位移运算生成伪随机数，和地址、和对象内容都无关。 也就是说，默认的 hashCode() 本质上是一个和对象绑定的伪随机数，只是为了效率碰巧可能和地址相关的实现（-XX:hashCode=1/4）也存在，但不是默认策略。 ...

Swiss Table 是什么 Swiss Table 是 Google 在 2017 年前后公开的一种高性能哈希表设计（最早用在 Abseil 库的 absl::flat_hash_map 里），本质上是开放地址法的一个工程变体：在经典的线性探测 / 二次探测之上，加入了按"组"批量比较的机制，充分利用 CPU 的 SIMD 指令与缓存局部性。基本的开链法、开放地址法概念见 开链法与开放地址法。 它已经被多个主流项目采纳：Rust 的 hashbrown（std::collections::HashMap 自 1.36 起的底层实现）就是 Google SwissTable 的 Rust 移植版；Go 1.24 内置的 map 也从桶+溢出桶的实现换成了基于 Swiss Table 思路的新实现（细节见 开链法与开放地址法#在-go-语言中的应用）。 核心设计 控制字节（control byte） Swiss Table 给每个槽位（slot）配一个额外的 1 字节"控制字节"，不存实际数据，只存槽位的状态和一段哈希指纹： 槽位状态：EMPTY（从未用过）、DELETED（曾经用过、已删除，即墓碑标记）、FULL（当前有效数据）。 如果槽位是 FULL，控制字节里还会存一段哈希指纹，Abseil 里称为 h2，取的是 key 完整哈希值的低 7 位。 h1 和 h2：哈希值一分为二 Swiss Table 把 key 的哈希值拆成两部分： h1：哈希值的剩余高位，用来计算这个 key 应该落在哪一个"组"（group），即决定探测起点，作用类似前文开放地址法里的 root = hash(key) % m。 h2：哈希值的低 7 位，存进控制字节，作为一个廉价的"预筛选"指纹。 分组批量比较 控制字节在内存中是连续排列的，按组打包（Abseil/hashbrown 里一组 16 个，Go 1.24 里一组 8 个，打包进一个 64 位控制字）。查找时： ...

开链法与开放地址法，Separate Chaining and Open Addressing 哈希表在插入元素时，如果两个不同的 key 计算出的哈希值落到了数组的同一个位置，就发生了哈希冲突（hash collision）。解决哈希冲突主要有两种思路：开链法（Separate Chaining）和开放地址法（Open Addressing）。Java 的 HashMap 用的是开链法；Python 的 dict 用的是开放地址法。Java 里也有用开放地址法的例子，比如 IdentityHashMap 和 ThreadLocal.ThreadLocalMap，详见后文「在 Java 中的应用」一节。 开链法，Separate Chaining 开链法是一种二维结构：第一维是一个数组，数组的每个槽位（bucket）挂着一个链表（第二维）。插入元素时，先用 hash 函数算出该 key 应该落在数组的哪个槽位，然后直接把这个 key（连同 value）作为一个节点追加到该槽位的链表上。 当多个不同的 key 计算出相同的槽位时，它们并不会互相覆盖或者被挪到别处，而是全部挂在同一个槽位的链表里，按顺序排列。查找时，先定位到槽位，然后遍历该槽位的链表，逐个比较 key 是否相等，直到找到目标或者遍历到链表末尾。 优点 实现简单，冲突处理直观，槽位之间互不影响。 删除操作非常简单，只需要从链表中把对应节点摘除即可，不会影响其它元素的查找路径。 负载因子（元素个数 / 数组长度）可以大于 1，只是链表会变长，查找退化为线性扫描。 负载因子，Load Factor 负载因子的英文是 load factor，公式为 load factor = 哈希表中总元素个数 / 数组长度（槽位数）。这里的"元素个数"指的是整个哈希表中的元素总数，而不是某一个槽位对应的元素个数；某个槽位挂了多少个元素（链表长度）反映的是 hash 分布是否均匀，是另一个维度的问题。例如数组长度为 16，哈希表中一共存了 12 个元素，此时 load factor 就是 0.75。 开链法下即使 load factor 大于 1（元素个数超过数组长度）也不会出错，只是链表会变长；而开放地址法由于只有一个数组，load factor 不能超过 1（数组会满）。 ...