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

Question

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

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

有这样的事吗？

Answer 1

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

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

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

Answer 2

哈希表？

编辑：数组是O(1)查找的，因为a[i]它只是 的语法糖*(a+i)。换句话说，要获取O(1)，您需要一个直接指针或一个易于计算的指向每个元素的指针（以及您要查找的内存用于您的程序的良好感觉）。如果没有指向每个元素的指针，那么在没有连续内存的情况下，不可能有一个易于计算的指针（并且知道内存是为您保留的）。

当然，有一个哈希表实现是合理的（如果很糟糕的话），其中每个查找的内存地址根本不是*(a + hash(i))在数组中完成的，即如果您有这种控制权，则在指定的内存位置动态创建......重点是最有效的实现将是一个底层数组，但是在其他地方进行命中来执行 WTF 实现仍然可以让您进行恒定时间查找，这当然是合理的。

Edit2：我的观点是，数组依赖连续内存，因为它是语法糖，但哈希表选择数组是因为它是最好的实现方法，而不是因为它是必需的。当然，我一定是读了太多 DailyWTF 了，因为我想象着重载 C++ 的数组索引运算符，以同样的方式在没有连续内存的情况下完成它。