Какая скорость чтения элемента в Set?

Какая скорость чтения элемента в Set?

Set в Java — это коллекция уникальных элементов. Скорость чтения (поиска) зависит от реализации Set. Разберу все основные реализации с их сложностью.

HashSet — O(1) в среднем

HashSet использует хеш-таблицу внутри. Это самый быстрый Set для операций чтения.

import java.util.HashSet;
import java.util.Set;

public class HashSetSpeed {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        
        // Добавляем 1 000 000 элементов
        for (int i = 0; i < 1_000_000; i++) {
            set.add("item" + i);
        }
        
        // Поиск элемента
        long startTime = System.nanoTime();
        boolean contains = set.contains("item500000");
        long endTime = System.nanoTime();
        
        System.out.println("HashSet contains: " + contains);
        System.out.println("Time: " + (endTime - startTime) + " ns");
        // Типичное время: 100-500 нанолсекунд (почти мгновенно)
    }
}

Сложность операций в HashSet:

Операция        | Средняя | Худшая   | Примечание
────────────────────────────────────────────────────────────
contains(elem)  | O(1)    | O(n)     | O(n) только при плохой хеш-функции
add(elem)       | O(1)    | O(n)     | С resize: O(n) редко
remove(elem)    | O(1)    | O(n)     | Как contains()
iterator()      | O(1)    | -        | Доступ к первому элементу

TreeSet — O(log n)

TreeSet использует красно-чёрное дерево (Red-Black Tree). Медленнее, чем HashSet, но элементы отсортированы.

import java.util.TreeSet;
import java.util.Set;

public class TreeSetSpeed {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        
        for (int i = 0; i < 1_000_000; i++) {
            set.add("item" + String.format("%07d", i));
        }
        
        // Поиск элемента
        long startTime = System.nanoTime();
        boolean contains = set.contains("item0500000");
        long endTime = System.nanoTime();
        
        System.out.println("TreeSet contains: " + contains);
        System.out.println("Time: " + (endTime - startTime) + " ns");
        // Типичное время: 5000-50000 нанолсекунд (медленнее, чем HashSet)
    }
}

Сложность операций в TreeSet:

Операция        | Время     | Примечание
──────────────────────────────────────────
contains(elem)  | O(log n)  | На одну операцию дольше, чем HashSet
add(elem)       | O(log n)  | Нужна балансировка дерева
remove(elem)    | O(log n)  | Со сложной переиндексацией
first()         | O(1)      | Левый узел (минимум)
last()          | O(1)      | Правый узел (максимум)
headSet(elem)   | O(log n)  | Все элементы < elem

LinkedHashSet — O(1)

LinkedHashSet — это HashSet с сохранением порядка вставки. Скорость такая же, как HashSet.

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetSpeed {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();
        
        set.add("zebra");
        set.add("apple");
        set.add("banana");
        
        // Итерация в порядке вставки
        for (String item : set) {
            System.out.println(item);
        }
        // Output:
        // zebra (первым добавлен)
        // apple
        // banana
        
        // Поиск O(1) как в HashSet
        System.out.println(set.contains("apple")); // true, очень быстро
    }
}

Сравнительная таблица скоростей

Set реализация | contains() | add()  | remove() | Сортирован | Порядок
───────────────────────────────────────────────────────────────────────────
HashSet        | O(1) ☆☆☆  | O(1)   | O(1)     | Нет       | Случайный
LinkedHashSet  | O(1) ☆☆☆  | O(1)   | O(1)     | Нет       | Вставки
TreeSet        | O(log n)   | O(log) | O(log n) | Да        | Сортиров.
CopyOnWriteSet | O(n)       | O(n)   | O(n)     | Нет       | Безопасн.

Практический бенчмарк

import java.util.*;

public class SetPerformanceBenchmark {
    static class BenchmarkResult {
        String name;
        long addTime;
        long containsTime;
        long removeTime;
    }
    
    public static void main(String[] args) {
        int size = 1_000_000;
        
        // HashSet
        BenchmarkResult hashSetResult = benchmarkSet(
            new HashSet<>(),
            "HashSet",
            size
        );
        
        // TreeSet
        BenchmarkResult treeSetResult = benchmarkSet(
            new TreeSet<>(),
            "TreeSet",
            size
        );
        
        // LinkedHashSet
        BenchmarkResult linkedSetResult = benchmarkSet(
            new LinkedHashSet<>(),
            "LinkedHashSet",
            size
        );
        
        printResults(hashSetResult, treeSetResult, linkedSetResult);
    }
    
    static BenchmarkResult benchmarkSet(Set<Integer> set, String name, int size) {
        BenchmarkResult result = new BenchmarkResult();
        result.name = name;
        
        // Измеряем добавление
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) {
            set.add(i);
        }
        result.addTime = System.nanoTime() - start;
        
        // Измеряем поиск (10000 операций)
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            set.contains(i);
        }
        result.containsTime = System.nanoTime() - start;
        
        // Измеряем удаление (10000 операций)
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            set.remove(i);
        }
        result.removeTime = System.nanoTime() - start;
        
        return result;
    }
    
    static void printResults(BenchmarkResult... results) {
        System.out.printf("%-20s | %15s | %15s | %15s\n",
            "Set Type", "Add Time (ns)", "Contains (ns)", "Remove Time (ns)");
        System.out.println("-".repeat(70));
        
        for (BenchmarkResult r : results) {
            System.out.printf("%-20s | %15d | %15d | %15d\n",
                r.name, r.addTime, r.containsTime, r.removeTime);
        }
    }
}

// Примерный output:
// Set Type            |     Add Time (ns) |  Contains (ns) |   Remove Time (ns)
// ──────────────────────────────────────────────────────────────────────────
// HashSet            |          8000000 |         10000 |          8000
// TreeSet            |         20000000 |         50000 |         30000
// LinkedHashSet      |          9000000 |         12000 |         10000

Когда использовать каждый Set

Используй HashSet когда:

// 1. Нужна максимальная скорость чтения
Set<String> userIds = new HashSet<>();
if (userIds.contains("user123")) { // Очень быстро O(1)
    // ...
}

// 2. Не нужен порядок элементов
Set<Integer> uniqueNumbers = new HashSet<>();
for (int num : largeList) {
    uniqueNumbers.add(num); // Быстрое добавление
}

// 3. Высоконагруженные системы
Set<Long> cache = new HashSet<>(10_000_000); // Лучшая производительность

Используй TreeSet когда:

// 1. Нужны отсортированные элементы
Set<String> sorted = new TreeSet<>();
for (String word : words) {
    sorted.add(word);
}
// Итерация даст элементы в алфавитном порядке

// 2. Нужны операции range
Set<Integer> scores = new TreeSet<>();
Set<Integer> highScores = ((TreeSet<Integer>) scores)
    .tailSet(90); // Все элементы >= 90, O(log n)

// 3. Нужны операции first/last
int minScore = ((TreeSet<Integer>) scores).first();
int maxScore = ((TreeSet<Integer>) scores).last();

Используй LinkedHashSet когда:

// 1. Нужен порядок вставки
Set<String> insertionOrder = new LinkedHashSet<>();
insertionOrder.add("first");
insertionOrder.add("second");
insertionOrder.add("third");

for (String item : insertionOrder) {
    System.out.println(item);
}
// Output: first, second, third (в порядке добавления)

// 2. Нужна скорость, но также порядок
Set<String> cacheWithOrder = new LinkedHashSet<>(16, 0.75f, true);
// LRU (Least Recently Used) кеш

Оптимизация с помощью инициализации

// ❌ Медленно: множество resize'ов
Set<String> set = new HashSet<>();
for (String item : millionItems) {
    set.add(item); // Множество раз расширяется
}

// ✅ Быстро: задаём начальный размер
int capacity = (int) (millionItems.size() / 0.75) + 1;
Set<String> set = new HashSet<>(capacity);
for (String item : millionItems) {
    set.add(item); // Нет resize'ов
}

Многопоточная работа со Set

// ❌ Плохо: HashSet не потокобезопасен
Set<String> notSafe = new HashSet<>();
// Из разных потоков может быть гонка

// ✅ Хорошо: Collections.synchronizedSet()
Set<String> safe = Collections.synchronizedSet(new HashSet<>());
// Потокобезопасен, но медленнее

// ✅ Лучше: ConcurrentHashMap-based Set
Set<String> concurrent = ConcurrentHashMap.newKeySet();
// Высокая параллелизм для чтения

Best Practices

1. HashSet по умолчанию — самый быстрый
2. TreeSet если нужна сортировка
3. Указывай начальный размер при создании
4. Не путай Set с List — Set для уникальности, List для порядка
5. Используй конкурентные версии в многопоточных приложениях

В production коде я обычно использую HashSet для кешей и проверки принадлежности, TreeSet для отсортированных данных, и ConcurrentHashMap.newKeySet() для многопоточных систем.