阵列的查找时间复杂度与存储方式的关系

Question

众所周知，通过索引访问数组的时间复杂度为0(1)。

Java的ArrayList(由数组支持)的文档对其get操作也有相同的说明:

size、isEmpty、get、set、iterator和listtiterator操作在常量时间内运行。

查找是通过独立于数组大小(如start_address + element_size * index)获得给定索引处元素的内存地址来完成的。我的理解是，数组的元素必须在内存中彼此相邻存储，才能实现这种查找机制。

然而，从这个问题中，我了解到Java中的数组不能保证其元素连续存储在内存中。如果是这样，为什么总是O(1)呢?

---

编辑:我很清楚ArrayList是如何工作的。我的观点是，如果JVM规范不能保证数组的连续存储，那么数组的元素可能位于内存中的不同区域。尽管这种情况极不可能发生，但它将使上面提到的查找机制变得不可能，并且JVM将有另一种方法来执行查找，这种方法不再应该是O(1)。在这一点上，它将违反本问题顶部所述的常识和ArrayList关于其get操作的文档。

谢谢大家的回答。

---

编辑:最后，我认为这是JVM特定的事情，但大多数，如果不是全部，JVM坚持数组元素的连续存储，即使没有保证，所以上面的查找机制可以使用。这是简单、高效和经济的。

在我看来，将元素存储在各处，然后必须采用不同的方法进行查找，这将是愚蠢的。

Answer 1

据我所知，规范没有保证数组将连续存储。我推测大多数JVM实现将会。在基本情况下，执行起来很简单:如果你不能扩展数组，因为其他内存占用了你需要的空间，把整个数组移到其他地方。

你的困惑源于对O(1)的含义的误解。0(1)并不意味着在单个操作中执行一个函数(例如start_address + element_size * index)。这意味着无论输入数据(在本例中是数组)的大小如何，操作都会在恒定的时间内执行。对于不连续存储的数据，这是完全可以实现的。例如，您可以使用一个查找表将索引映射到内存位置。

Answer 2

从链接的问题中您可以看到，即使JVM规则没有强制要求，1D数组在内存中很可能是连续的。

给定一个连续数组，ArrayList的时间复杂度如下所示。但是，在特殊情况或特殊JVM中，复杂性可能略有不同，这并非不可能。如果您必须考虑规范允许的所有类型的vm，则不可能提供时间复杂性。

Answer 3

每次添加元素时，都会检查其容量:http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b27/java/util/ArrayList.java ArrayList.add % 28 java . 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 % 28 int % 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这样的基本类型，需要低效的包装器类，并且在整个分配的内存中混乱地划分对象。仍然是0(1)，但有一个很大的常数因子。

对于基本类型，你可以使用数组并自己递增:

    elementData = Arrays.copyOf(elementData, newCapacity);

或者，如果合适，使用Bitset，其中索引为true的值