Можешь ли проранжировать коллекции по скорости доступа к элементу

Ранжирование коллекций по скорости доступа к элементу

Основные коллекции и их временная сложность

Скорость доступа элемента (Big O нотация):

┌────────────────────────────┬──────────┬────────────┐
│ Коллекция                  │ Доступ   │ Вставка    │
├────────────────────────────┼──────────┼────────────┤
│ 1. Array (массив)          │ O(1)     │ O(n)       │
│ 2. ArrayList               │ O(1)     │ O(n)       │
│ 3. HashMap                 │ O(1)*    │ O(1)*      │
│ 4. ConcurrentHashMap       │ O(1)*    │ O(1)*      │
│ 5. HashSet                 │ O(1)*    │ O(1)*      │
│ 6. LinkedList              │ O(n)     │ O(1)**     │
│ 7. TreeMap                 │ O(log n) │ O(log n)   │
│ 8. TreeSet                 │ O(log n) │ O(log n)   │
│ 9. LinkedHashMap           │ O(1)*    │ O(1)*      │
│ 10. WeakHashMap            │ O(1)*    │ O(1)*      │
└────────────────────────────┴──────────┴────────────┘

* В среднем случае, O(n) в худшем
** Если у вас есть итератор на нужное место

1. САМЫЕ БЫСТРЫЕ: O(1) - Constant Time

Array (обычный массив)

public class ArrayAccessDemo {
    public static void main(String[] args) {
        int[] array = {10, 20, 30, 40, 50};
        
        // O(1) - доступ по индексу мгновенный
        int element = array[2];  // 30 (instant access)
        System.out.println("Element at index 2: " + element);
        
        // Время доступа не зависит от размера массива
        long[] bigArray = new long[1_000_000_000];
        long value = bigArray[500_000_000];  // Такой же быстрый доступ
    }
}

ArrayList

public class ArrayListAccessDemo {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        
        // O(1) - доступ по индексу быстрый
        String element1 = list.get(0);    // A (very fast)
        String element2 = list.get(3);    // D (very fast)
        String element3 = list.get(100);  // IndexOutOfBoundsException
        
        // Внутри: list.elementData[index]
    }
}

HashMap

public class HashMapAccessDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        
        // O(1) в среднем случае
        Integer age1 = map.get("Alice");  // 25 (O(1))
        Integer age2 = map.get("Bob");    // 30 (O(1))
        Integer age3 = map.get("NotFound"); // null (O(1))
        
        // Внутри: hash("Alice") -> index -> value
    }
}

HashSet

public class HashSetAccessDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        
        // O(1) проверка наличия элемента
        boolean hasApple = set.contains("Apple");      // true (O(1))
        boolean hasGrape = set.contains("Grape");      // false (O(1))
        
        // Даже с 1 миллионом элементов
        set.add("Element1");
        // ... добавить еще 999,999
        boolean found = set.contains("Element500000"); // O(1) all the same
    }
}

2. СРЕДНИЕ: O(log n) - Logarithmic Time

TreeMap

public class TreeMapAccessDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        for (int i = 1; i <= 100; i++) {
            map.put(i, "Value" + i);
        }
        
        // O(log n) доступ
        String value1 = map.get(10);    // O(log 100) ~ O(7)
        String value2 = map.get(50);    // O(log 100) ~ O(7)
        String value3 = map.get(99);    // O(log 100) ~ O(7)
        
        // Внутри: красно-черное дерево, поиск в глубину
        // Для 1 миллиона элементов: O(log 1,000,000) ~ O(20)
    }
}

TreeSet

public class TreeSetAccessDemo {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 1; i <= 1000; i++) {
            set.add(i);
        }
        
        // O(log n) проверка наличия
        boolean has500 = set.contains(500);    // O(log 1000) ~ O(10)
        boolean has999 = set.contains(999);    // O(log 1000) ~ O(10)
        
        // Сортированный доступ
        Integer first = set.first();           // O(1) - самый первый
        Integer last = set.last();             // O(1) - самый последний
        Integer floor = set.floor(500);        // O(log n) - largest <= 500
        Integer ceiling = set.ceiling(500);    // O(log n) - smallest >= 500
    }
}

3. МЕДЛЕННЫЕ: O(n) - Linear Time

LinkedList

public class LinkedListAccessDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");
        
        // O(n) доступ по индексу
        String elem0 = list.get(0);  // O(1) - первый элемент
        String elem1 = list.get(1);  // O(2) - второй
        String elem2 = list.get(2);  // O(3) - третий
        String elem4 = list.get(4);  // O(5) - последний
        
        // Внутри: проход по связному списку
        // Node current = head;
        // for (int i = 0; i < index; i++) current = current.next;
    }
}

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

public class LinkedListPerformance {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        
        // Добавляем 100,000 элементов
        for (int i = 0; i < 100_000; i++) {
            list.add(i);
            arrayList.add(i);
        }
        
        // Доступ к последнему элементу
        long start1 = System.nanoTime();
        Integer lastFromList = list.get(99_999);  // O(100,000)!
        long time1 = System.nanoTime() - start1;
        
        long start2 = System.nanoTime();
        Integer lastFromArray = arrayList.get(99_999);  // O(1)
        long time2 = System.nanoTime() - start2;
        
        System.out.println("LinkedList time: " + time1 + " ns");
        System.out.println("ArrayList time: " + time2 + " ns");
        // LinkedList может быть в 10,000 раз медленнее!
    }
}

Полная таблица сравнения

public class CollectionsComparison {
    public static void main(String[] args) {
        
        // Рейтинг по скорости доступа (лучше = 1, хуже = 10)
        String table = """
        ╔════════════════════════════════════════════════════════════════╗
        ║           СКОРОСТЬ ДОСТУПА К ЭЛЕМЕНТУ (get)                   ║
        ╠════╦═══════════════════╦═════════╦═══════════════════════════╣
        ║ # ║ Коллекция         ║ Big O   ║ Скорость относительно   ║
        ╠════╬═══════════════════╬═════════╬═══════════════════════════╣
        ║ 1 ║ Array[]           ║ O(1)    ║ ████████████████ (быстро)║
        ║ 2 ║ ArrayList         ║ O(1)    ║ ████████████████         ║
        ║ 3 ║ HashMap           ║ O(1)*   ║ ████████████████         ║
        ║ 4 ║ HashSet           ║ O(1)*   ║ ████████████████         ║
        ║ 5 ║ LinkedHashMap     ║ O(1)*   ║ ████████████████         ║
        ║ 6 ║ ConcurrentHashMap ║ O(1)*   ║ ████████████████         ║
        ║ 7 ║ WeakHashMap       ║ O(1)*   ║ ████████████████         ║
        ║ 8 ║ TreeMap           ║ O(log n)║ ████████ (средне)        ║
        ║ 9 ║ TreeSet           ║ O(log n)║ ████████                 ║
        ║10 ║ LinkedList        ║ O(n)    ║ █ (медленно)             ║
        ╚════╩═══════════════════╩═════════╩═══════════════════════════╝
        * В среднем случае
        """;
        System.out.println(table);
    }
}

Практический тест производительности

public class PerformanceTest {
    public static void main(String[] args) {
        int size = 100_000;
        
        // 1. Array
        int[] array = new int[size];
        for (int i = 0; i < size; i++) array[i] = i;
        
        // 2. ArrayList
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) arrayList.add(i);
        
        // 3. HashMap
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < size; i++) hashMap.put(i, i);
        
        // 4. TreeMap
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < size; i++) treeMap.put(i, i);
        
        // 5. LinkedList
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) linkedList.add(i);
        
        int iterations = 10_000;
        Random random = new Random();
        
        // Тест скорости
        System.out.println("=== Тест доступа к " + iterations + " случайным элементам ===");
        
        // Array
        long start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            int index = random.nextInt(size);
            int val = array[index];
        }
        long arrayTime = System.nanoTime() - start;
        System.out.println("Array:     " + arrayTime + " ns");
        
        // ArrayList
        random.setSeed(0);
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            int index = random.nextInt(size);
            int val = arrayList.get(index);
        }
        long arrayListTime = System.nanoTime() - start;
        System.out.println("ArrayList: " + arrayListTime + " ns (x" + 
                          String.format("%.1f", (double) arrayListTime / arrayTime) + ")");
        
        // HashMap
        random.setSeed(0);
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            int key = random.nextInt(size);
            Integer val = hashMap.get(key);
        }
        long hashMapTime = System.nanoTime() - start;
        System.out.println("HashMap:   " + hashMapTime + " ns (x" + 
                          String.format("%.1f", (double) hashMapTime / arrayTime) + ")");
        
        // TreeMap
        random.setSeed(0);
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            int key = random.nextInt(size);
            Integer val = treeMap.get(key);
        }
        long treeMapTime = System.nanoTime() - start;
        System.out.println("TreeMap:   " + treeMapTime + " ns (x" + 
                          String.format("%.1f", (double) treeMapTime / arrayTime) + ")");
        
        // LinkedList
        random.setSeed(0);
        start = System.nanoTime();
        for (int i = 0; i < iterations; i++) {
            int index = random.nextInt(size);
            Integer val = linkedList.get(index);
        }
        long linkedListTime = System.nanoTime() - start;
        System.out.println("LinkedList:" + linkedListTime + " ns (x" + 
                          String.format("%.1f", (double) linkedListTime / arrayTime) + ")");
    }
}

Когда использовать каждую коллекцию

public class UsageGuide {
    
    // ✅ Array: когда нужна максимальная скорость и размер фиксированный
    int[] scores = new int[100];
    scores[0] = 95;  // O(1)
    
    // ✅ ArrayList: по умолчанию для всех случаев
    List<String> names = new ArrayList<>();
    String name = names.get(0);  // O(1)
    
    // ✅ HashMap: когда нужен быстрый поиск по ключу
    Map<String, Integer> ageMap = new HashMap<>();
    Integer age = ageMap.get("John");  // O(1)
    
    // ✅ TreeMap: когда нужны отсортированные данные
    TreeMap<Integer, String> rankedItems = new TreeMap<>();
    String top1 = rankedItems.get(1);  // O(log n), но отсортировано
    
    // ⚠️ LinkedList: ТОЛЬКО если часто вставляете/удаляете в начало/конец
    LinkedList<Integer> queue = new LinkedList<>();
    queue.addFirst(10);    // O(1) в начало
    queue.removeLast();    // O(1) с конца
    queue.get(50000);      // O(n) - ПЛОХО!
}

Вывод: Рейтинг по скорости доступа

1. Array              - O(1)      ████████████████
2. ArrayList          - O(1)      ████████████████
3. HashMap            - O(1)*     ████████████████
4. HashSet            - O(1)*     ████████████████
5. LinkedHashMap      - O(1)*     ████████████████
6. ConcurrentHashMap  - O(1)*     ████████████████
7. WeakHashMap        - O(1)*     ████████████████
8. TreeMap            - O(log n)  ████████
9. TreeSet            - O(log n)  ████████
10. LinkedList        - O(n)      █

Золотое правило: Используй ArrayList для быстрого доступа по индексу, HashMap для быстрого поиска по ключу, TreeMap для отсортированных данных, и LinkedList только для частых операций вставки/удаления в начало/конец.