我最近一直在考虑 HashMaps/Dictionaries，我意识到我对它们的实现存在差距。
从我的数据结构类中，我被告知哈希值会将键直接映射到链表存储桶向量中的位置。根据维基百科，MurmurHash 创建一个 32 位或 128 位的值。显然，该值不能直接映射到内存中的某个位置。该哈希值如何用于将基础向量中的位置分配给放置在哈希图中的对象？
阅读大卫罗宾逊的回答后，我想扩展我的问题：如果映射基于列表的基础向量的大小，那么当向量调整大小时会发生什么？
问问题
75 次
1 回答
2
通常，当生成散列的结果时，它会经过模运算N，其中N是分配的链表向量的大小。伪代码：
linked_list = lists[MurmurHash(x) % len(lists)]
linked_list.append(x)
这让实现者可以决定链表向量的长度（即，他想用多少空间效率换取时间效率），同时保持结果是伪随机的。
一个值得一提的常见替代方法是位掩码——例如，忽略除b最低有效位之外的所有位。（例如，执行该操作会x & 7忽略除 3 个最低有效位之外的所有位）。这相当于 x 模 2^b，它恰好在大多数操作系统上更快。
要回答您的第二个问题：如果必须调整向量的大小，则确实需要重新映射存储在字典中的每个值。
有一篇关于在 Python中实现字典的优秀博客文章解释了该语言如何实现其内置的哈希表（它称为字典）。在该实施中：
如果超过 2/3 的插槽正在使用，则字典会调整大小（变大）
插槽列表的大小调整为当前大小的 4 倍
旧插槽列表中的每个值都重新映射到新插槽列表。
该博客文章中描述了许多其他有用的优化；它很好地说明了实现哈希表的实际方面。
于 2012-11-07T06:19:40.243 回答