寻找具备O(1)访问效率、无需预指定容量的动态数组替代数据结构

首先明确核心需求：O(1)随机访问、无需预定义容量、排除动态数组和链表，以下是可行的选型：

• 开放寻址实现的哈希表
  当你使用连续整数作为键时，开放寻址实现的哈希表可以实现接近O(1)的访问效率，且不需要预定义固定容量，触发扩容时自动重哈希即可。如果你的访问是按索引顺序的，可以直接把索引作为键，访问开销几乎和数组一致。
• 页表式多层数组
  用固定大小的数组作为「页块」，上层用目录数组存储各页块的指针。比如第一层是存储指针的数组，每个指针指向一个大小为4KB的二级数组，当需要扩容时只需要新增二级数组、更新上层目录即可。随机访问时只要通过索引的高位计算页号、低位计算页内偏移，两次数组访问即可拿到数据，实践中可以认为是常数时间开销，而且不需要预先分配全部容量。
• 完美哈希表
  如果你的数据是静态的（仅读取无写入），可以预先构建完美哈希函数，实现严格O(1)的访问效率，且不需要预先分配和最大元素数匹配的连续空间，完全匹配你的使用场景。

补充说明：如果你的使用场景有频繁的随机插入/删除需求，优先选开放寻址哈希表；如果是只读的静态数据集，完美哈希表是最优选择。

内容的提问来源于stack exchange，提问作者Lisa