设计hash_table时，要注意几个方面？

Question

我有一些候选方面：

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

我的问题是：

1. 还有哪些方面值得关注？
2. 如何设计hash_table来充分满足这些方面呢？
3. 有什么资源我可以参考吗？

非常感谢！

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

---

In a book explaining the source code of SGI STL, I found some useful informations:

1. 后端数据结构是链表的桶。当在 hash_table 中查找、插入或删除元素时：
   1. 使用哈希函数计算桶中对应的位置，并将元素存储在此位置之后的链接列表。
   2. 当元素的大小大于桶的大小时，桶需要调整大小：将尺寸扩大到旧尺寸的2倍。存储桶的大小应该是prime。然后将旧存储桶和元素复制到新存储桶和元素。
   3. 我没有找到元素数量远小于桶数量时垃圾回收的逻辑>。但我认为，当首先进行多次插入，然后进行多次删除时，应该考虑这种逻辑。
2. 其他数据结构例如具有线性检测或方形检测的数组不如链表。
3. 一个好的哈希函数可以避免簇，而双哈希可以帮助解决簇。

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

---

Answer 1

有两个（稍微）正交的问题。

虽然哈希函数显然很重要，但一般来说，您将后端的设计与哈希函数的设计分开：

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

对于哈希函数，我会建议阅读 CityHash 或 MurmurHash （带有 对 SO 的解释）。

正如您所指出的，对于后端，存在各种问题。一些评论：

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

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

参考文献：

• Wikipedia 上的文章公开了许多不同的实现，总是很高兴了解各种
• 实现GoogleTalk 展示了一个用 Java 语言设计的、专为高度多线程系统设计的哈希表。

Answer 2

我建议您阅读 http://www.azulsystems.com /blog/cliff/2007-03-26-non-blocking-hashtable

该链接指向 Cliff Click 的博客，其中有一个关于哈希函数的条目。他的一些结论是：

• 要从散列到索引，请使用二进制 AND 而不是对质数取模。这要快很多倍。您的桌子大小必须是 2 的幂。
• 对于哈希冲突，不要使用链表，将值存储在表中以提高缓存性能。
• 通过使用状态机，您可以获得非常快速的多线程实现。在他的博客文章中，他列出了状态机中的状态，但由于许可证问题，他没有提供源代码。