是否存在支持O(1)时间追加与读取、O(n)空间的数据结构？

完全存在满足你列出的所有性能要求的数据结构，最常用、经过工业界几十年验证的实现就是动态数组，这也是Python list、Java ArrayList、C++ std::vector 等几乎所有主流语言内置可变列表的底层结构。

性能匹配验证 #

• 元素读取：动态数组的元素存储在连续内存块上，只要传入目标元素的索引，直接通过内存基地址加固定偏移量就能定位到元素存储位置，不需要遍历或额外跳转，时间复杂度为严格O(1)。
• 元素追加：动态数组采用倍数预扩容策略实现O(1)级别的追加效率：
  1. 数组初始化时会申请一段略大于初始元素数量的连续内存作为预留空间，日常追加元素时直接往空闲预留位写入即可，单次操作是纯O(1)
  2. 当预留空间全部用完时，会申请一块长度为原数组1.5~2倍的新连续内存，将旧元素批量拷贝到新内存后再完成追加。由于每次扩容产生的拷贝开销会被后续数十次甚至上百次无需扩容的追加操作平摊，整体追加操作的均摊时间复杂度为O(1)
• 空间复杂度：动态数组除了存储n个元素本身的内存外，仅需要固定大小的额外空间存储内存基地址、当前元素长度、数组容量三个元信息，即使算上扩容预留的空闲空间，闲置内存占比始终不会超过固定阈值（比如2倍扩容时最多闲置50%的空间），整体空间复杂度为O(n)。

如果你要求追加操作的最坏情况（而非均摊）时间复杂度也达到严格O(1)，可以使用分块式动态数组的变体：将元素拆分存储在多个固定大小的独立内存块中，用一个固定开销的索引表记录每个内存块的起始地址。读取元素时先计算目标元素所在的块编号和块内偏移，查索引表拿到块地址后直接访问，全程O(1)；追加元素时仅在当前块写满时申请一个新的固定大小块挂到索引表即可，不需要迁移任何已有元素，最坏情况追加效率也是O(1)，整体空间复杂度依旧保持O(n)。

内容的提问来源于stack exchange，提问作者D.M.28