寻找哈希表C库
我确实检查了以前关于这个主题的问题，但找不到符合我需要的解决方案。
我需要的：
-
支持字符串和整数元组（C中的int数组）。 如果它是整数数组，则长度在编译时固定。
-
快速。
-
内存效率高。 我将需要使用它来处理超大型数据集。
-
哈希表的容量将动态增长。 我喜欢由库处理的哈希表大小的增长，而不是我。
-
我需要创建大量这样的哈希表。 并且这些哈希表将像树一样链接，因为一个哈希表中的值指向其他哈希表。
我的应用程序是内存和CPU绑定。 – 我是多么幸运啊！ 🙂
我现在不考虑任何C ++实现，除非我在C中找不到任何解决方案。
谢谢！
那么uthash – C结构的哈希表 。
- 支持字符串和整数元组
uthash对密钥没有限制： 密钥和结构可以有任何数据类型 。
它包括用于散列公共密钥类型的默认宏，即整数和字符串。 此外，它还提供通用宏（ HASH_ADD和HASH_FIND ）以支持任何数据类型 。
- 快速
听起来像是：
添加，查找和删除通常是恒定时间操作。 […]这个哈希的目的是简约和高效。 这是大约900行C.
- 内存效率高
更多细节在这里 ：
散列句柄在32位系统上每个项目消耗约32个字节，或在64位系统上每个项目消耗56个字节。 其他管理成本 – 桶和表 – 相比之下可以忽略不计。
- 哈希表的容量将动态增长
它支持开箱即用 ：
根据需要，铲斗扩展会自动且无形地发生。 应用程序无需知道何时发生。
Blender（3D图形应用程序）有自己的散列库BLI_ghash ，它有一些有用的function。
虽然不是作为独立库编写的，但它并不难提取，但它可能有用作参考。 （注意其GPL2许可） 。
- 使用内存池作为元素。
- 根据需要（自动）扩展铲斗。
- 每个元素需要3个指针（每个元素12或24个字节）。
- 用于散列字符串，指针，整数的实用程序函数，或者可以选择进行比较和散列回调。
- 暴露一个迭代器（循环遍历ghash中的所有项目）。
- 同时公开BLI_gset API，基于BLI_ghash，但保存存储值指针。
其他补充：
- 可以预留一个大小，以避免在提前知道大小时resize。
- 可以计算散列函数的质量（用于测试桶的均匀分布）。
从你的描述来看，它没有做得那么好 – 分配很多地图，因为每个地图都有自己的内存池，但没有很大的限制阻止你共享一个mempool，它只是没有开箱即用。
源代码： BLI_ghash.c ， BLI_ghash.h BLI_mempool.c ， BLI_mempool.h
注意， MEM_mallocN/MEM_freeN函数可以由malloc/free替换