如何设计哈希函数呢

设计哈希函数的核心目标是：把任意长度的输入，快速、均匀地映射到一个固定范围的整数（通常是 0～N-1），同时尽量避免冲突（collision）。下面从设计原则 → 常见方法 → 实战示例 → 常见坑系统讲一下。

一、哈希函数设计的基本原则

1️⃣ 确定性

同一个输入，必须永远得到同一个哈希值
否则哈希表、缓存、签名都会失效。

2️⃣ 高效性

计算要快
理想情况：O(1) 或 O(输入长度)，不能太复杂。

3️⃣ 均匀性（最重要）

输出值应尽量均匀分布
否则会导致：

• 哈希冲突增多
• 哈希表退化成链表

✅ 好的哈希函数 = 让数据“看起来像随机数”

4️⃣ 雪崩效应（Avalanche Effect）

输入哪怕改 1 个 bit，输出也要尽量不同
这能防止“相似输入聚集在一起”。

5️⃣ 抗冲突（视场景而定）

• 普通哈希表：不要求加密级
• 安全场景（签名、区块链）：需要抗碰撞（如 SHA-256）

二、通用哈希函数设计方法

✅ 方法一：除法哈希（最简单）

hash(key) = key mod N

✅ 适合：

• 整数 key
• N 是质数时效果更好

❌ 缺点：

• 分布不均匀（如果 key 有规律）

✅ 方法二：乘法哈希（更均匀）

hash(key) = floor( N * ( (key * A) mod 1 ) )

常用：

A ≈ 0.6180339887（黄金比例）

适合整数、浮点数。

✅ 方法三：字符串哈希（经典）

1️⃣ 简单加权求和

hash = 0
for c in str:
    hash = hash * P + c

常用：

P = 31 或 131

➕ 最后再取模：

hash = hash mod N

✅ Java hashCode() 就是类似思想

2️⃣ 带进位的字符串哈希（防溢出）

int hash = 0;
for (char c : str.toCharArray()) {
    hash = (hash * 31 + c) & 0x7fffffff;
}

✅ 方法四：位运算哈希（高性能）

hash ^= (hash << 5) | (hash >> 27);

✅ 特点：

• 快
• 雪崩效应好
• 常用于底层系统

三、实战示例

✅ 示例 1：整数哈希（Java HashMap 思想）

static int hash(int key) {
    key ^= (key >>> 20) ^ (key >>> 12);
    return key ^ (key >>> 7) ^ (key >>> 4);
}

✅ 示例 2：字符串哈希（教学版）

int hash(String s, int N) {
    int h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = h * 31 + s.charAt(i);
    }
    return h % N;
}

✅ 示例 3：对象哈希（真实工程）

class Person {
    String name;
    int age;

    public int hashCode() {
        return Objects.hash(name, age);
    }
}

四、哈希表大小怎么选？

✅ 选质数

N = 101, 1009, 10007, 100003

原因：

• 减少周期性冲突
• 分布更均匀

✅ 动态扩容时：

• 负载因子 α ≈ 0.75
• 超过就 rehash

五、常见错误 ❌

❌ 1. 哈希函数太简单

hash = key % 10

如果 key 是 10 的倍数 → 全冲突

❌ 2. 忽略负数

hash = hash % N; // 可能为负

✅ 正确：

hash = (hash & 0x7fffffff) % N;

❌ 3. 只哈希一部分字段

hash = name.hashCode(); // 忽略 age

六、什么时候不用自己设计？

✅ 不用自己写的情况

• Java：Objects.hash()
• C++：std::hash
• 安全场景：SHA-256、HMAC

✅ 需要自己设计的情况

• 刷题（字符串哈希）
• 嵌入式 / 高性能系统
• 一致性哈希
• 自定义对象 + 哈希表

七、一句话总结

好的哈希函数 = 快 + 均匀 + 稳定

如果你愿意，可以告诉我：

• 你是用在 哈希表 / 缓存 / 安全 / 刷题 / 分布式？
• 输入类型是什么？

我可以直接帮你定制一个最合适的哈希函数。