什么时候使用哈希表？

Question

在什么情况下使用哈希表可以提高性能，什么时候不能？什么情况下使用哈希表不适用？

Answer 1

在什么情况下使用哈希表可以提高性能，什么时候不能？

如果您有理由关心，请使用哈希表和您正在考虑的任何其他方式实施，通过您的实际数据，并衡量哪个表现更好。

也就是说，如果哈希表具有您需要的操作（即您不希望按排序顺序迭代它，或者将它快速与另一个哈希表进行比较），并且有数百万或更多（数十亿、数万亿...）元素，那么它可能是您的最佳选择，但很大程度上取决于哈希表的实现（尤其是封闭哈希与开放哈希的选择）、对象大小、哈希函数质量和计算成本/运行时间）、比较成本、奇数您的计算机在不同缓存级别的内存性能......简而言之：在重要的时候，即使是有根据的猜测也比测量更好的选择。

什么情况下使用哈希表不适用？

主要是什么时候：

• 输入不能被散列（例如，你得到了二进制 blob 并且不知道其中哪些位是重要的，但你确实有一个int cmp(const T&, const T&)可以用于 a的函数std::map），或者

• 可用/可能的哈希函数非常容易发生冲突，或者

• 您想避免最坏情况下的性能影响：

  • 处理大量散列冲突元素（可能是由试图使您的软件崩溃或减慢软件速度的人“设计”的）

  • 调整哈希表的大小：除非预先设置足够大（使用过多内存时可能会浪费且缓慢），否则大多数实现会时不时地超出他们用于哈希表的数组，然后分配更大的数组并复制内容：这会使导致重新散列的特定插入比正常的 O(1) 行为慢得多，即使平均值仍然是 O(1)；如果您在所有情况下都需要更一致的行为，则可以使用平衡二叉树之类的东西

• 您的访问模式非常专业（例如，经常对键在某些特定排序顺序“附近”的元素上进行操作），这样缓存效率对于将它们保持在内存附近的其他存储模型（例如桶排序元素）来说更好，即使如果您不完全依赖排序顺序进行例如迭代