Почему ArrayList имеет константное время получения элемента по индексу?

Почему ArrayList обеспечивает O(1) доступ по индексу

Это фундаментальный вопрос о структурах данных и памяти в Java. Рассмотрим детально, почему это работает.

Основа: массивы в памяти

ArrayList основан на обычном массиве:

public class ArrayList<E> extends AbstractList<E> {
    // Внутри — обычный массив
    Object[] elementData;
    private int size;
    
    @SuppressWarnings("unchecked")
    public E get(int index) {
        // Просто вернуть элемент из массива — O(1)!
        return (E) elementData[index];
    }
}

Как работает адресация в массиве

Ключ к пониманию: линейное распределение памяти

Массив целиком занимает непрерывный блок памяти

База (начало) массива: 0x1000
Размер одного элемента: 8 байт (для Object ссылки на 64-bit JVM)

indexes:      0         1         2         3
Мемория:   0x1000    0x1008    0x1010    0x1018
           [obj1]    [obj2]    [obj3]    [obj4]

Математика адресации

Для доступа к элементу по индексу используется простая формула:

Адрес элемента = Базовый адрес + (индекс × размер элемента)

Например:
Получить элемент с индексом 2:
  Адрес = 0x1000 + (2 × 8 байт) = 0x1000 + 16 = 0x1010
  Загрузить значение из памяти 0x1010

Это просто математическая операция (умножение и сложение), не требующая поиска!

Пример в Java

public class ArrayAccessDemo {
    public static void main(String[] args) {
        // Создаём ArrayList
        ArrayList<String> list = new ArrayList<>(1_000_000);
        
        // Добавляем 1 млн элементов
        for (int i = 0; i < 1_000_000; i++) {
            list.add("Item " + i);
        }
        
        // Получение элемента — всегда O(1)
        long start = System.nanoTime();
        String first = list.get(0);           // Доступ к 1-му элементу
        long timeFirst = System.nanoTime() - start;
        
        start = System.nanoTime();
        String last = list.get(999_999);      // Доступ к последнему
        long timeLast = System.nanoTime() - start;
        
        System.out.println("Time for first: " + timeFirst + " ns");
        System.out.println("Time for last: " + timeLast + " ns");
        // Оба практически одинаковые! ~10-20 наносекунд
    }
}

Сравнение с LinkedList (O(n))

LinkedList имеет другую структуру:

private static class Node<E> {
    E item;
    Node<E> next;  // Ссылка на следующий элемент
    Node<E> prev;  // Ссылка на предыдущий
}

// Для получения элемента нужно пройти по цепи:
public E get(int index) {
    // Начиная с начала, пройти index шагов
    Node<E> node = getNode(index);
    return node.item;
}

private Node<E> getNode(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException();
    
    Node<E> x;
    // Оптимизация: если индекс ближе к концу, начать с конца
    if (index < (size >> 1)) {
        x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // O(n) операция!
    } else {
        x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // O(n) операция!
    }
    return x;
}

Для LinkedList получение 1-го vs 1000000-го элемента:

get(0):       1 перепрыжка → ~10 ns
get(1_000_000): 1 млн перепрыжек → миллионы ns

Сравнение производительности

public class PerformanceComparison {
    public static void main(String[] args) {
        int size = 100_000;
        
        // ArrayList
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) arrayList.add(i);
        
        // LinkedList
        LinkedList<Integer> linkedList = new LinkedList<>(arrayList);
        
        // Случайный доступ
        long start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            int randomIndex = (int) (Math.random() * size);
            int value = arrayList.get(randomIndex);
        }
        long arrayListTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            int randomIndex = (int) (Math.random() * size);
            int value = linkedList.get(randomIndex);
        }
        long linkedListTime = System.nanoTime() - start;
        
        System.out.println("ArrayList: " + arrayListTime + " ns");
        System.out.println("LinkedList: " + linkedListTime + " ns");
        System.out.println("LinkedList медленнее в " + 
                          (linkedListTime / (double) arrayListTime) + "x раз");
        // Результат: LinkedList медленнее в 100-200x раз!
    }
}

Деталь реализации в Java

// Вот реальный код ArrayList.get() из JDK
public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return elementData(index); // O(1) — просто вернуть из массива
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index]; // Это операция процессора, не итераций!
}

Сложность операций ArrayList

Сложность операций LinkedList

Визуализация памяти

ArrayList внутренняя структура:

объект ArrayList:
  ├─ elementData[] (Object[]) → указывает на массив
  ├─ size = 3
  └─ capacity = 10

Массив в памяти (непрерывно):
  Адрес          Содержимое
  0x1000      [String "A"]
  0x1008      [String "B"]
  0x1010      [String "C"]
  0x1018      [null]
  0x1020      [null]
  ...

Доступ list.get(2):
  1. Вычислить адрес: 0x1000 + (2 × 8) = 0x1010
  2. Загрузить значение из 0x1010
  3. Вернуть результат
  Всё это — несколько инструкций процессора!

CPU Cache эффект

Ещё одна причина быстродействия ArrayList:

public class CacheEffectDemo {
    static class Element {
        public long value = 0;
        public long padding1, padding2, padding3, padding4;
        public long padding5, padding6, padding7; // False sharing prevention
    }
    
    public static void main(String[] args) {
        int[] arrayAccess = new int[1000];
        int[] randomAccess = new int[1000];
        
        // Заполнить
        for (int i = 0; i < 1000; i++) {
            arrayAccess[i] = i;
            randomAccess[i] = i;
        }
        
        // Последовательный доступ (CPU cache friendly)
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100_000; i++) {
            for (int j = 0; j < 1000; j++) {
                sum += arrayAccess[j];
            }
        }
        long sequentialTime = System.nanoTime() - start;
        
        // Случайный доступ (CPU cache unfriendly)
        start = System.nanoTime();
        sum = 0;
        int[] indices = new int[1000];
        for (int i = 0; i < 1000; i++) {
            indices[i] = (int) (Math.random() * 1000);
        }
        for (int i = 0; i < 100_000; i++) {
            for (int j = 0; j < 1000; j++) {
                sum += randomAccess[indices[j]];
            }
        }
        long randomTime = System.nanoTime() - start;
        
        System.out.println("Sequential: " + sequentialTime);
        System.out.println("Random: " + randomTime);
        System.out.println("Random медленнее в " + 
                          (randomTime / (double) sequentialTime) + "x");
        // Random может быть медленнее в 10-50x из-за cache misses!
    }
}

Итог

ArrayList.get(index) — это O(1) потому что:

1. Массив в памяти занимает непрерывный блок — это основа
2. Адрес элемента вычисляется математически — это не поиск
3. Формула: baseAddress + (index × elementSize) — несколько инструкций CPU
4. CPU может закешировать соседние элементы — дополнительное ускорение
5. Не нужно перемещаться по ссылкам — как в LinkedList

Сравнение с LinkedList:

• ArrayList: одна математическая операция
• LinkedList: n переходов по ссылкам

Именно поэтому ArrayList остаётся самой универсальной коллекцией в Java!