C / C++ / 系统课时

实现一个字符串哈希表

实现一个字符串哈希表

这一节把字符串哈希函数、桶数组和链表真正组合起来,做出一个可插入、更新、查询和释放的基础哈希表。重点不是追求工业级性能,而是看清键如何从字符串变成桶下标,以及发生哈希冲突后如何沿链表继续查找。

学习目标

  • 理解字符串哈希值如何映射到固定数量的桶。
  • 使用链地址法处理不同字符串落入同一桶的冲突。
  • 完成插入、更新、查询和内存释放,并用输出验证结果。

哈希表由哪几部分组成

以字符串为键时,哈希表至少需要三部分:哈希函数负责把字符串变成整数;桶数组负责根据下标快速定位候选区域;桶中的链表负责保存真正的键值对,并处理哈希冲突。

字符串哈希表的桶与链表结构

链地址法的关键是:桶数组只保存链表头指针。查询时先用同一个哈希函数找到桶,再逐个比较字符串;只有 strcmp 返回 0 才表示命中真实键,因此哈希值相同并不会把两个键混为一谈。

完整实现

下面使用固定 8 个桶实现最小可运行版本。字符串复制函数自行分配内存,避免依赖非标准的 strdup。

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

#define BUCKET_COUNT 8

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;

typedef struct {
    Entry *buckets[BUCKET_COUNT];
} HashTable;

static unsigned long hash_string(const char *s) {
    unsigned long hash = 5381;
    unsigned char c;

    while ((c = (unsigned char)*s++) != 0) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

static char *dup_string(const char *s) {
    size_t len = strlen(s) + 1;
    char *copy = malloc(len);

    if (copy != NULL) {
        memcpy(copy, s, len);
    }
    return copy;
}

static void table_init(HashTable *table) {
    for (size_t i = 0; i < BUCKET_COUNT; ++i) {
        table->buckets[i] = NULL;
    }
}

static int table_put(HashTable *table, const char *key, int value) {
    size_t index = hash_string(key) % BUCKET_COUNT;

    for (Entry *p = table->buckets[index]; p != NULL; p = p->next) {
        if (strcmp(p->key, key) == 0) {
            p->value = value;
            return 1;
        }
    }

    Entry *entry = malloc(sizeof(*entry));
    if (entry == NULL) {
        return 0;
    }

    entry->key = dup_string(key);
    if (entry->key == NULL) {
        free(entry);
        return 0;
    }

    entry->value = value;
    entry->next = table->buckets[index];
    table->buckets[index] = entry;
    return 1;
}

static int table_get(const HashTable *table, const char *key, int *out_value) {
    size_t index = hash_string(key) % BUCKET_COUNT;

    for (Entry *p = table->buckets[index]; p != NULL; p = p->next) {
        if (strcmp(p->key, key) == 0) {
            *out_value = p->value;
            return 1;
        }
    }
    return 0;
}

static void table_free(HashTable *table) {
    for (size_t i = 0; i < BUCKET_COUNT; ++i) {
        Entry *p = table->buckets[i];

        while (p != NULL) {
            Entry *next = p->next;
            free(p->key);
            free(p);
            p = next;
        }
        table->buckets[i] = NULL;
    }
}

int main(void) {
    HashTable table;
    int value;

    table_init(&table);

    if (!table_put(&table, "apple", 3) ||
        !table_put(&table, "banana", 5) ||
        !table_put(&table, "name", 42) ||
        !table_put(&table, "orange", 7) ||
        !table_put(&table, "banana", 9)) {
        fprintf(stderr, "memory allocation failed\n");
        table_free(&table);
        return 1;
    }

    if (table_get(&table, "banana", &value)) {
        printf("banana=%d\n", value);
    }
    if (table_get(&table, "name", &value)) {
        printf("name=%d\n", value);
    }

    printf("pear found=%s\n",
           table_get(&table, "pear", &value) ? "yes" : "no");

    table_free(&table);
    return 0;
}

预期输出

text
banana=9
name=42
pear found=no

在这个 8 桶示例中,banana 与 name 会落入同一桶,但两者仍能分别查到正确值,说明链表冲突处理生效。banana 第二次写入时不会创建重复节点,而是找到已有键并更新为 9;pear 不存在,因此查询返回失败。

冲突为什么不会破坏查询

两个不同字符串可能得到同一个桶下标,这就是哈希冲突。插入新键时,代码先扫描当前桶:若找到同名键就更新;否则把新节点挂到链表头。查询也执行同样的“定位桶,再比较键”流程,所以冲突只会增加桶内比较次数,不会直接产生错误结果。

当键分布均匀、装载因子合理时,插入和查询的平均时间通常接近 O(1)O(1);如果大量键都挤进同一桶,链表会变长,最坏情况下会退化为 O(n)O(n)。实际哈希表通常会在元素增多时扩容并重新散列。

实现时最容易漏掉的边界

这个版本最值得检查的是内存所有权。表内不能只保存调用者传入的字符串指针,否则原字符串离开作用域或被修改后,键就会失效。因此插入新键时复制字符串,释放表时同时释放键和节点。

另一个边界是空指针约定:当前接口假设 table、key 和 out_value 都是有效指针。若要把它升级为公共库,应明确参数检查策略,并增加删除操作、动态扩容以及更稳定的哈希函数。基础版本先把“哈希定位 + 桶内链表 + 键比较 + 生命周期管理”做对,就已经形成了完整的字符串哈希表索引。

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

目录与阅读设置

阅读设置

17

记录一个想法

实现一个字符串哈希表

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

登录哪都通