我想实现一个哈希图，但是不允许它扩展。因为我确实知道我最多需要存储N元素，所以我可以N为哈希表的每个存储桶预先分配一个包含元素的数组，这样我仍然可以N在最坏的情况下存储所有键都存储在同一存储桶中的元素。但是我需要存储的元素很大，因此，对于大的存储来说，N这是非常低效的使用。
是否可以通过固定数量的内存有效地（在内存方面）实现哈希图，例如通过实现智能哈希功能？
（PS：密钥是一个无符号的32位整数，除了对该密钥的了解，我没有任何先验知识，只是我将收到的密钥值位于该范围的一个很小的子集中，并且该子集在该范围内非常缓慢地向上移动）
现在，我有一个实现，其中有两个length数组N，一个包含元素，一个包含对应i于两个数组中元素的键的键。我将模运算用作哈希函数来确定应在何处插入/显示元素，并使用线性探针在发生碰撞的情况下找到最近的空白点。我认为这是复杂度O（N），并且我认为这对于我期望的数据量将相当快。我问了一个问题，看是否可以做得更好。
对于散列，您可以使用以下代码段，btw 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，这将导致很多浪费的空间。优点是插入时不需要执行线性探针。我们只是检查内部数组中最后一个元素的索引，然后将其递增一个，以获取下一个插入新元素的插槽。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句