Какая сложность поиска элемента в HashSet?

Какая сложность поиска элемента в HashSet?

Ответ: O(1) в среднем случае, но может быть O(n) в худшем случае при плохой хеш-функции или коллизиях.

Как работает HashSet

HashSet внутренне использует HashMap с hash-таблицей:

public class HashSet<E> extends AbstractSet<E> {
    private transient HashMap<E, Object> map;  // Внутренний HashMap
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    @Override
    public boolean contains(Object o) {
        return map.containsKey(o);  // Находит за O(1) в среднем
    }
}

Процесс поиска элемента:

1. Вычислить hash code объекта: hash = o.hashCode()
2. Найти индекс в таблице: index = hash % capacity
3. Перейти на bucket с индексом index
4. Найти элемент в bucket (коллизия — несколько элементов на одном индексе)
5. Вернуть результат

Временная сложность

Средний случай: O(1)

Если хеш-функция хорошо распределяет элементы и коллизий мало:

HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < 1_000_000; i++) {
    set.add(i);  // O(1) на каждое добавление
}

boolean found = set.contains(999_999);  // O(1) на поиск

Худший случай: O(n)

Если все элементы хешируются в один bucket (perfect collision):

// Плохая хеш-функция
public class BadHash {
    @Override
    public int hashCode() {
        return 1;  // ВСЕ элементы вернут 1
    }
}

HashSet<BadHash> set = new HashSet<>();
for (int i = 0; i < 1_000_000; i++) {
    set.add(new BadHash());  // O(n) на каждое добавление!
}

// Поиск: O(n)
boolean found = set.contains(new BadHash());  // Проверяет все элементы

Разница между Java 7 и Java 8+

Java 7: Linked List для коллизий

Bucket 0: -> Element1 -> Element2 -> Element3  (Linked List)
Bucket 1: -> Element4
Bucket 2: Empty

При коллизии:

1. Найти индекс за O(1)
2. Пройти по linked list за O(k), где k — количество коллизий

Результат: O(k) где k — количество элементов в bucket

Java 8+: Tree для много коллизий

Bucket 0: Red-Black Tree с элементами (если > 8 элементов)
Bucket 1: Linked List (если <= 8 элементов)
Bucket 2: Empty

Оптимизация: если в bucket становится 9+ элементов, linked list преобразуется в красно-чёрное дерево:

HashMap<Integer, Integer> map = new HashMap<>();
// Если много коллизий, linked list -> Red-Black Tree
// Поиск в дереве: O(log n) вместо O(n)

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

@Test
public void testHashSetPerformance() {
    HashSet<Integer> set = new HashSet<>();
    
    // Добавить 1 миллион элементов
    long startAdd = System.nanoTime();
    for (int i = 0; i < 1_000_000; i++) {
        set.add(i);  // O(1) в среднем
    }
    long addTime = System.nanoTime() - startAdd;
    
    // Поиск элемента
    long startSearch = System.nanoTime();
    for (int i = 0; i < 1_000_000; i++) {
        boolean found = set.contains(i);  // O(1) в среднем
        assert found;
    }
    long searchTime = System.nanoTime() - startSearch;
    
    System.out.println("Add: " + addTime + "ns");     // ~100-200ms
    System.out.println("Search: " + searchTime + "ns"); // ~50-100ms
    // Примерно одинаково — оба O(1)!
}

Сравнение с другими коллекциями

*In average case; **O(1) in end; ***With iterator

Оптимизация HashSet

1. Хорошая хеш-функция

// ПЛОХО
public class User {
    public int hashCode() {
        return name.length();  // Многие users имеют одинаковую длину имени
    }
}

// ХОРОШО
public class User {
    @Override
    public int hashCode() {
        return Objects.hash(id, name, email);  // Используй Objects.hash()
    }
}

2. Правильный capacity

// ПЛОХО: слишком много коллизий
HashSet<Integer> set = new HashSet<>(10);
for (int i = 0; i < 1_000_000; i++) {
    set.add(i);  // Будет много расширений
}

// ХОРОШО: достаточный capacity
HashSet<Integer> set = new HashSet<>(2_000_000);
for (int i = 0; i < 1_000_000; i++) {
    set.add(i);  // Меньше расширений
}

Загрузочный фактор (load factor):

• По умолчанию: 0.75 (когда 75% таблицы заполнено, происходит resize)
• Меньше = меньше коллизий, но больше памяти
• Больше = меньше памяти, но больше коллизий

3. Когда выбрать TreeSet

// Если нужна сортировка или диапазонные запросы
SortedSet<Integer> set = new TreeSet<>();
for (int i = 0; i < 1_000_000; i++) {
    set.add(i);  // O(log n)
}

// Но вернёшь элементы в отсортированном порядке
for (Integer x : set) {  // Обход в порядке
    System.out.println(x);
}

// Диапазонные операции O(log n)
NavigableSet<Integer> range = set.subSet(100_000, 100_100);

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

// 1. Используй HashSet для fast lookup
Set<String> emailSet = new HashSet<>(users.size());
for (User user : users) {
    emailSet.add(user.getEmail());  // O(1)
}

if (emailSet.contains("john@example.com")) {  // O(1)
    // ...
}

// 2. Реализуй хороший hashCode()
public class Product {
    private Long id;
    private String name;
    
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        Product other = (Product) obj;
        return Objects.equals(id, other.id) && 
               Objects.equals(name, other.name);
    }
}

// 3. Инициализируй с правильным размером
Set<String> set = new HashSet<>(expectedSize);

// 4. Если нужна сортировка — используй TreeSet
Set<String> sorted = new TreeSet<>(set);

Вывод

HashSet: O(1) в среднем, O(n) в худшем случае

Реально:

• Для корректных объектов (с хорошим hashCode и equals) → почти всегда O(1)
• Java 8+ улучшил TreeSet внутри → O(log n) даже в худшем случае
• Используй HashSet для быстрого поиска, TreeSet если нужна сортировка