除了数组之外，还有哪些支持随机访问的数据结构？
我想知道是否有任何其他数据结构支持随机访问（即：恒定的时间复杂度） 在我看来，只有数组是这样构建的。
注意：您不能在数组之上构建数据结构
I'm trying to think if there is any other data structure that support random access (i.e: constant time complexity)
It looks to me like only array is built this way.
Note: you can't build a data structure on top of array
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
哈希表还允许给定密钥进行随机访问。因此，与数组相反，它们是基于键的，而不是基于索引的，但仍然允许对给定元素进行 O(1) 访问。
Hash tables also allow random access given a key. So contrary to arrays they are key-based, not index-based, but still allow for a O(1) access to a given element.
最后这取决于你对“数组”的含义。我会告诉你，RAM 是一个大字节数组（从技术上讲是一个大字节数组加上一些重载方法来以 1、2、（几乎总是）4 和（有时）8 字节的块读取它们，但并不总是有效）好吧（或者不工作句号），如果您尝试从与该数字“未对齐”的字节开始读取）。所以一切都是建立在数组之上的。
如果“数组”只是指“我使用的语言的结构调用数组以及基于该数组的该语言的所有结构”，那么我可以简单地（在 C 代码中）
malloca内存板并以类似于数组的方式使用它（可能还可以在其上构建哈希表）。关键词是“相似”。如果有足够的虚拟地址空间，您可以使用 VirtualAlloc（在 Windows 下，在 Linux 下）使用计算机的 MMU 来模拟哈希表。它将非常昂贵且无用:-)而且我仍然认为它是另一个名称的数组（“稀疏”数组）。
In the end it depends on what you mean with "Array". I'll tell you that the RAM is a big array of bytes (technically a big array of bytes plus some overloaded methods to read them in blocks of 1, 2, (nearly always)4 and (sometimes)8 bytes that not always work well (or not work full stop) if you try to read starting from a byte "unaligned" with that number). So everything is built on top of an Array.
If by "Array" you only mean "the structure the language I'm using calls Array and all the structures of that language based on that array", then I could simply (in C code)
malloca slab of memory and use it in a manner similar to an array (and perhaps build on top of it an Hash table). The key word is "similar".Given enough Virtual Address space you could use
VirtualAlloc(under Windows,mmapunder linux) to emulate an Hash Table using the MMU of your computer. It would be quite expensive and useless :-) And I would still consider it to be an Array by another name (a "sparse" Array).我能想到列表和字典。
由于字典是键值对，因此它们对随机访问“更加”友好。
I can think of lists and dictionaries.
As dictionaries are key-value pairs, they are "more" random-access friendly.