类似列表的数据结构，在实践中具有 O(1) 访问权限，但在大容量情况下具有 O(N) 访问权限；它是什么？

Question

在 java.util.RandomAccess ¹ 的文档中，我看到了这个注释：

例如，某些 List 实现如果变得很大，则提供渐近线性访问时间，但实际上访问时间是恒定的。

这样的数据结构会是什么样子？显然，本文档的作者有一些想法。

我能想到的最好的事情是创建一个数组的链接列表，正如在这个问题中所讨论的那样。我想知道这是否是一个现实世界的选择，是否还有其他选择（我链接的问题甚至称其为“半措施”）

奖励积分：

1. 此类数据结构出现在哪些类型的应用中？
2. 我可以看看这个概念的一些开源实现吗？任何语言都可以。

^{[1] 一个标记接口，用于区分具有快速随机访问的列表实现。数组支持的实现可以实现它，而链表则不会。但这不是一个java问题。}

Answer 1

我不知道他们在谈论什么数据结构。但不可调整大小的基于哈希的数据结构就是一个例子。只要没有超过桶数，就平均

O(1)

。但如果元素数量较多，则平均

O(size / buckets)

，线性增长。