具有恒定时间访问和可变大小的数据结构

Question

我在一次面试中被问到了这个问题。

是否有具有以下2种功能的数据结构：

1。恒定时间访问(随机访问)，类似于ArrayList

2。可变大小，如LinkedList

如果没有这样的数据结构，请自己创建一个。

Answer 1

我相信您正在寻找的答案是“哈希表”(见维基百科中的“哈希表”)，因为您已经评论说，他们正在寻找ArrayList之外的另一个表(请参阅：哈希表)。

尽管要注意的是，它可以是接近恒定的时间，这取决于散列算法和数据集，因为可能会发生冲突，从而导致(短)次线性搜索。Javadoc很好地解释了如何在Java实现中处理这个问题。

Answer 2

除了HashTable，正如布赖恩·罗奇所说，采访者可能暗示了LinkedHashMap或LinkedHashSet，后者为一些基本操作提供了恒定的时间表现，同时也保持了插入顺序，因为它将HashTable与双链接列表结合在一起。

换句话说，如果在键上循环，将元素放入LinkedHashMap的顺序将与检索它们的顺序相同。

但是，使用集合的一个缺点是不能有重复的，而Maps也不能有重复的键。解决办法是拥有一组列表，或者使用类似Google的多机。

但正如其他人所说，ArrayList已经满足了这两种要求。它是一个没有可变大小的数组。

此外，与ArrayList的O(n)性能相比，LinkedList相对于ArrayList的主要优势是在列表的末尾和开头都有恒定时间插入/删除。两者都可以提供可变大小。

Answer 3

http://en.wikipedia.org/wiki/Deque或者“双端队列”怎么样？在许多实现中，除了头或尾之外，对于任何位置的插入和删除，它都不会有效地改变大小，但它提供了所需的两个属性：

• 添加元素时，只会偶尔进行最小的重新分配。
• 固定时间访问，因为deque通常作为数组存储。

您在问题中提到了Java --作为标记--我必须指出，Java中的接口不提供随机访问。甚至连混凝土级都不提供它。这是一个不幸的选择，其目的是为了更抽象，并在接口上提出尽可能少的需求。

不管怎么说，除了Java之外，您还可以找到满足您所请求的属性的deque实现。