ArrayList Get Operation O(1). How?

问题:

In one of the stack overflow answers as to why ArrayList.get is O(1) and not O(n)

The responder said that ArrayList was backed by an array and a

      RangeCheck(index); 

is what determined the constant time complexity instead of linear! I'm trying to wrap my head around this, won't ANY array have to at least a partial search over perhaps a %age of n fields in an array thus constituting somehow an O(n) search ( if the element being hunted for is in the n-1 position of the array - wont this be an O(n) search? Its still a one level for loop which I thought was O(n) complexity?

回答1:

Arrays are laid sequentially in memory. This means, if it is an array of integers that uses 4 bytes each, and starts at memory address 1000, next element will be at 1004, and next at 1008, and so forth. Thus, if I want the element at position 20 in my array, the code in get() will have to compute:

1000 + 20 * 4 = 1080

to have the exact memory address of the element. Well, RAM memory got their name of Random Access Memory because they are built in such way that they have a hierarchy of hardware multiplexers that allow them to access any stored memory unit (byte?) in constant time, given the address.

Thus, two simple arithmetic operations and one access to RAM is said to be O(1).

回答2:

Posted as answer, as suggested:

ArrayList.get(int) does not search. It returns directly the element addressed by the index supplied... Exactly like with an array - hence the name.

ArrayList.get(int) source:

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

Where rangeCheck(int) is:

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

And elementData() is:

E elementData(int index) {
    return (E) elementData[index];
}

A Linked List would however have an O(n) get: it would have to step to the next element until the desired index is reached...

public E get(int index) {
    return entry(index).element;
}

Where entry(int) is (this is what makes it O(n)):

private Entry<E> More ...entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Entry<E> e = header;

    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

(Note: it is double linked list, so saves some time by selecting the endpoint that is closest to the desired result, but this is still O(n) )

回答3:

Accessing a particular index in an array is a constant time operation, because it involves getting the base memory address from the array object, and accessing the memory at base address + index multiplied by size of element type. Since all of the elements in between are skipped, the access time is bound by a constant.

The ArrayList.get(int) method is a thin wrapper over a direct array access, so it is also bounded by a constant.