如何实现固定大小的哈希图？

Question

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

是否可以使用固定数量的内存（例如通过实现智能散列函数）有效地（就内存而言）实现散列图？

（PS：键是一个无符号的 32 位整数，我对键没有先验知识，只是我将收到的键值在范围的一个相当小的子集中，并且这个子集在范围内移动得非常缓慢.)

---

我现在有一个实现，其中我有两个 length 数组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);
}

幻数0x9e370001UL是一个很大的质数。以下是“理解 Linux 内核”中解释幻数的摘录：

您可能想知道 0x9e370001 常量 (= 2,654,404,609) 从何而来。这个散列函数基于索引乘以一个合适的大数，因此结果溢出，32位变量中剩余的值可以被认为是取模运算的结果。Knuth 建议，当大乘法器是大约黄金比例为 232（32 位是 80×86 寄存器的大小）的素数时，可以获得良好的结果。现在，2,654,404,609 是接近的素数，也可以很容易地乘以加法和位移，因为它等于 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 .

右移hash >> (32 - bits);只是说保留位的散列值的比特数。其他位将被清零。在您的情况下，位将由 limit 确定N。为了使其正常工作，N需要使其最高有效设置位之后的所有位也设置，例如N = 7（其中最后三位都设置并且所有其他位为零）并且位将为3。或N = 63其中最低有效的六位都被设置，所有其他位都为零。这里的位将是 6。

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

处理碰撞

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

处理碰撞（更新）

如果您不能动态分配新内存，那么您发布的解决方案似乎很好，尽管我不确定只包含键的数组的目的是什么（键不应该是它所属元素的成员吗？）。以下是针对您的解决方案的建议：

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