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

Question

我在一次采访中被问到这个问题.

是否存在具有以下2种功能的数据结构:

1.持续时间访问(随机访问),如ArrayList

2.可变大小,如LinkedList

如果没有这样的数据结构,请自行创建一个.

Answer 1

我相信你正在寻找的答案是"哈希表"(参见:维基百科中的"哈希表"),因为你评论说他们正在寻找另一个超越ArrayList(对于Java,请参阅:Hashtable)

虽然可以知道它可能接近恒定时间,具体取决于散列算法和数据集,因为可能发生冲突,导致(短)次级线性搜索.Javadoc非常好地解释了如何在Java实现中处理它.