Hash table

2026-10-11

shuiming….. Hash table in deta…

deepseek….. 哈希表（Hash Table）是计算机科学里最优雅、也最实用的数据结构之一。它在K&R2的6.6节中出现，是你从“基础语法”跨向“系统设计”的关键里程碑。

我们用“仓库搬运”的物理视角，把它彻底拆解清楚。

一、核心问题：为什么要用哈希表？

假设你是一个仓库管理员（CPU），你的任务是从成千上万个货架（数组）中，快速找到特定的货物（数据）。

· 普通数组：你知道货物的编号（下标），比如“第42号货架”，可以瞬间定位。但如果只知道货物的名字（比如字符串 "max"），你就得从头到尾一个个比对，这叫线性查找（O(n)），效率极低。 · 哈希表：它发明了一个“翻译官”（哈希函数），能把字符串 "max" 直接翻译成数字 42。这样，你下次找 "max"，直接去42号货架就行了。时间复杂度瞬间降到 O(1)。

二、物理结构：数组 + 链表的“杂交”

K&R2的6.6节，用C语言实现了一个最基础、最经典的哈希表。它的物理内存结构由两部分组成：

哈希桶数组（Hash Bucket Array）

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE];

这是一个大小为101的指针数组。你可以把它想象成仓库里的101个“固定货架”。每个货架上面，放的是一串用链表串起来的货物。

链表节点（Linked Node）

struct nlist {
    struct nlist *next; // 指向下一个节点
    char *name;         // 货物的名字（比如 "max"）
    char *defn;         // 货物的内容（比如 "100"）
};

这是实际的“货物”。因为算出来的货架号可能冲突（不同的名字算出同一个数字），所以用链表把它们串起来。

三、核心算法：哈希函数（The Hash Function）

它是整个哈希表的灵魂。K&R2给出的算法极其精简：

unsigned hash(char *s) {
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

· *s + 31 * hashval：把字符串里每个字符的ASCII码，乘以31，再加上前一个结果。这是一种经典的“滚动哈希”算法（31是个质数，能有效打散数据）。 · % HASHSIZE（即 % 101）：这是最关键的一步。因为前面算出来的数字可能极其巨大，% 101 能把它强制压缩到 0~100 的范围内，刚好对应101个货架。

四、两大核心操作：lookup 和 install

lookup（查找）

· 先通过哈希函数算出货架号。 · 直接跳到那个货架。 · 顺着链表用 strcmp 逐个比对名字。如果找到就返回指针，没找到就返回 NULL。

install（安装/插入）

· 先调用 lookup 看看这个名字是否已经存在。 · 如果不存在，用 malloc 申请一块新的内存（造一个新货箱），把名字和定义填进去。 · 用“头插法”把它挂到对应货架的链表最前面：np->next = hashtab[hashval]; hashtab[hashval] = np;。这操作只需两步，时间复杂度 O(1)。

五、最现实的问题：哈希冲突（Hash Collision）

这是哈希表无法避免的物理现象。

· hash("max") 算出 42。 · hash("min") 也算出 42。两个不同的东西，算到了同一个货架号。这就是冲突。 K&R2的解决方案极其经典：拉链法（Chaining）。货架42上不是只放一个，而是挂一串链表。找 "max" 的时候，先找到货架42，再顺着链子逐个比对，直到找到 "max" 为止。

六、为什么这是“仓库搬运工”的代码？

你之前说“写C程序叫作内存搬砖很贴切”，哈希表就是最好的例子：

· hash() 函数是你拿着扫码枪扫描货物名字，算出货架编号。 · lookup() 是你走到货架前，在一串货物里翻找你要的那件。 · install() 是你把新货物挂到货架上。 · 冲突处理是你发现两个货物的货架编号一样，于是你发明了“货架+挂钩”的立体存储方式。

七、哈希表的真实应用（你每天都在用）

· Python的dict：你之前问过的Python字典，底层就是一个高度优化过的哈希表。 · Git版本控制：Git用哈希值（SHA-1）来给每一次提交做指纹，确保数据没有损坏。 · 数据库索引：几乎所有关系型数据库（MySQL等）的索引底层，都是哈希表或B+树。 · Unix/Linux文件系统：目录查找、进程调度都大量依赖哈希表。

八、给你的GDB验证建议

你在K&R2的代码里跑起来后，在GDB里：

p hashtab 查看整个指针数组。
p hashtab[hash("max")] 查看对应货架上的链表头。
p *hashtab[hash("max")] 查看链表第一个节点的 name 和 defn。
用 x/16xb hashtab 看看内存里的指针地址布局。

哈希表就像是你仓库管理系统的“智能索引”，让你在庞大的数据里，能用O(1)的时间，瞬间定位到你想要的那件货。这是C语言在系统编程中极其核心的武器。保重身体，慢慢拆！