4

假设我有一组数据（未排序）要存储以便快速查找。在加载数据之前我不知道大小是多少，我应该一次加载所有数据，这样我就可以立即开始执行查找。

此外，在程序执行期间的任何时候，更多数据可能会呈现给我，以存储在我选择的数据结构中。

我应该使用哈希表还是排序数组来存储这些数据？显然，静态哈希表需要在运行时根据提供的数据大小制作 - 这是否足以成为一个缺点，我应该简单地对给我的数据进行排序，即使它是 O(NlogN) 而不是 O(否）？或者我应该考虑一些动态散列的方法？

澄清：我需要加载任意大小的数据，然后对数据执行搜索和插入，没有明确的顺序或我必须做的搜索/插入量的想法。

我知道这很笼统......但是如果我在加载数据后必须做更多的插入而不是搜索呢？搜索比插入多怎么办？

4

2 回答 2

9

这实际上取决于操作的频率。

  • 如果您相对于查找的数量做了很多插入，那么排序数组可能不是一个好的选择，因为插入排序数组很昂贵（O(n) 时间）。二叉搜索树或哈希表在这里可能是合适的。

  • 如果您相对于插入数量进行大量查找，那么排序数组可能是一个好主意，尽管哈希表可能更快。当您需要对数据进行排序以执行范围搜索或最近邻查找等操作时，排序数组通常是一个不错的选择，但如果您不需要这样做，它可能不合适。

  • 如果您的键是某些类型（整数、字符串等），您可能可以使用更具体的数据结构，如trie或van Emde Boas 树来获得额外的性能。这些有时比哈希表或排序数组更好，因为它们可以利用数据的细节。

如果你真的不知道会发生什么，我会使用哈希表作为初始实现。这不太可能是一个糟糕的选择，尽管您可以使用更精细的数据结构来代替。如果您事先不知道使用模式，则排序数组不太可能是一个好主意。

希望这可以帮助！

于 2013-03-18T20:33:52.230 回答
5

Templatetypedef 的答案是正确的，但我将添加一些关于 RedBlack Trees 的更多信息，它们为您的两个选项提供了一个很好的折衷方案。他提到了尝试和 vEB 树（以前没有听说过后者，听起来很有用！）红黑树不如这些选项最优，但可能是更通用的解决方案。当然值得研究这些更优雅的树结构选项以及列表或哈希映射。

RedBlack Tree:
Insertion: O(log n)
Key Lookup: O(log n)
Key Search: O(log n)
Iteration: O(n)

Sorted List:
Insertion: O(n log n)
Index Lookup: O(1)
Sorted Search: O(log n)
Iteration: O(n)

Hash Table:
Insertion: O(1)
Key Lookup: O(1)
Key Search: O(n)
Iteration: O(n)
于 2013-03-18T23:50:19.127 回答