PAYATHON 2026

纯 C 中有哪些支持 RapidHash 和动态扩容的高性能哈希表？

数据小许

可以先比较 khash 和 uthash：两者都适用于 C，支持扩容，也能接入自定义哈希函数。建议先用 khash 建立性能基线；如果需要把现有结构体直接加入哈希表，并保持结构体地址稳定，可以重点考虑 uthash。

现有信息不足以判断哪一个“最快”。键长度、数据规模、查找命中率、增删比例和内存分配方式都会影响结果，需要在实际负载下比较。

两个候选实现有什么区别？

实现自定义哈希方式扩容与存储特点适合优先评估的需求
khash通过 KHASH_INIT 指定哈希函数和相等判断函数开放寻址，插入时按容量条件扩容，也提供 kh_resize希望使用数组存储键和值，评估吞吐与内存占用
uthash定义 HASH_FUNCTION通过桶链组织元素，按需自动增加桶数希望索引现有结构体，并保持结构体地址稳定

这些功能可以在 khash 源码和 uthash 使用指南中确认。功能符合要求，并不能证明哪个实现更快。

如何给 khash 接入 RapidHash？

以非空、以 \0 结尾的字符串键和 int 值为例，准备好 khash.h 和 rapidhash.h，再使用自定义函数实例化哈希表。

示例使用 rapidhash(const void *key, size_t len) 接口，返回值为 64 位哈希。接入其他版本前，应核对实际头文件中的声明：RapidHash 接口源码。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rapidhash.h"
#include "khash.h"

static khint_t hash_string(const char *key)
{
    uint64_t h = rapidhash(key, strlen(key));
    return (khint_t)(h ^ (h >> 32));
}

static int equal_string(const char *a, const char *b)
{
    return strcmp(a, b) == 0;
}

KHASH_INIT(rapid_map, const char *, int, 1,
           hash_string, equal_string)

int main(void)
{
    khash_t(rapid_map) *map = kh_init(rapid_map);
    if (map == NULL)
        return EXIT_FAILURE;

    int status;
    khiter_t it = kh_put(rapid_map, map, "alpha", &status);
    if (status < 0) {
        kh_destroy(rapid_map, map);
        return EXIT_FAILURE;
    }
    kh_value(map, it) = 42;

    it = kh_get(rapid_map, map, "alpha");
    if (it != kh_end(map))
        printf("%d\n", kh_value(map, it));

    kh_destroy(rapid_map, map);
    return EXIT_SUCCESS;
}

示例显式将 64 位结果折叠到 khash 使用的 khint_t，让位宽转换清楚可见，但不能保证这种处理方式的性能最优。哈希值相同仍需比较键，因此不能省略 equal_string。

接入时需要注意什么？

  • 示例保存字符串指针，不复制字符串。字符串字面量在这里有效；换成动态字符串后，需要自行管理内存，键留在表中期间也不能修改其内容。
  • 判定为相等的键必须产生相同哈希。若使用带 seed 的接口，同一张表在存续期间应保持 seed 一致。
  • strlen 不适用于含有内嵌 \0 的二进制数据。此时应把指针和长度一起作为键，并按长度和字节内容比较。
  • khash 扩容可能移动内部数组；修改表后，不应继续使用此前取得的槽位索引或内部元素指针。上面的示例在插入后重新查找。

若改用 uthash，应在包含 uthash.h 前定义 HASH_FUNCTION，并在所有操作同一张表的编译单元中使用一致配置。它的桶扩容不会搬动应用提供的结构体，但结构体及键的内存仍由应用负责管理。uthash 使用指南

如何确定实际负载下哪个更快？

先让两个实现使用相同的键集合、RapidHash 配置和编译优化选项，再分别测量：

  1. 构建：从空表插入全部数据，计入内存分配和扩容成本。
  2. 查找：分开测量命中与未命中，并使用实际键长度分布。
  3. 混合操作：按业务中的比例执行插入、删除和查找。
  4. 资源开销：记录内存占用；如果关心延迟，再记录扩容时的耗时尖峰。

已知最终规模时，可以额外比较预分配容量后的表现，但要把它与从空表增长的结果分开记录。测试中还要实际使用查找结果，避免编译器消除无效操作。

RapidHash 的单独计算速度不能代表整张哈希表的速度。缺少上述测量结果时，这两个实现都值得试用，但尚不能认定其中任何一个最快。对 GLib 安全性的疑虑也需要具体说明是并发访问、内存管理还是其他问题，不能据此直接断言其实现不安全。

备注：内容仅供参考。