哈希表中的哈希码转换成内部表索引

Question

哈希图通常使用桶的内部数组（表）实现。访问哈希图通过键时，我们使用键类型特定（逻辑类型特定）的哈希函数获取密钥的哈希码。然后，我们需要将哈希码映射到实际的内部存储桶索引。

 key -> (hash function) -> hashcode -> (???) -> index in internal table

有时内部表可能会根据哈希映射填充比率而收缩和扩展。那么，哈希码->索引转换方法可能需要稍作更改。

例如，我们的哈希函数返回32位无符号整数值，且

A时刻：内部表容量为10000

B时刻：内部表容量为100000

通常用什么算法或方法来执行哈希码->内部表索引转换？如何解决表调整大小问题？

- vard

Answer 1

通常，简单的取模运算就可以完成任务。

举个例子，从维基百科上快速了解一下，就像这样简单：

hash = hashfunc(key)
index = hash % array_size

正如你所说，重新调整大小取决于哈希映射填充比率。数组将被重新分配（参见realloc()），然后给定新数组大小重新计算索引，并将值复制到它们的新索引。

- kjaquier

---

如果哈希值为负数，则相应的索引也将为负数。 - Satyendra

Answer 2

我在这里和这里写过。

当你增加索引向量的大小时，可以确定在较短向量上表现良好的算法在较长向量上表现会更差。可以事先进行测试，并在向量变长时采用新的算法。或者，随着当前向量中占用索引的数量增加，可以有一个后台低优先级线程，在数据上测试不同的算法。

正如我其中一个答案中的例子所示，“新算法”可能只是一对不同的匹配质数。

- Olof Forshell