arrays - 哈希表与排序数组 - 使用哪个？

Question

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

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

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

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

我知道这真的很普遍……但是如果我在加载数据后必须进行比搜索更多的插入呢？比插入更多的搜索怎么样？

Answer 1

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

如果相对于查找次数进行大量插入，那么排序数组可能不是一个好的选择，因为插入排序数组的开销很大(O(n) 时间)。二叉搜索树或哈希表可能适合这里。

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

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

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

希望这可以帮助!