二分搜索与基于键的搜索

Question

假设我有 10000 个项目，每个项目都由一个 id（1、2、3 等等）表示。此外，一个键可以是最大 10e6 的任何大数）并且我可以选择使用键值存储（ Redis，准确地说）和一个排序数组。

键值：

{
    1: 1,
    2: 2,
    3: 3 //and so on
}

排序数组：

[1, 2, 3, ...]

现在，如果我想搜索一个项目，速度会更快（以及为什么）：

或者是否有任何其他数据结构比上述两个选项更快。

Answer 1

如果域是 dense（例如 1、2、3、4、5 而不是 1、4、6、18），到目前为止最快的数据结构是简单的数组。那么对象的索引就是对象id。

如果您的域名是 small，您也可以使用它。例如，如果所有 id 都小于 100,000，您可以简单地创建一个包含 100,000 个元素的数组，并让一些值指示缺少的元素。

如果不是，那么最好的选择是键值数据结构。为此进行了优化。它可以实现为哈希映射或排序树，您可以假设您的编程语言设计者为您选择了最佳选择。

如果选择由您决定（例如在 C++ 中），哈希映射对于整数键来说应该是最快的。

Answer 2

这完全取决于您希望如何实现第一种方法，即字典。如果您决定使用散列 table，您可以获得预期的 O(1) 时间访问，但是，细节还取决于所选的实现。

注意，如果您的键不是非常大的整数，您可以使用一个简单的数组来访问它们。这样做，假设你最大的键是K，你可以用O(K)内存实现O(1)次访问。

Binary search vs key based search