multithreading - 设计一个hash_table，应该注意几个方面？

Question

我有一些候选方面:

1. 哈希函数很重要，哈希码要尽可能唯一。
2. 后端数据结构很重要，查找、插入和删除操作的时间复杂度都应该是O(1)。
3. 内存管理很重要，每个哈希表条目的内存开销应该尽可能少。当 hash_table 扩大时，内存应该有效地增加，而当 hash_table 缩小时，内存应该有效地进行垃圾收集。而有了这些内存操作，aspect 2 也应该是满满的。
4. 如果哈希表将在多线程中使用，它应该是线程安全的并且是高效的。

我的问题是:

1. 还有什么值得关注的方面吗？
2. 如何设计hash_table来满填这些方面？
3. 有什么资源可以引用吗？

非常感谢!

阅读一些 Material 后，更新我的问题。 :)

---

在一本解释SGI STL源代码的书中，我找到了一些有用的信息:

1. 后端数据结构是链表的桶。在 hash_table 中搜索、插入或删除一个元素时:
   1. 使用哈希函数计算桶中对应的位置，元素存储在此位置之后的链表。
   2. 当elements的尺寸大于buckets的尺寸时，buckets需要resize:将尺寸扩大到比旧尺寸大 2 倍。桶的大小应该是 prime。然后复制旧的桶和元素到新的。
   3. 当elements的数量远小于buckets的数量时，我没有找到垃圾回收的逻辑>。但我认为当许多 inserts 开始然后许多 deletes 时，应该考虑这个逻辑。
2. 其他数据结构如数组线性检测或方 block 检测不如链表。
3. 一个好的哈希函数可以避免簇，双重哈希可以帮助解决簇。

关于multi_threads 的问题仍然悬而未决。 :D

---

Answer 1

有两个(稍微)正交的关注点。

虽然哈希函数显然很重要，但通常您将后端的设计与哈希函数的设计分开:

• 哈希函数取决于要存储的数据
• 后端取决于存储的要求

对于哈希函数，我建议阅读 CityHash或 MurmurHash (带有 explanation on SO )。

如您所述，对于后端，存在各种问题。一些评论:

• 我们说的是平均复杂度还是最坏情况复杂度？没有完美的散列，据我所知几乎不可能实现 O(1)，尽管最坏情况下的频率和复杂性可以大大降低。
• 我们是在谈论摊销的复杂性吗？摊销的复杂性通常以“尖峰”为代价提供更好的吞吐量。以稍微降低吞吐量为代价的线性重新散列将为您提供更平滑的曲线。
• 关于多线程，请注意读/写模式可能会影响解决方案，考虑到极端情况，1 个生产者和 99 个读者与 99 个生产者和 1 个读者非常不同。一般来说，写入更难并行化，因为它们可能需要修改结构。在最坏的情况下，它们可能需要序列化。
• 垃圾收集在分摊情况下非常微不足道，使用线性重新散列会稍微复杂一些，但可能是难度最小的部分。

您从未谈论过您将要使用的数据量。写入者可以更新不同的桶而不会互相干扰，所以如果你有很多数据，你可以尝试分散它们以避免争用。

引用资料:

• article on Wikipedia公开了许多不同的实现，总能很好地了解多样性
• 这GoogleTalk来自 Cliff 博士(Azul Systems)的文章展示了一个用 Java 为大量多线程系统设计的哈希表。