algorithm - Hashmap hashcode到内表索引的转换

Question

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

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

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

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

时刻A:内表容量为10000

时刻B:内表容量为100000

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

Answer 1

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

以Wikipedia中的一个简单例子为例，就这么简单:

hash = hashfunc(key)
index = hash % array_size

如您所说，调整大小取决于散列映射填充率。重新分配数组(参见 realloc() )，然后根据新数组大小重新计算索引，并将值复制到新索引。