algorithm - 是否存在不依赖连续存储的 O(1) 随机访问数据结构？

Question

经典的 O(1) 随机访问数据结构是数组。但是数组依赖于使用的编程语言来支持有保证的连续内存分配(因为数组依赖于能够获取基的简单偏移量来查找任何元素)。

这意味着语言必须具有关于内存是否连续的语义，而不是将其作为实现细节。因此，可能需要一个具有 O(1) 随机访问但不依赖于连续存储的数据结构。

有这种事吗？

Answer 1

trie 怎么样？其中键的长度限制为某个常数 K(例如，4 个字节，因此您可以使用 32 位整数作为索引)。然后查找时间将是 O(K)，即 O(1) 与非连续内存。对我来说似乎很合理。

回想一下我们的复杂度类，不要忘记每个 big-O 都有一个常数因子，即 O(n) + C，这种方法的 C 肯定会比实际数组大得多。

编辑:实际上，现在我想起来了，它是 O(K*A)，其中 A 是“字母”的大小。每个节点必须有一个最多包含 A 个子节点的列表，该列表必须是一个链表，以保持实现不连续。但是 A 仍然是常数，所以它仍然是 O(1)。