java数组的查找时间复杂性与存储方式

Question

众所周知，按索引访问数组的时间复杂度为O（1）

Java的ArrayList文档由一个数组支持，它的get操作也是如此：

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.

查找是通过获取给定索引处元素的内存地址来完成的，该地址与数组的大小无关（类似于start_address + element_size * index）。我的理解是，为了使这种查找机制成为可能，数组的元素必须在内存中彼此相邻地存储

但是，从this question开始，我了解到Java中的数组不能保证其元素连续存储在内存中。如果是这样的话，它怎么可能总是O（1）

---

编辑：我很清楚ArrayList是如何工作的。我的观点是，如果JVM规范不能保证阵列的连续存储，那么它的元素可能位于内存中的不同区域。尽管这种情况不太可能发生，但它会使上述查找机制变得不可能，并且JVM将有另一种方式来进行查找，这种方式不应该再是O（1）。在这一点上，这既违背了本问题顶部所述的常识，也违背了ArrayList关于其get操作的文件

谢谢大家的回答

---

编辑：最后，我认为这是一个特定于JVM的东西，但大多数JVM（如果不是全部的话）都坚持使用数组元素的连续存储，即使没有保证，这样就可以使用上面的查找机制。它简单、高效、经济

就我所见，将元素存储在所有位置，然后必须采用不同的方法进行查找是愚蠢的

Answer 1

从链接的问题中，您可以看到，尽管JVM规则没有强制执行1D数组，但1D数组在内存中很可能是连续的

给定一个连续数组，ArrayList的时间复杂度如下所示。然而，在特殊情况或特殊JVM中，复杂性可能略有不同，这并非不可能。如果你必须考虑S.

允许的各种VM，就不可能提供时间复杂度。

Answer 2

据我所知，规范并不能保证数组将被连续存储。我推测大多数JVM实现将。在基本情况下，它非常简单，可以强制执行：如果因为其他内存占用了您所需的空间而无法扩展阵列，请将整个阵列移动到其他位置

你的困惑源于对O（1）的含义的误解。O（1）并不意味着在单个操作（例如^{）中执行功能。这意味着无论输入数据的大小（在本例中为数组），操作都是在恒定的时间内执行的。对于不连续存储的数据，这是完全可以实现的。例如，可以使用一个查找表将索引映射到内存位置

Answer 3

每次添加元素时，都会检查其容量： http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/ArrayList.java#ArrayList.add%28java.lang.Object%29

public boolean add(E e) {
   ensureCapacity(size + 1);  // Increments modCount!!
   elementData[size++] = e;
   return true;
}

在这里，ensureCapacity()执行保持数组顺序的技巧。怎样 http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29

public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
           Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
           newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

因此，在每个阶段，它都试图确保数组具有足够的容量，并且是线性的，即范围内的任何索引都可以在O（1）中检索

Answer 4

ArrayList包装一个实数组。（在add上，它可能需要增长。）因此get和set，O（1）具有相同的复杂性

但是，ArrayList只能包含对象（直到Java的未来版本）。对于像int或char这样的基本类型，需要效率低下的包装类，并且在整个分配的内存中无序地划分对象。仍然是O（1），但具有较大的常数因子

因此，对于基本类型，您可以使用数组并自己进行扩展：

    elementData = Arrays.copyOf(elementData, newCapacity);

或者，如果合适，使用位集，其中带true的索引是值