数据结构与算法 / 系统课时

哈希函数

哈希函数

哈希表需要快速找到可能保存键的位置。先计算键的整数哈希值,再按当前桶数把它映射到下标。落在同一桶里的键仍须根据相等规则区分。

学习目标

  • 区分键、原始哈希值、桶下标和两类冲突。
  • 解释 Java equals 与 hashCode 的一致性要求。
  • 用正容量和非负余数处理包含极端值的整数哈希。

从键到桶

设桶数 m>0m>0。本课使用 Math.floorMod(hash, m) 把原始整数压到 [0,m)。这是本例的压缩规则;具体容器还可能对原始哈希做混合,并采用其他下标计算方式。即使两键哈希不同,也可能因容量映射落到同一桶。若原始哈希已经相同,同一压缩规则当然不能把它们分开。 Java Math.floorMod Java HashMap 说明

键经过哈希函数映射到桶的流程

在 Java 中,按 equals 相等的对象必须有相同的 hashCode。反过来并不成立。参与相等的状态没有变时,同一程序执行期间的哈希值应保持一致。一般对象的哈希值不保证跨程序运行稳定;String.hashCode 则有规定的整数多项式计算。若存入哈希表后修改了参与判等或哈希的字段,元素可能无法按原方式找回。 Java Object.hashCode 契约 Java String.hashCode 计算

安全地计算桶下标

Java 的 % 是余数,负哈希可能得到负值。Math.abs(Integer.MIN_VALUE) 仍为负,用它再取余也不能覆盖全部整数。对于正容量,floorMod 返回非负结果。不同键域映射到有限桶中,好的分布可以减少局部拥挤;小样本恰好分散,不能证明对其他键也分散。普通集合的哈希值也不适合作为完整性或身份凭据。 Java Math 取余与绝对值

Java 17 实例

用 String.hashCode 核对真实冲突,再把不同原始哈希映到同一桶。保存为 HashFunctionDemo.java。执行 javac -encoding UTF-8 --release 17 HashFunctionDemo.java,再执行 java HashFunctionDemo。

java
import java.util.Arrays;

public class HashFunctionDemo {
    static int bucketIndex(int hash, int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        return Math.floorMod(hash, capacity);
    }

    public static void main(String[] args) {
        String[] keys = {"apple", "banana", "Aa", "BB", "a", "i"};
        int capacity = 8;
        int[] loads = new int[capacity];
        for (String key : keys) {
            int hash = key.hashCode();
            int bucket = bucketIndex(hash, capacity);
            loads[bucket]++;
            System.out.printf("%s -> hash=%d, bucket=%d%n", key, hash, bucket);
        }
        System.out.println("桶负载: " + Arrays.toString(loads));
        System.out.println("最小 int 在 3 个桶中: " + bucketIndex(Integer.MIN_VALUE, 3));
    }
}
text
apple -> hash=93029210, bucket=2
banana -> hash=-1396355227, bucket=5
Aa -> hash=2112, bucket=0
BB -> hash=2112, bucket=0
a -> hash=97, bucket=1
i -> hash=105, bucket=1
桶负载: [2, 2, 1, 0, 0, 1, 0, 0]
最小 int 在 3 个桶中: 1

Aa 与 BB 的原始哈希值相同,改变容量后仍会同桶。a 与 i 只在这个例子的容量压缩后同桶,改成容量 7 时可以分开。查找时即使先比较哈希,也要检查实际键相等。键若是长字符串,计算其哈希或比较内容也可能依赖键长,不能把所有键操作都视为固定时间。 Java String.hashCode 计算

本课练习

把容量改成 1 和 7,验证所有下标仍合法,记录两类冲突的变化。再用两个整数写一个不可变 record Key,确认相等键放入集合后只保留一个成员。下一课用链地址法保存和查找同桶的不同键。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

哈希函数

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通