Hashmap哈希码到内表索引的转换

Question

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

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

有时，内部表可能会收缩和扩展，具体取决于哈希图填充率。那么 hashcode->index 转换方法可能可以稍微改变一下。

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

A时刻：内表容量为10000

B时刻：内表容量为100000

通常使用什么算法或方法来进行hashcode->内表索引转换？如何为他们解决表大小调整问题？

Answer 1

通常，一个简单的模数就可以完成这项工作。

举一个维基百科的简单例子，很简单：

hash = hashfunc(key)
index = hash % array_size

正如您所说，调整大小取决于哈希图填充率。数组被重新分配（请参阅realloc()），然后在给定新数组大小的情况下重新计算索引，并将值复制到新索引。