哈希映射哈希码到内部表索引的转换

Question

Hashmaps通常使用桶的内部数组(表)来实现。在通过键访问hashmap时，我们使用键类型特定(逻辑类型特定)的hash函数获得键的hashcode。然后我们需要将hashcode映射到实际的内部桶表索引。

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

有时，内部表可能会收缩和扩展，这取决于hashmap填充率。那么可能是散列码-

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

时刻A：内表容量为10000

时刻B：内工作台容量为100000

通常使用什么算法或方法来执行哈希码-

Answer 1

我在这里和这里写了这个。

当您增加 indeces 向量的大小时，您可以确定在较短的向量上运行良好的算法在较长的向量上效果较差。可以事先进行测试，并在使矢量更长时采用新的算法。或者，随着当前向量中占用的 indeces 数量的增加，使用一个后台的低优先级线程来测试数据的不同算法。

正如我的一个答案中的例子所显示的那样，“新算法”只需要一对不同的匹配素数。

Answer 2

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

举一个维基百科的简单例子，就这么简单：

hash = hashfunc(key)
index = hash % array_size

如你所说，调整大小的发生取决于散列表的填充率。数组被重新分配(参见realloc())，然后给定新的数组大小重新计算索引，并将值复制到它们的新索引中。