寻找 C 中的数组（与链表）哈希表实现

Question

我正在寻找 C 中的哈希表实现，它将其对象存储在（二维）数组而不是链接列表中。 即，如果发生冲突，导致冲突的对象将存储在下一个空闲行索引中，而不是推送到链表的头部和第一个元素。

另外，对象本身必须复制到哈希表中，而不是通过指针引用。 （对象不会在程序的整个生命周期中存在，但表却存在）。

我知道这样的实现可能会存在严重的效率缺陷，并且不是“散列的标准方式”，但当我致力于一个非常特殊的系统架构时，我需要这些特征。

谢谢

Answer 1

一个超级简单的实现：

char hashtable[MAX_KEY][MAX_MEMORY];
int counts[MAX_KEY] = {0}; 

/* Inserting something into the table */
SomeStruct* some_struct;
int hashcode = compute_code(some_struct);
int size = sizeof(SomeStruct); 
memcpy(hashtable[hashcode] + counts[hashcode] * size, some_struct, size);
++counts[hashcode];

不要忘记检查MAX_MEMORY。

Answer 2

我的猜测是您的系统不允许动态内存分配。因此，您需要预先定义适合您的数据的数组边界（对象总数和最大预期冲突），并另外为您的对象定义一个自定义哈希函数，因此最好实现您自己的哈希表。

Answer 3

它不是用 C 编写的，而是用 C++ 编写的，但请看一下 Google Sparse Hash -可能会给你一些想法。关键要求是所存储的对象有办法成为null。