c - 如何实现固定大小的 HashMap ？

Question

我想实现一个hashmap，但我不允许让它扩展。因为我确实知道我最多需要存储 N 个元素，所以我可以为哈希表的每个存储桶预先分配一个包含 N 个元素的数组，这样我仍然可以在最坏的情况下存储 N 个元素，即所有键都在同一个存储桶上进行散列。但我需要存储的元素相当大，因此对于较大的 N 来说，这对内存的使用效率非常低。

是否可以使用固定数量的内存高效(就内存而言)实现 HashMap ，例如通过实现智能哈希函数？

(P.S.: key 是一个无符号的 32 位整数，我对 key 没有先验知识，除了我将收到的 key 值位于该范围的一个相当小的子集中，并且该子集向上移动非常缓慢范围内。)

---

我现在有一个实现，其中有两个长度为 N 的数组，一个包含元素，另一个包含与位置 i 处的元素相对应的键两个数组。我使用模运算作为哈希函数来确定元素应插入/存在的位置，并使用线性探针来查找发生碰撞时最近的空点。我认为这的复杂度为 O(N)，并且我认为对于我期望的数据量来说，这将相当快地工作。我问这个问题是为了看看是否可以做得更好。

Answer 1

对于散列，您可以使用以下代码片段，顺便说一句，Linux 内核使用它来散列 PID:

unsigned long hash_long(unsigned long val, unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}

魔数(Magic Number)0x9e370001UL是一个很大的素数。以下是理解 Linux 内核的摘录，解释了这个神奇的数字:

You might wonder where the 0x9e370001 constant (= 2,654,404,609) comes from. This hash function is based on a multiplication of the index by a suitable large number, so that the result overflows and the value remaining in the 32-bit variable can be considered as the result of a modulus operation. Knuth suggested that good results are obtained when the large multiplier is a prime approximately in golden ratio to 232 (32 bit being the size of the 80×86’s registers). Now, 2,654,404,609 is a prime near to that can also be easily multiplied by additions and bit shifts, because it is equal to 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1.

右移 hash >> (32 - 位); 只是表示在哈希值中保留 bits 位数。其他位将被清零。在您的情况下，位将由限制N确定。为了使其按原样工作，N 需要设置其最高有效设置位之后的所有位，例如对于 N = 7(最后三位均已设置且所有其他位均为零)，bits 将为 3。或者 N = 63其中最低有效六位均已设置，所有其他位均为零。这里位将为6。

hash_long 函数返回的值将形成数组的索引。

处理碰撞

为了处理冲突，只保留一个数组，但使其成为链表节点的数组。所以数组中的每个元素都指向一个链表。当发生冲突时，只需将新条目附加到与数组中该插槽对应的链表末尾。

处理碰撞(更新)

如果您无法动态分配新内存，那么您发布的解决方案似乎很好，尽管我不确定仅包含键的数组的用途是什么(键不应该是它所属元素的成员吗？ )。以下是对您的解决方案的建议:

拥有一维数组意味着在发生碰撞时，我们在插入和检索时都会执行线性探测。另一种方法是使用一个二维数组，其中内部数组充当链表。我们需要插入每个内部数组中最后一个元素的索引。与一维数组相比的缺点是，如果同一索引上发生太多冲突，那么我们可能会耗尽其中一个内部数组的空间，除非我们也将每个内部数组的长度设置为 N，这将导致大量浪费空间。优点是插入时我们不需要进行线性探测。我们只需检查内部数组中最后一个元素的索引并将其加一以获得下一个槽以插入新元素。