Откуда знаешь про время коллекций

Источники информации о сложности операций коллекций

Основные источники

1. Официальная документация Java

Первый и самый надёжный источник — Oracle JavaDoc:

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html
https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/ArrayList.html
https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/LinkedList.html

В каждом классе коллекции есть раздел "Implementation Notes", где описана временная сложность основных операций.

2. Java Collections Framework Documentation

Оффициальная документация JDK содержит подробную таблицу сложности:

ArrayList:    O(1) - get, O(n) - add, O(n) - remove
LinkedList:   O(n) - get, O(1) - add/remove (в начало/конец), O(n) - remove (в конец)
HashMap:      O(1) - get, O(1) - put, O(1) - remove (average case)
TreeMap:      O(log n) - get, O(log n) - put, O(log n) - remove
HashSet:      O(1) - add, O(1) - contains, O(1) - remove
TreeSet:      O(log n) - add, O(log n) - contains, O(log n) - remove

Почему нужно знать временную сложность

1. Выбор правильной структуры данных

// ❌ Неправильно: использование LinkedList для быстрого доступа
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 1000000; i++) {
    String element = list.get(i);  // O(n) операция!
}

// ✅ Правильно: использование ArrayList
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    String element = list.get(i);  // O(1) операция
}

2. Оптимизация алгоритмов

// ❌ O(n²) - очень медленно
for (String item : items) {
    if (linkedList.contains(item)) {  // O(n) для каждого элемента
        // ...
    }
}

// ✅ O(n) - намного быстрее
HashSet<String> itemSet = new HashSet<>(items);
for (String item : itemSet) {
    if (itemSet.contains(item)) {  // O(1)
        // ...
    }
}

3. Прогнозирование производительности

// Если у вас 10,000 элементов и вы используете LinkedList.get():
// 10,000 операций * O(n) = 10,000 * 5,000 = 50,000,000 операций
// Это может занять секунды!

LinkedList<Integer> numbers = new LinkedList<>();
// ... добавили 10,000 элементов

long start = System.nanoTime();
for (int i = 0; i < numbers.size(); i++) {
    Integer num = numbers.get(i);  // Очень медленно!
}
long end = System.nanoTime();
System.out.println("Time: " + (end - start) / 1_000_000 + " ms");

Как самостоятельно изучить сложность операций

1. Читайте source code JDK

// Установленный JDK содержит исходный код
// ~/.jdks/openjdk-21/lib/src.zip

// HashMap.get() - O(1) average case
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// ArrayList.get() - O(1)
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

// LinkedList.get() - O(n)
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  // Линейный поиск от начала или конца
}

2. Теоретические знания

Основные структуры данных и их сложность:

• Array: O(1) доступ, O(n) вставка/удаление в середину
• Linked List: O(n) доступ, O(1) вставка/удаление в начало/конец
• Hash Table: O(1) average, O(n) worst (коллизии)
• Binary Search Tree: O(log n) balanced, O(n) unbalanced
• Heap: O(log n) insert/delete, O(1) peek

3. Практическое тестирование

public class CollectionPerformanceTest {
    
    @Test
    public void compareListPerformance() {
        int size = 100_000;
        
        // ArrayList get() операции
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) arrayList.add(i);
        
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.get(i);
        }
        long arrayListTime = System.nanoTime() - start;
        
        // LinkedList get() операции
        LinkedList<Integer> linkedList = new LinkedList<>(arrayList);
        
        start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.get(i);
        }
        long linkedListTime = System.nanoTime() - start;
        
        System.out.println("ArrayList: " + arrayListTime + " ns");
        System.out.println("LinkedList: " + linkedListTime + " ns");
        System.out.println("Difference: " + (linkedListTime / arrayListTime) + "x");
    }
}
// Результат: LinkedList примерно в 1000+ раз медленнее!

Практические рекомендации

• Всегда проверяйте JavaDoc перед выбором коллекции
• Знайте Big O нотацию для основных операций
• Выбирайте коллекцию в зависимости от сценария использования:
  • Частый random access → ArrayList
  • Частые вставки/удаления в начало/конец → LinkedList
  • Частые поиски по ключу → HashMap
  • Нужна сортировка → TreeMap/TreeSet
• Пишите тесты производительности для критичных частей кода
• Помните о worst-case сценариях (например, HashMap с плохой hash-функцией)