我正在寻找 C 中的哈希表实现，它将其对象存储在（二维）数组而不是链表中。即如果发生碰撞，导致碰撞的对象将存储在下一个空闲行索引中，而不是推到链表的头部和第一个元素。
另外，对象本身必须被复制到哈希表中，而不是被指针引用。（对象不会在程序的整个生命周期中存在，但表会存在）。
我知道这样的实现可能有严重的效率缺陷，并且不是“标准的散列方式”，但是当我在一个非常特殊的系统架构上工作时，我需要这些特性。
谢谢
问问题
2449 次
3 回答
6
一个超级简单的实现：
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。
于 2010-04-28T16:09:44.973 回答
1
我的猜测是您的系统不允许动态内存分配。因此，您需要为您的数据定义合理的前端数组边界（总对象数和最大预期冲突），另外还需要为您的对象定义一个自定义哈希函数，因此最好实现自己的哈希表。
于 2010-04-28T16:05:54.073 回答
0
它不是在 C 中，而是在 C++ 中，但看看Google Sparse Hash - 可能会给你一些想法。关键要求是被存储的对象有办法成为null.
于 2010-04-28T16:07:33.800 回答