Luc*_*tti 5 java arrays time-complexity
众所周知，通过索引访问数组的时间复杂度是 O(1)。
ArrayList由数组支持的 Java 的文档对其get操作也有相同的说法：
size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。
查找是通过获取给定索引处元素的内存地址来完成的，该地址与数组的大小无关（类似于start_address + element_size * index）。我的理解是数组的元素必须在内存中并排存储，这样查找机制才能成为可能。
但是，从这个问题，我了解到 Java 中的数组不能保证其元素连续存储在内存中。如果是这样，它怎么可能总是 O(1)？
编辑：我很清楚 a 是如何ArrayList工作的。我的观点是，如果 JVM 规范不保证数组的连续存储，则其元素可能位于内存中的不同区域。尽管这种情况不太可能发生，但它会使上面提到的查找机制变得不可能，并且 JVM 将有另一种方法来进行查找，不再是 O(1)。在这一点上，这既违反了这个问题顶部所述的常识，也违反了ArrayList关于其的文件get操作。
谢谢大家的回答。
编辑：最后，我认为这是一个特定于 JVM 的事情，但大多数（如果不是全部）JVM 仍然坚持数组元素的连续存储，即使没有保证，以便可以使用上面的查找机制。它简单、高效且具有成本效益。
据我所知，将元素存储在所有地方然后必须采用不同的方法进行查找是愚蠢的。
据我所知，规范不保证数组将连续存储。我推测大多数 JVM 实现都会这样做。在基本情况下，强制执行很简单：如果由于其他内存占用了您需要的空间而无法扩展数组，请将整个内容移到其他地方。
您的困惑源于对 O(1) 含义的误解。O(1) 并不意味着功能在单个操作中执行（例如start_address + element_size * index）。这意味着无论输入数据的大小如何，操作都会在恒定的时间内执行 - 在这种情况下，是数组。对于不连续存储的数据，这是完全可以实现的。例如，您可以有一个将索引映射到内存位置的查找表。