我记住，hash如果我想编写一个要求高查找速度的应用程序，那将是我应该求助的第一件事，而任何其他数据结构都不能保证这一点。
但是当我看到很多帖子说不同的时候我很困惑，比如后缀树，特里，仅举几例。
所以我想知道hash高速查找总是最好的吗？如果我想要高查找速度和更少的空间成本怎么办？
是否有任何关于高速查找和空间效率的数据结构或算法的材料（书籍或论文） ？任何此类都受到高度赞赏。
问问题
124 次
5 回答
3
所以我想知道哈希总是高速查找的最佳选择吗？
没有。如评论中所述：
[一些通用问题]从来没有这样的事情最好的数据结构。一切都取决于大小写。尝试和基数树可能非常适合字符串，因为无论如何您都需要读取字符串。数组允许简单性和出色的缓存效率 - 通常是小规模静态信息的最佳选择
我曾经回答过一个相关问题，即树可能比哈希表更好：Hash Table v/s Trees
如果我想要高查找速度和更少的空间成本怎么办？
这两者可能是自相矛盾的。X即使对于 size的哈希表与size 的哈希表的简单示例也是如此2*X。较大的哈希表发生冲突的可能性较小，因此预计会比较小的哈希表更快。
是否有任何材料（书籍或论文）讲授有关高速查找和空间效率的数据结构或算法？
Introduction to Algorithms很好地介绍了所使用的主要数据结构。开发的任何算法都试图提供良好的空间和时间效率，但就像说的那样，有一个权衡，有些算法可能比其他算法更适合特定情况。
为特定问题选择正确的算法/数据结构/设计是工程的意义所在，不是吗？
于 2012-09-20T13:35:32.517 回答
1
只有良好的哈希实现才能为您提供良好的性能。并且您无法在所有情况下都将哈希与 Trie 进行比较。Trie 适用的情况很快，但在内存方面可能会很昂贵（再次取决于实现）。
但是你测量过性能吗？或者这是您正在寻找的不必要的优化。地图让你失望了吗？
于 2012-09-20T13:29:19.263 回答
1
我假设您在这里谈论的是字符串，答案是“否”，哈希不是查找字符串的最快或最节省空间的方法，尝试是。当然，编写散列算法比编写 trie 容易得多。
在维基百科或有关尝试的书籍中找不到的一件事是，如果您天真地用每个字母一个节点来实现它们，您最终会得到大量低效的单子节点。要进行真正消耗 CPU 的尝试，您必须实现节点，以便它们可以具有可变数量的字符。当然，这比写一个普通的 trie 更难。
我已经编写了处理超过 10 亿个条目的 trie 实现，我可以告诉你，如果处理得当，它的速度非常快，没有什么比得上的了。
尝试的另一个问题是您必须编写自定义堆，因为如果您只使用某种通用内存管理它会很慢。因此，除了实现 trie 之外，您还必须实现 trie 运行所在的堆。相当复杂，但如果你这样做，你会得到疯狂的速度。
于 2012-09-20T22:52:30.337 回答
0
这也可能取决于元素的实际数量。在复杂性理论中，散列还不错，但复杂性理论只有在元素的实际数量大于某个阈值时才是好的。
即，如果您只有 2 个元素，则有比散列更快的方法；-)
于 2012-09-20T13:24:54.853 回答
0
哈希表是一种很好的通用结构，但如果哈希函数不适合输入数据，它们可能会严重失败。最坏情况查找是 O(n)。正如您提到的，它们还浪费了一些空间。其他通用结构（如平衡二叉搜索树）的平均情况较差，但比哈希表的最坏情况性能更好。这对于实时应用程序很重要。trie 是为字符串查找量身定制的更特殊用途的结构。
于 2012-09-20T13:39:08.497 回答