是否有O(1)随机访问数据结构不依赖于连续存储？

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

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

有这样的事吗？

怎么样特里结构,其中键的长度被限制在一定含量的不同K(例如,4个字节因此可以使用32位的整数作为索引).然后查找时间将是O(K),即具有非连续存储器的O(1).对我来说似乎很合理.

回想一下我们的复杂性类,不要忘记每个大O都有一个常数因子,即O(n)+ C,这种方法肯定会比真正的数组有更大的C.

编辑:实际上,现在我想起来,它是O(K*A),其中A是"字母"的大小.每个节点必须有一个最多A个子节点的列表,这些节点必须是一个链表才能保持实现不连续.但是A仍然是不变的,所以它仍然是O(1).