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 对于整数键来说应该是最快的。