HashMap 通常使用存储桶的内部数组(表)实现。在通过键访问 HashMap 时,我们使用特定于键类型(特定于逻辑类型)的哈希函数获取键的哈希码。然后我们需要将哈希码映射到实际的内部桶表索引。
key -> (hash function) -> hashcode -> (???) -> index in internal table
有时内部表可能会收缩和扩展,具体取决于 HashMap 填充率。那么可能hashcode->index的转换方法可以稍微改变一下。
例如我们的哈希函数返回 32 位无符号整数值和
时刻A:内表容量为10000
时刻B:内表容量为100000
hashcode->内表索引转换通常使用什么算法或途径?他们如何解决表大小调整问题?
最佳答案
通常,一个简单的模就可以完成这项工作。
以Wikipedia中的一个简单例子为例,就这么简单:
hash = hashfunc(key)
index = hash % array_size
如您所说,调整大小取决于散列映射填充率。重新分配数组(参见 realloc() ),然后根据新数组大小重新计算索引,并将值复制到新索引。
关于algorithm - Hashmap hashcode到内表索引的转换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24555783/