如何实现固定大小的hashmap?

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

是否可以使用固定数量的内存有效地 (就内存而言)实现散列映射,例如通过实现智能散列函数?

(PS:密钥是一个无符号的32位整数,除了我将收到的键值在该范围的一个相当小的子集中之外我没有关于键的先验知识,并且该子集在该范围内移动得非常慢。)


我现在有一个实现,其中我有两个长度为N数组,一个带有元素,另一个带有与两个数组中位置i的元素对应的键。 我使用模运算作为哈希函数来确定元素应该插入/存在的位置,并使用线性探针来查找碰撞情况下最近的空白点。 我认为这是复杂的O(N),我认为这对于我期待的数据量来说会相当快。 我问了这个问题,看看能否做得更好。

对于散列,您可以使用以下代码段,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); 只是说保持哈希值中的位数。 其他位将被清零。 在您的情况下, 将由限制N确定。 为了使其按原样工作, N需要使其在其最重要的设置位之后的所有位也被设置,例如对于N = 7 (其中最后三位全部被设置而所有其他位都为零)并且将是3.或N = 63 ,其中最低有效6位全部置位,所有其他位为零。 位数为6。

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

处理碰撞

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

处理冲突(更新)

如果你不能动态分配新的内存,那么你发布的解决方案看起来很好,虽然我不确定只包含键的数组的目的是什么(键不应该是它所属元素的成员?)。 以下是对您的解决方案的建议:

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