1. 引言
HashMap 是一种强大的数据结构，在需要快速查找的场景中应用广泛。但如果不注意细节，它的性能可能并不理想。
本篇文章将带你了解如何让 HashMap 的性能达到最优。
2. HashMap 的性能瓶颈
✅ HashMap 元素查找的时间复杂度为常数级别（O(1)），这得益于哈希函数的强大能力。
对于每个元素，HashMap 都会计算其哈希值，并将该元素放入与该哈希值对应的桶中。由于不同的对象可能具有相同的哈希值（即哈希冲突），桶的大小可能会增长。
⚠️ 桶本质上是一个链表。虽然链表查找效率不高（O(n)），但如果链表很短，问题不大。一旦出现大量哈希冲突，就会导致少数几个桶变得非常大，严重影响性能。
❌ 在最坏的情况下，所有元素都落入同一个桶中，此时 HashMap 就退化成了链表。 查找时间复杂度从 O(1) 直接降级为 O(n)，性能急剧下降。
3. 使用红黑树替代链表
从 Java 8 开始，HashMap 引入了一个内置优化：当桶中的链表长度超过一定阈值时，会自动转换为红黑树。
这使得最坏情况下的查找时间复杂度从 O(n) 降低到 O(log n)，性能提升明显。
⚠️ 但要注意：要使这个优化生效，HashMap 的键必须实现 Comparable 接口。
虽然这是个自动优化机制，但仍有不足之处：
- O(log n) 还是不如理想的 O(1)
- 构造和维护红黑树需要额外的计算资源和内存
4. 编写高质量的 hashCode 方法
设计哈希函数时，需关注两个关键因素：
- 哈希码的质量（即分布是否均匀）
- 哈希算法的执行速度
4.1. 衡量 hashCode 质量的标准
由于哈希值存储在 int 类型变量中，因此哈希值的数量是有限的。这也意味着，在不发生冲突的前提下，HashMap 能容纳的键数量是有限的。
✅ 为了尽可能避免哈希冲突，我们需要让哈希值分布尽可能均匀。 也就是说，每个哈希值出现的概率应该大致相同。
❌ 如果 hashCode 方法质量差，哈希值分布不均，甚至可能始终返回同一个值，这会导致严重的性能问题。
4.2. Object 默认的 hashCode 实现
一般不建议使用 Object 类默认的 hashCode 方法，因为通常我们不希望在 equals 方法中使用对象的引用地址进行比较（即对象身份）。
⚠️ 除非你确实需要以对象身份作为键，否则应提供自定义的 hashCode 实现。
4.3. 自定义 hashCode 实现
通常我们在重写 equals 方法时，也必须重写 hashCode 方法。
简单场景：对象身份仅由一个 id 决定
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberWithId that = (MemberWithId) o;
return id.equals(that.id);
}
@Override
public int hashCode() {
return id;
}
✅ 这种方式非常高效，且不会产生哈希冲突。此时，HashMap 的行为几乎等同于使用 int 作为键。
复杂场景：多个字段参与比较
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MemberWithIdAndName that = (MemberWithIdAndName) o;
if (!id.equals(that.id)) return false;
return name != null ? name.equals(that.name) : that.name == null;
}
此时，我们需要将多个字段的哈希值组合起来：
@Override
public int hashCode() {
int result = id.hashCode();
result = PRIME * result + (name != null ? name.hashCode() : 0);
return result;
}
其中，PRIME 是一个精心挑选的质数。历史上最常用的是 31，原因如下：
- 是质数，有助于均匀分布
- 数值较小，便于优化
- 可通过位运算优化乘法操作：
31 * i == (i << 5) - i
✅ 现代 JVM 会自动进行此类优化，因此我们无需手动写位运算来“炫技”。
当然，也可以使用更大的质数，比如 524287：
524287 * i == i << 19 - i
可能带来更好的分布效果，减少冲突概率。
4.4. 使用 Objects.hash() 工具方法
上述算法非常经典，Java 提供了 Objects.hash() 方法供我们直接使用：
@Override
public int hashCode() {
return Objects.hash(id, name);
}
✅ 内部实现正是我们前面提到的算法，乘数为 31。
4.5. 使用更高质量的哈希函数
如果你对哈希质量有极高要求，而对性能不敏感，可以考虑使用 Guava 库提供的 Hashing 工具类：
@Override
public int hashCode() {
HashFunction hashFunction = Hashing.murmur3_32();
return hashFunction.newHasher()
.putInt(id)
.putString(name, Charsets.UTF_8)
.hash().hashCode();
}
⚠️ 注意选择 32 位的哈希函数，因为 HashMap 无法存储更长的哈希值。
5. 总结
Java 中的 HashMap 是一个功能强大、高度优化的数据结构。但其性能表现，很大程度上取决于键对象的 hashCode 实现是否合理。
在本文中，我们探讨了如何编写高效、低冲突的哈希函数，从而让 HashMap 达到最佳性能。
📌 本文所有代码示例均可在 GitHub 上获取。