4、链地址法实现（上）：结构体定义、节点设计、哈希表初始化、插入操作实现

好，咱们今天正式进入链地址法的代码实现环节。说实话，哈希表这块内容，很多教材讲得偏理论，一上来就给你看一堆数学公式。我个人觉得，对于C语言开发者来说，先把结构体定义清楚，把节点怎么挂、怎么取搞明白，比什么都重要。

链地址法，说白了就是「数组 + 链表」的组合拳。数组用来做哈希桶，每个桶里挂一个链表。冲突了？没关系，往链表后面挂就行。我当年第一次实现这个结构时，犯了个低级错误——忘了给每个桶初始化空链表，结果插入时直接段错误。嗯，这种坑咱们今天必须避开。

4.1 结构体定义与节点设计

先看节点。哈希表里存的是键值对，每个节点就是一个链表结点。我习惯把 key 和 value 分开存，这样扩展性更好。

// 哈希表节点
typedef struct HashNode {
    int key;                // 键
    int value;              // 值
    struct HashNode *next;  // 指向下一个节点
} HashNode;

这里要注意：next 指针必须显式声明为 struct HashNode *，因为 typedef 还没结束，不能直接用 HashNode *。这个细节我见过不少新手栽跟头。

接下来是哈希表本身的结构。它包含一个桶数组，以及当前存储的元素个数。桶数组的每个元素是一个 HashNode * 指针，指向该桶链表的头节点。

// 哈希表结构
typedef struct HashTable {
    HashNode **buckets;  // 桶数组，每个元素是链表头指针
    int size;            // 桶的数量
    int count;           // 当前存储的键值对数量
} HashTable;

关键设计决策：

  • buckets 是二级指针：因为每个桶存的是 HashNode *，所以桶数组的类型就是 HashNode **。
  • size 和 count 分开记录：size 是桶总数，固定不变（除非扩容）；count 是实际元素数，用于计算负载因子。

我个人建议把 size 选为质数，比如 127、251 这些。为什么？因为哈希函数取模时，质数能减少哈希碰撞的概率。我在一个项目中用过 128（2的幂），结果某些 key 分布极不均匀，一个桶挂了上千个节点，其他桶空荡荡。换成 127 后，分布立马均匀多了。

4.2 哈希表初始化

初始化要做三件事：分配桶数组、把每个桶置空、设置初始值。代码很简单，但容易漏掉细节。

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    if (!ht) return NULL;

    ht->size = size;
    ht->count = 0;

    // 分配桶数组
    ht->buckets = (HashNode **)malloc(sizeof(HashNode *) * size);
    if (!ht->buckets) {
        free(ht);
        return NULL;
    }

    // 每个桶初始化为空链表
    for (int i = 0; i < size; i++) {
        ht->buckets[i] = NULL;
    }

    return ht;
}

⚠️ 我曾经踩过的坑：

忘记初始化每个桶为 NULL！malloc 分配的内存内容是不确定的，如果不手动置 NULL，后续插入时判断 buckets[hash] == NULL 就会出错。这个 bug 我调了整整一下午，最后发现是初始化漏了循环。

另外，内存分配失败的处理一定要做。虽然平时很少遇到 malloc 返回 NULL，但在嵌入式环境或内存紧张的系统里，这是必备的健壮性措施。

4.3 哈希函数

哈希函数的选择直接影响性能。对于整数 key，最简单的就是取模。但取模有个讲究：用质数取模效果更好。

// 哈希函数：取模
int hash(int key, int size) {
    return key % size;  // size 建议选质数
}

你可能会问：如果 key 是负数怎么办？C 语言的 % 运算结果可能是负数。我一般这样处理：

int hash(int key, int size) {
    return (key % size + size) % size;  // 保证结果在 [0, size-1]
}

嗯，加一次 size 再取模，确保索引非负。这个写法虽然多了一次运算，但胜在安全。

4.4 插入操作实现

插入操作是链地址法的核心。流程很简单：

  1. 计算 key 的哈希值，找到对应桶
  2. 遍历该桶的链表，检查 key 是否已存在
  3. 如果存在，更新 value；如果不存在，头插法或尾插法插入新节点

我个人偏爱头插法，因为不用遍历到链表尾部，时间复杂度 O(1)。但要注意：头插法会改变链表中节点的顺序，如果后续需要按插入顺序遍历，就得用尾插法。

// 插入键值对
void insert(HashTable *ht, int key, int value) {
    int index = hash(key, ht->size);
    HashNode *current = ht->buckets[index];

    // 遍历链表，查找是否已存在
    while (current != NULL) {
        if (current->key == key) {
            // key 已存在，更新 value
            current->value = value;
            return;
        }
        current = current->next;
    }

    // key 不存在，创建新节点（头插法）
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    if (!newNode) return;  // 内存分配失败处理

    newNode->key = key;
    newNode->value = value;
    newNode->next = ht->buckets[index];
    ht->buckets[index] = newNode;
    ht->count++;
}

💡 关于头插法的思考：

头插法代码简洁，性能也好。但如果你需要实现 LRU 淘汰策略，或者要求遍历顺序与插入顺序一致，那就得用尾插法。尾插法需要维护一个 tail 指针，或者每次遍历到链表末尾。我个人在大多数场景下用头插法，除非有明确顺序要求。

4.5 完整代码示例

把上面几段拼起来，就是一个可运行的链地址法哈希表雏形。我习惯把结构体定义、函数声明放头文件，实现放 .c 文件。这里为了演示，全部写在一起。

#include <stdio.h>
#include <stdlib.h>

// 哈希表节点
typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表结构
typedef struct HashTable {
    HashNode **buckets;
    int size;
    int count;
} HashTable;

// 哈希函数
int hash(int key, int size) {
    return (key % size + size) % size;
}

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    if (!ht) return NULL;

    ht->size = size;
    ht->count = 0;
    ht->buckets = (HashNode **)malloc(sizeof(HashNode *) * size);
    if (!ht->buckets) {
        free(ht);
        return NULL;
    }

    for (int i = 0; i < size; i++) {
        ht->buckets[i] = NULL;
    }
    return ht;
}

// 插入键值对
void insert(HashTable *ht, int key, int value) {
    int index = hash(key, ht->size);
    HashNode *current = ht->buckets[index];

    while (current != NULL) {
        if (current->key == key) {
            current->value = value;
            return;
        }
        current = current->next;
    }

    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    if (!newNode) return;

    newNode->key = key;
    newNode->value = value;
    newNode->next = ht->buckets[index];
    ht->buckets[index] = newNode;
    ht->count++;
}

// 打印哈希表（调试用）
void printHashTable(HashTable *ht) {
    for (int i = 0; i < ht->size; i++) {
        printf("bucket[%d]: ", i);
        HashNode *current = ht->buckets[i];
        while (current != NULL) {
            printf("(%d, %d) -> ", current->key, current->value);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main() {
    HashTable *ht = createHashTable(7);  // 7 是质数

    insert(ht, 10, 100);
    insert(ht, 17, 200);
    insert(ht, 24, 300);  // 10、17、24 对 7 取模分别是 3、3、3，会冲突
    insert(ht, 5, 50);

    printHashTable(ht);

    // 清理内存（略，后续章节会讲）
    return 0;
}

运行结果会看到：bucket[3] 上挂了三个节点（10、17、24），bucket[5] 上挂了一个节点（5）。这就是链地址法处理冲突的效果——冲突的 key 都挂在同一个桶的链表上。

4.6 核心逻辑流程图

下面这张图展示了插入操作的整体流程，从计算哈希到最终挂载节点，一目了然。

链地址法插入操作流程图 输入 key, value 计算 hash(key) % size 定位到 buckets[index] 链表为空？ 是 直接插入头节点 否 遍历链表查找 key

4.7 小结与避坑指南

这一章的内容其实就三个核心点：结构体怎么设计、初始化要注意什么、插入操作怎么实现。我再用自己的经验帮你总结几个容易踩的坑：

常见错误 后果 正确做法
桶数组未初始化 插入时野指针崩溃 malloc 后循环置 NULL
哈希函数未处理负数 数组索引越界 用 (key % size + size) % size
插入时未检查 key 是否已存在 出现重复 key，数据不一致 先遍历链表查找，再决定更新还是插入
头插法忘记更新桶指针 新节点丢失，内存泄漏 newNode->next = buckets[index]; buckets[index] = newNode;

我曾经在一个线上项目中，因为哈希表初始化漏了置 NULL，导致服务启动后随机崩溃。查了两天，最后发现是这个低级错误。从那以后，我写初始化代码都会反复检查循环体。

好了，链地址法的前半部分就讲到这里。结构体定义、节点设计、初始化、插入操作，这些是哈希表最基础的骨架。你把这些代码亲手敲一遍，跑一跑，比看十遍文章都管用。

公众号：蓝海资料掘金营，微信 deep3321
← 上一章 📖 返回目录 下一章 →