C语言实现高效HashTable：结构、核心操作与迭代遍历

结果与目标

构建一个具备完整生命周期管理的哈希表（HashTable），支持动态分配、查找、插入、删除及高效遍历。该实现旨在通过内存池技术降低频繁申请/释放堆内存的系统开销，并解决哈希碰撞问题。

准备条件与数据结构

实现前需明确两个核心结构体：用于存储具体数据的节点（HashNode）和用于组织节点的哈希表容器（HashTable）。

定义 HashNode 结构

HashNode是链表的节点，采用链地址法解决哈希冲突。

typedef struct hashnode_struct {
    struct hashnode_struct *next; // 指向同一桶中的下一个节点
    const char *key;              // 键名
    void *val;                    // 指针类型的值
} *hashnode, _hashnode;

定义 HashTable 结构

HashTable包含内存池句柄、桶数量、节点计数以及桶数组指针。

typedef struct hashtable_struct {
    pool_t p;                       // 内存池句柄
    int size;                       // 桶数组大小
    int count;                      // 当前有效节点数
    struct hashnode_struct *z;      // 桶数组指针 (bucket array)
} *hashtable, _hashtable;

真实操作顺序

第1步：创建哈希表 (初始化)

• 目的：预分配一块连续的内存区域以存储表头信息和所有桶节点，避免碎片化。
• 入口：hashtable_new(int size)
• 动作：
  1. 计算所需总内存：包含 _hashtable 大小加上 size 个 _hashnode 的大小。
  2. 调用 _pool_new_heap 创建内存池。
  3. 从池中分配 _hashtable 空间作为表头，初始化 size 和 p。
  4. 从池中分配连续的空间赋给 ht->z，作为桶数组。注意：此处数组长度应为传入的 size，而非变量 prime（原文代码可能有误，实际应使用 size）。
• 完成状态：返回非空的 hashtable 指针，其内部 z 数组已初始化。

第2步：计算哈希码 (Hash Function)

使用经典的 ELF Hash 算法将字符串转换为索引值，以保证分布均匀。

static int hashcode(const char *s, int len) {
    const unsigned char *name = (const unsigned char *)s;
    unsigned long h = 0, g;
    int i;
    for (i=0; i

第3步：存入 Key-Value (Insert/Put)

• 目的：在指定位置插入或更新数据。
• 入口：void hashtable_put(hashtable h, const char* key, void *val)
• 动作：
  1. 检查 key 是否已存在（调用内部 hashtable_node_get）。
  2. 如果存在：直接更新 node->val 和 node->key，无需新建节点。
  3. 如果不存在：
     • 计算 index = hashcode(key, len) % h->size。
     • 遍历该桶链表，优先复用标记为“无效”（Key为空）的旧节点以节省内存。
     • 若无可用旧节点，则调用 pool_malloc 分配新节点。
     • 将新节点插入链表头部（node->next = z[i].next; z[i].next = node;）。

第4步：获取 Value (Get)

• 目的：根据 Key 查找对应的 Value。
• 入口：void *hashtable_get(hashtable h, const char *key)
• 动作：
  1. 计算哈希索引。
  2. 遍历对应桶的链表进行匹配（比较长度和字符串内容）。
  3. 返回匹配节点的 val，未找到则返回 NULL。

第5步：释放资源 (Free)

• 风险提醒：由于使用了内存池，请勿手动 free 单个节点，否则会破坏内存池结构。
• 动作：hashtable_free(h) 仅需要调用一次 pool_free(h->p)，即可一次性回收所有相关内存。

第6步：实现高效的迭代遍历 (Iteration)

传统的遍历方式需要嵌套循环扫描整个数组及其链表，效率低下且无法感知当前位置。为实现类似 C++ STL Iterator 的功能，需要对 HashTable 结构进行扩展，增加游标域。

1. 结构修改：在 _hashtable 中添加：

int bucket;     // 当前所在桶的索引
hashnode node;  // 当前所在的节点指针

2. 初始化迭代器 (hashtable_iter_first)：
   • 重置 bucket 为 -1，node 为 NULL。
   • 立即调用 hashtable_iter_next 寻找第一个有效节点。
3. 获取下一个节点 (hashtable_iter_next)：
   1. 若当前节点有下一个链表节点 (node->next)，则直接移动到那里。
   2. 若当前桶内无更多节点，递增 bucket 索引，直到找到一个包含有效节点（Key和Val不为NULL）的桶。
   3. 若扫描完所有桶仍未找到，重置游标并返回失败。
4. 注意事项：如果在遍历过程中删除了当前 node，必须重新调用 hashtable_iter_next 以使游标跳过被删除的位置，防止悬垂指针。

总结

以上是在C语言中实现具有高性能和良好内存管理特性的HashTable的详细内容，主要涵盖了数据结构设计、关键API实现以及高效的遍历方案，更多关于底层数据结构优化的资料请关注本站其它相关文章！