arrays - 二分搜索与基于键的搜索

Question

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

键值:

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

排序数组:

[1, 2, 3, ...]

现在，如果我想搜索一个项目，速度会更快(以及为什么):

1. 访问 key ，例如:obj['3'] 或者，
2. 对具有 log(N) 复杂度的排序数组应用二进制搜索？

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

Answer 1

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

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

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

如果选择取决于您(例如在 C++ 中)， HashMap 对于整数键来说应该是最快的。