data-structures - 是否可以在不使用数组的情况下实现 O(1) 搜索的数据结构实现？

Question

我目前正在学习数据结构方面的大学类(class)，这个话题已经困扰了我一段时间(这不是家庭作业，只是一个纯粹的理论问题)。

假设您想实现一个字典。字典当然应该有一个搜索功能，接受一个键并返回一个值。

现在，我只能想象两种非常通用的方法来实现这样的事情:

使用某种搜索树，这将(总是？)给出 O(log n) 最坏情况下的运行时间，用于通过键查找值，或者，

对键进行散列，它本质上返回一个与值数组中的索引相对应的自然数，给出 O(1) 最坏情况运行时间。

是 O(1) 最坏情况 在不使用数组的情况下，搜索功能的运行时间可能吗？

是否只能通过使用数组进行随机访问？
是否可以通过使用基于指针的数据结构(如链表、搜索树等)？

在进行一些特定假设时是否有可能，例如， key 按某种顺序排列？

换句话说，你能想到一个搜索函数和字典的实现(如果可能的话)，它将接收字典中的任何键并在 O(1) 时间内返回其值，而不使用数组进行随机访问？

Answer 1

Here's another answer I made on that general subject.
本质上，算法通过处理一定数量的信息位来达到其结果。他们花费的时间长短取决于他们能多快做到这一点。

只有 2 个分支的决策点不能处理超过 1 位的信息。但是，具有 n 个分支的决策点最多可以处理 log(n) 位(基数为 2)。

我所知道的，在计算机中，可以在单个操作中处理超过 1 位信息的唯一机制是索引，无论是索引数组还是执行跳转表(索引数组)。