Какова скорость доступа к элементу в основных коллекциях Java?

Скорость доступа к элементу (по индексу или ключу) в стандартных коллекциях Java:

O(1) - Константное время:

• Массив (Array) и ArrayList - прямое обращение по индексу.
• HashMap/HashSet - в среднем, благодаря хэш-функции. В худшем случае (коллизии) O(n).

O(log n) - Логарифмическое время:

• TreeMap/TreeSet - доступ через сбалансированное бинарное дерево (красно-черное дерево).

O(n) - Линейное время:

• LinkedList - требуется последовательный проход от начала или конца.

Практический пример:

// Самый быстрый доступ по индексу
int[] array = new int[1000];
int element = array[500]; // O(1)

// Быстрый доступ по ключу (в среднем)
HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42);
Integer value = map.get("key"); // O(1) в среднем

// Медленный доступ по индексу
LinkedList<String> list = new LinkedList<>();
String item = list.get(500); // O(n) - проходит 500 узлов

Почему такая разница? ArrayList использует внутренний массив, а LinkedList — цепочку узлов, где каждый элемент знает только о соседях.