arrays - 除了数组，还有哪些支持随机访问的数据结构？

Question

我试图考虑是否有任何其他支持随机访问的数据结构（即：恒定时间复杂度）在我看来，只有数组是以这种方式构建的。

注意：您不能在数组之上构建数据结构

Answer 1

哈希表还允许在给定密钥的情况下进行随机访问。因此，与数组相反，它们是基于键的，而不是基于索引的，但仍然允许对给定元素进行 O(1) 访问。

Answer 2

最后，这取决于您对“数组”的含义。我会告诉你，RAM 是一个大字节数组（技术上是一个大字节数组加上一些重载方法以 1、2、（几乎总是）4 和（有时）8 个字节的块读取它们，但并不总是有效如果您尝试从与该数字“未对齐”的字节开始读取，则很好（或无法完全停止）。所以一切都建立在一个数组之上。

如果“数组”仅表示“我正在使用的语言的结构调用数组以及基于该数组的该语言的所有结构”，那么我可以简单地（在 C 代码中）malloc一块内存并在类似于数组的方式（并且可能在其之上构建一个哈希表）。关键词是“相似”。

给定足够的虚拟地址空间，您可以使用VirtualAlloc（在 Windows 下，mmap在 linux 下）使用计算机的 MMU 模拟哈希表。这将非常昂贵且无用:-)而且我仍然认为它是另一个名称的数组（“稀疏”数组）。

Answer 3

我可以想到列表和字典。由于字典是键值对，它们对随机访问“更加”友好。