C Academy · 课时

哈希函数

Q: 「哈希函数」这节课中我会学到什么？

将键映射到桶 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

将键映射到桶

哈希函数 是 CoddyKit 上的免费 C Academy 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

什么是哈希函数

哈希函数接收一个键，并生成数组中桶的整数索引。它是哈希表的核心，可以将字符串等任意键转换为快速的数组位置。

输入：一个键（字符串、整数等）
输出：范围为 [0, capacity) 的桶索引

良好哈希的特性

良好的哈希函数应当具有确定性、高速度，并将键均匀地分散到各个桶中。

相同的键始终产生相同的索引
键的微小变化会导致索引发生较大变化（雪崩效应）
对于典型数据，冲突较少

映射到桶

计算出原始哈希值后，使用取模运算符将它映射到哈希表中：index = hash % capacity。

请使用 unsigned 类型，以确保取模不会产生负索引。

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

简单的求和哈希

最简单的字符串哈希会将字符值相加。它易于实现，但分布效果较差，因为字母顺序不同的字符串可能发生冲突。

运行它，观察两个不同的字符串如何得到相近的哈希值。

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

DJB2 哈希

DJB2 是 Daniel J. Bernstein 提出的经典且分布良好的字符串哈希算法。它从 5381 开始，并使用 hash * 33 + c。

乘法与加法的混合比简单求和能更好地打散位。

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++))
        h = ((h << 5) + h) + c; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

FNV-1a 哈希

FNV-1a 先对每个字节执行 XOR，再乘以一个质数。它简单、快速且应用广泛。

顺序是：先 XOR，再乘法（这就是 1a 变体）。

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

整数哈希

整数键仍然需要进行混合，因为仅使用 x % capacity 时，如果键具有相同的模式，就会发生聚集。乘法混合算法（Knuth）可以分散各个位。

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

二的幂容量

当容量是二的幂时，可以使用快速的按位 AND 替代 % capacity：hash & (capacity - 1)。

之所以可行，是因为二的幂减一的低位构成了完整的掩码。

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

为什么取模可能很慢

% 运算符会编译为除法指令，而除法比 AND 更慢。在紧密循环中，这一点很重要。

容量为二的幂的哈希表：使用 AND 掩码
容量为质数的哈希表：使用取模（对于较弱的哈希函数，分布更好）

冲突不可避免

根据鸽巢原理，将许多键映射到较少的桶中必然会产生冲突。良好的哈希函数可以尽量减少冲突，但无法完全消除冲突。

下一课将介绍如何解决冲突。

分布演示

让我们统计 DJB2 如何将几个键分布到 8 个桶中。良好的哈希函数会使键分布得相当均匀。

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

int main(void) {
    const char *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

快速检查

测试您对哈希函数基础知识的理解。

回顾

您学习了哈希函数的作用，以及如何将键映射到桶中。

良好的哈希函数具有确定性、速度快且分布均匀
DJB2 和 FNV-1a 是可靠的字符串哈希算法
使用 % capacity 进行映射；容量为二的幂时使用 & (capacity-1)
使用无符号类型；冲突无法避免

常见问题解答

「哈希函数」课时是免费的吗？

是的 — 「哈希函数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「哈希函数」这节课中我会学到什么？

将键映射到桶你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「哈希函数」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy