理想哈希码的特性

一个设计良好的hashCode方法应当具备以下特性：

• 确定性：同一个对象多次调用，返回值必须一致（前提是对象状态不变）。

• 高效率：计算过程不能过于复杂，否则会成为性能瓶颈。

• 均匀性：对于不同的对象（尤其是逻辑上可能相近的对象），产生的哈希码应尽可能均匀地分布在

  int

  范围内，以减少哈希碰撞，提升哈希表性能。

2.2

常见实现策略

2.2.1

手工组合字段

最经典的手工实现方式是：为每个关键字段（参与equals比较的字段）计算一个哈希码，然后按照一定规则组合起来。

Effective

Java

一书中推荐了一种算法：

java

public
class
作为乘数，其优势在于：
31
是一个不大不小的素数，在乘法运算中不容易产生溢出（尽管溢出是允许的），且能产生较好的分布。
31
==
会自动进行这种优化。
2.2.2
Objects.hash
开始，java.util.Objects类提供了静态方法hash(Object...
values)，可以方便地组合多个字段的哈希码：
java
@Override
public
}
Objects.hash内部实际上也是采用类似的手工组合方式，它会创建一个数组来接收可变参数，因此会有一定的性能开销（数组创建和装箱）。
在性能敏感的代码中，建议手工实现。
2.2.3
Lombok
等工具
通过注解@EqualsAndHashCode，Lombok
可以在编译期自动生成高质量的hashCode和equals方法，大大简化开发。
生成的代码通常也是基于字段组合的方式，并考虑了继承关系。
2.3
为什么选择
31：
java
public
int
的原因主要有两点：
性能：31
<<
上比乘法快很多。
虽然现代处理器乘法速度已经很快，但这种习惯依然保留。
分布：31
是一个奇素数，使用素数作为乘数可以减少哈希碰撞。
如果乘数是偶数，并且乘法溢出，信息会丢失（因为乘以
相当于移位，低位补
的乘法结果在二进制表示上具有良好的混合效果。
2.4
常见误区
误用随机数：有些开发者试图使用Random或ThreadLocalRandom生成哈希码，这完全违背了“确定性”原则，会导致哈希表行为异常。
忽略
null
的引用类型做处理，否则会抛出NullPointerException。
可以用0作为
null
的哈希码，或者使用Objects.hashCode(obj)。
使用数组字段：数组的默认hashCode是基于身份标识的，而不是内容。
如果字段是数组，应使用Arrays.hashCode()来计算其内容哈希码。
忘记排除非关键字段：只应使用参与equals比较的字段来计算哈希码，否则会导致两个逻辑相等的对象产生不同的哈希码。
/>
第三章：哈希算法基础理论
3.1
Function）是一种将任意长度的输入（称为预映射，pre-image）通过某种算法压缩映射为固定长度输出（称为哈希值）的函数。
其数学形式为：
text
h
=
是生成的哈希值。
哈希函数在计算机科学中有广泛的应用，包括数据校验、密码学、数据结构（哈希表）等。
3.2
理想哈希函数的特性
对于用于哈希表的哈希函数（非密码学用途），我们通常关注以下特性：
确定性：相同的输入必须产生相同的输出。
高效性：计算速度要快，不能成为系统瓶颈。
均匀性：输出值应尽可能均匀地分布在值域空间中，避免聚集。
雪崩效应：输入的微小变化应导致输出发生巨大变化，即输出位应以约
50%
的概率翻转。
最小碰撞：不同输入产生相同输出的概率应尽可能低。
3.3
常见哈希算法分类
非加密哈希：如
Java
的hashCode、MurmurHash、CityHash、xxHash
等。
它们追求速度和均匀分布，不要求抗碰撞攻击（即不要求难以人为制造碰撞）。
加密哈希：如
MD5、SHA-1、SHA-256
等。
除了均匀性，还必须具备单向性、抗弱碰撞性、抗强碰撞性等安全特性。
由于计算复杂，不适合作为哈希表的哈希函数。
3.4
Table）是一种根据键直接访问内存存储位置的数据结构。
它通过哈希函数将键映射到数组的某个索引，从而实现快速访问。
基本操作：
插入：计算键的哈希值，得到数组下标，将键值对存入该位置。
查找：计算键的哈希值，得到数组下标，直接取出该位置的值。
删除：类似查找，删除对应位置的元素。
3.4.1
哈希冲突
由于数组空间有限，而可能的键无限，不同的键可能映射到同一个数组下标，这称为哈希冲突（Hash
Collision）。
解决冲突的常见方法有：
链地址法（Separate
Chaining）：数组的每个元素是一个链表（或红黑树）的头节点，冲突的元素链接在同一个桶中。
Java
的HashMap采用此方法。
开放地址法（Open
Addressing）：当冲突发生时，通过探查序列寻找下一个空闲位置。
例如线性探测、二次探测、双重哈希。
ThreadLocalMap使用线性探测。
再哈希法：准备多个哈希函数，冲突时换另一个函数计算。
建立公共溢出区：将冲突的元素统一放到一个公共区域。
3.4.2
Factor）
桶数组长度。
它衡量了哈希表的装满程度。
负载因子越大，空间利用率越高，但冲突概率也越大，导致操作时间增加；负载因子越小，空间浪费越多，但冲突少，操作快。
HashMap默认负载因子
0.75，被认为是时间与空间的折中。
hashCode
类重写了hashCode方法，其算法是：
text
s[0]*31^(n-1)
+
s[n-1]
其中s[i]是字符串的第
个字符，n
是字符串长度，^表示乘幂。
String
内部缓存了计算好的哈希码（字段hash），第一次计算后便存储起来，后续调用直接返回缓存值，提高了性能。
注意：String
的哈希码算法虽然简单高效，但存在已知的碰撞风险，例如
"Aa"
值组合导致的巧合）。
但这对于大多数应用场景是可以接受的。
4.2
hashCode
Integer：直接返回其
int
值。
Long：返回(int)(value
(value
位异或，将高位信息混合到低位。
Boolean：返回true
1231
1237（这两个质数是随意选择的，只要不同即可）。
Byte/Short/Character：直接返回数值的
int
Object，默认hashCode是基于身份标识的，不反映内容。
若需基于内容计算，应使用Arrays.hashCode()或Arrays.deepHashCode()（针对多维数组）。
这些方法会遍历数组元素，递归调用各元素的hashCode，并按类似
hashCode
IDEA）自动生成hashCode和equals。
这些生成的代码通常质量很高，并提供了多种模板选择。
此外，Google
Guava
库也提供了Objects.hashCode的变体MoreObjects.hashCode等工具。
HashMap
及以后，HashMap由数组
+
红黑树组成。
当链表长度超过阈值（默认
8）且数组长度不小于
时，链表会转换为红黑树，以优化极端情况下的查找性能。
5.2
扰动函数：hash()
HashMap
并不是直接使用键的hashCode()作为哈希值，而是先经过一个扰动函数处理：
java
static
final
}
这段代码将键的hashCode的高
位与低
位进行异或，目的是混合高位和低位的信息，因为后续计算下标时只用到低几位（基于数组长度减一的与运算），如果不进行扰动，高位信息就会丢失，增加碰撞概率。
通过右移
位异或，让高位也参与低位运算，使哈希值分布更均匀。
5.3
下标计算：index
hash
当我们确定了哈希值hash后，需要将其映射到数组下标。
HashMap
采用(n
1，因此&操作只保留hash的低位，相当于取模。
5.4
的幂？
位运算替代取模：(n
&
n。
均匀分布：如果
1，导致某些位永远不会被使用，增加碰撞。
扩容方便：扩容时，元素在新数组中的位置要么在原索引，要么在原索引
+
旧容量，这得益于长度翻倍的设计。
具体判断是：(hash
&
扩容机制
当HashMap中的元素数量超过threshold（负载因子
容量）时，会触发扩容。
扩容过程：
创建一个新数组，大小为原数组的两倍。
遍历旧数组的每个桶，重新计算每个元素在新数组中的位置。
对于链表中的元素，根据hash
&
oldCap分为“低位”和“高位”两个链表，分别插入新数组的原索引位置和原索引+旧容量位置。
这样可以避免重新计算每个元素的哈希值（因为哈希值没变，只是利用了容量翻倍的特点）。
5.6
之前，HashMap仅使用链表处理冲突。
当哈希冲突严重时，链表会变得很长，查找时间复杂度退化为
且数组长度至少为
时，链表转为红黑树，查找复杂度降为
O(log
时，又会退化回链表，以避免频繁转换的开销。
为什么阈值是
8？这是基于统计学的泊松分布得出的结论，在理想随机哈希码下，链表长度达到
0.00000006），因此可以认为
是一个安全阈值，既保证了树化的必要性，又避免了过早树化带来的额外开销。
/>
第六章：哈希冲突的解决策略
6.1
链地址法（Separate
Chaining）
这是HashMap采用的方法。
每个数组元素是一个桶，桶内可以是一个链表（或红黑树）。
插入时，如果桶为空，直接放入；否则，将新节点加入链表尾部（或树中）。
查找时，先定位桶，再遍历桶内元素，通过equals找到匹配的键。
优点：实现简单，对哈希函数要求相对较低，删除操作方便。
/>缺点：需要额外的链表指针内存，极端情况下链表过长时性能下降。
6.2
开放地址法（Open
Addressing）
所有元素都存储在数组中，当冲突发生时，按照某种规则寻找下一个空闲位置。
常见探测方法：
线性探测：(hash
+
递增。
二次探测：(hash
+
m，避免线性探测的“一次聚集”。
双重哈希：(hash
+
m，使用第二个哈希函数作为步长。
Java
中的ThreadLocalMap使用线性探测解决冲突。
开放地址法的优点是内存紧凑，无需指针，但删除操作复杂，且容易产生聚集现象。
6.3
再哈希法
准备多个哈希函数，当第一个函数冲突时，使用第二个，直到找到空位。
这种方法不易产生聚集，但增加了计算时间。
6.4
公共溢出区
将冲突的元素统一放入一个公共溢出区。
查找时先查哈希表，若未找到再到溢出区查找。
适用于冲突较少的情况。
/>
第七章：性能考量与最佳实践
7.1
hashCode
分布不均匀的影响
如果大量对象的hashCode返回相同或相近的值，会导致哈希表发生严重碰撞。
例如，所有对象的哈希码都是
0，那么它们都会落入同一个桶，HashMap就退化成了链表（或红黑树），插入和查找的时间复杂度从
O(1)
O(n)。
因此，设计一个分布良好的hashCode至关重要。
7.2
String、Integer），缓存哈希码可以避免重复计算。
String
类就缓存了哈希值。
自定义不可变类也可以考虑缓存，但需要注意线程安全（使用
volatile
使用不可变对象作为键
HashMap的键应该是不可变的，或者至少保证哈希码不会改变。
如果键对象的状态改变导致哈希码变化，那么它原本在哈希表中的位置就找不到了，造成内存泄漏。
因此，常用的键类型如
String、Integer
选择合适的初始容量和负载因子
如果能预估HashMap将要存储的元素数量，可以在构造时指定初始容量，避免频繁扩容带来的性能损耗。
例如，期望存储
1000
2048）。
负载因子的选择需要权衡时间与空间。
如果对时间敏感，可以降低负载因子（如
0.5），但会浪费更多空间；如果内存紧张，可以适当提高（如
0.8），但要承受更高的碰撞风险。
7.5
hashCode
如果在hashCode中使用了可变字段，那么当对象存入集合后修改了该字段，哈希码就会改变，导致对象无法被找到。
因此，参与hashCode的字段最好是
final
/>
第八章：常见问题深度解析
8.1
为什么重写
hashCode？
这是由哈希表的契约决定的。
当一个对象作为键存入HashMap时，首先根据哈希码定位桶，然后在桶内用equals查找匹配。
如果两个对象逻辑相等（equals返回
true）但哈希码不同，它们会被放入不同桶，导致无法用其中一个找到另一个。
这违反了哈希表的基本工作方式。
因此，规范要求：equals相等则哈希码必须相等。
8.2
hashCode
0，会导致它们全部落入同一个桶，造成严重碰撞。
所以应该尽量避免，除非对象本身的设计导致其自然哈希值就是
能否使用随机数作为
hashCode？
绝对不能。
随机数违反了“一致性”要求，同一个对象两次调用可能返回不同值，导致哈希表完全失效。
此外，即使每次对象创建时随机生成并保持不变（即随机种子固定），也不能保证相等的对象（equals为
true）具有相同的随机数，这仍然违反契约。
8.4
hashCode
可能为负数吗？
可以。
hashCode返回的是
int
2^31-1，完全可能为负数。
在HashMap计算下标时，会通过扰动和与运算转换为正数下标，所以负数没有影响。
8.5
为什么
的幂？
前文已解释，主要是为了用位运算代替取模，以及扩容时的优化。
但需要注意的是，如果你在构造HashMap时传入的初始容量不是
的幂，HashMap内部会将其转换为大于等于该值的最小
String
节解释：性能（移位减）和分布（奇素数）。
8.7
如何理解
的“均匀分布”？
均匀分布意味着对于任意一组对象，它们的哈希码映射到数组下标后，各个桶中的元素数量大致相当。
这可以降低平均查找长度。
理论上，如果哈希码是真正的随机数，那么均匀性最好。
但在实际中，我们可以通过精心设计的哈希函数和扰动来接近这一目标。
8.8
6？
如前所述，基于泊松分布的概率计算，链表长度达到
是为了避免频繁地在树和链表之间转换：如果某桶元素在
之间波动，阈值
会导致反复转换，开销很大，所以留出
/>
第九章：进阶话题——一致性哈希
9.1
分布式系统中的哈希需求
在分布式缓存（如
Redis
集群）、负载均衡等场景中，我们通常需要将数据（或请求）映射到一组节点上。
最简单的做法是取模：hash(key)
N。
但这种方式在节点数量变化时（如扩缩容），绝大多数映射关系都会改变，导致大量缓存失效或数据迁移，称为“哈希雪崩”。
9.2
一致性哈希原理
一致性哈希（Consistent
Hashing）通过将哈希值空间组织成一个虚拟的圆环（0
2^32-1），然后将节点也映射到环上。
每个数据根据其哈希值定位到环上的某个位置，然后沿顺时针方向找到第一个节点，作为该数据所属的节点。
当节点增加或删除时，只有环上该节点附近的少量数据需要重新映射，大大减少了影响范围。
为了进一步提高均衡性，一致性哈希通常引入“虚拟节点”的概念，即每个物理节点对应多个虚拟节点，使它们在环上分布更均匀。
9.3
一致性哈希在
Jedis、Redisson）支持一致性哈希。
也可以自己实现，例如使用
Guava
的Hashing类提供的consistentHash方法：
java
int
bucket
Hashing.consistentHash(keyHash,
numberOfBuckets);
该方法基于
JDK
的Object.hashCode实现了一个高效的一致性哈希算法。
/>
第十章：哈希算法的安全考量
10.1
哈希碰撞攻击
如果攻击者能够构造大量哈希值相同但内容不同的对象，并将它们注入到HashMap中，就会导致哈希表退化成链表，造成服务器
CPU
飙升，甚至引发拒绝服务（DoS）攻击。
历史上，Java
的String.hashCode曾被用于此类攻击，因为可以轻易构造出哈希值相同的字符串。
10.2
Java
的应对措施
扰动函数：HashMap的hash()方法混合高位，增加攻击者预测桶位置的难度。
红黑树：即使发生碰撞，链表长度达到阈值后转为红黑树，保证最坏情况下的性能。
随机化哈希种子：在
Java
中引入了-Djdk.map.althashing.threshold参数，允许在
JVM
后被移除了，因为红黑树已经有效缓解了问题。
使用ConcurrentHashMap：ConcurrentHashMap在设计时也考虑了安全性，但其主要目标是并发。
对于需要更高安全性的场景，可以使用加密哈希（如
SHA-256）作为键的哈希函数，但性能会大幅下降。
也可以使用专门为抗碰撞设计的哈希算法，如
Java
的改进
Optional类的hashCode：与容器类类似，根据包含值的hashCode计算。
Records：Java
Record
类型自动生成equals、hashCode和toString，基于所有组件字段。
HashMap内部优化：持续的性能微调，如红黑树相关逻辑的优化。
11.2
未来展望
随着硬件发展，哈希算法可能会利用新的指令集（如
AVX-512）加速。
同时，在量子计算背景下，密码学哈希面临挑战，但对于非加密哈希影响不大。
Java
工程师，深入理解hashCode和哈希算法不仅是面试需要，更是写出高效、健壮代码的基础。
本文从概念、契约、实现、原理到最佳实践，全方位剖析了这一主题。
以下是核心要点回顾：
hashCode
是对象在哈希表中的身份证，必须与
equals
保持一致。
编写高质量
null
处理和数组。
哈希算法追求均匀、高效，HashMap
的幂容量、链地址+红黑树来平衡性能。
HashMap
源码是学习哈希算法的经典案例，理解其
hash()、resize()、树化等机制至关重要。
性能优化：选择合适初始容量和负载因子，使用不可变键，缓存哈希码。
分布式扩展：一致性哈希解决了节点变化时的映射动荡问题。
安全考量：哈希碰撞攻击不容忽视，Java
已有多种防御手段。