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

Ответ

Какая временная сложность HashSet

HashSet - это коллекция на основе хеш-таблицы. Его временная сложность зависит от операции и качества хеш-функции.

1. Временные сложности - основные операции

2. O(1) в среднем случае - why?

HashSet работает с bucket'ами (массив списков):

HashSet внутри:
Hash code -> Index -> Bucket -> Element

Пример:
hashSet = {"John", "Jane", "Bob"}

Внутренний массив (длина 16):
[0]  -> null
[1]  -> ["Jane"]
[2]  -> null
[3]  -> ["John", "Bob"]  <- collision!
[4]  -> null
...
[15] -> null

Процесс add("Alice"):

1. Вычислить hashCode: hash = "Alice".hashCode() = 2087575550
2. Найти индекс: index = hash % 16 = 14
3. Перейти к bucket[14]
4. Добавить элемент

Это O(1) если нет collisions!

3. O(n) в худшем случае - когда?

Худший случай - когда все элементы хешируются в одно место:

// Плохой hashCode - все в одном bucket
class BadHash {
    public int hashCode() {
        return 1;  // Всегда один и тот же! O(n)
    }
}

// Если добавить 1000 элементов
Set<BadHash> set = new HashSet<>();
for (int i = 0; i < 1000; i++) {
    set.add(new BadHash());  // Все в одном bucket
}

// contains() будет O(n) - проверить все 1000!
set.contains(new BadHash());  // O(n)

4. Resizing и rehashing - important!

HashSet<Integer> set = new HashSet<>();  // capacity = 16

// Добавляем элементы
for (int i = 0; i < 17; i++) {
    set.add(i);
    // Когда size > capacity * 0.75 (load factor)
    // -> RESIZE и REHASH!
    // Это стоит O(n) один раз!
}

// Примерный процесс:
// 1. Добавляем до 12 элементов - O(1) каждый
// 2. Добавляем 13-й элемент
// 3. 13 > 16 * 0.75 (12) - TRUE
// 4. Создаём новый массив (capacity = 32)
// 5. Rehash все элементы - O(n)
// 6. Добавляем 13-й элемент - O(1)

5. Load Factor влияет на производительность

Load Factor = size / capacity

HashSet по умолчанию: 0.75

Если LF = 0.75:
  - capacity = 16 -> resize when size > 12
  - capacity = 32 -> resize when size > 24
  - Меньше collisions, больше памяти

Если LF = 0.25:
  - Очень мало collisions
  - Но тратим много памяти

6. Java код - как это работает

public class HashSetTest {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        
        // O(1) - добавление
        set.add("John");      // hashCode, поиск индекса, добавить
        
        // O(1) - поиск
        boolean exists = set.contains("John");  // hashCode, поиск
        
        // O(1) - удаление
        set.remove("John");   // hashCode, поиск, удалить
        
        // O(n) - итерация по всем
        for (String name : set) {  // Итерируем все buckets
            System.out.println(name);
        }
    }
}

7. Сравнение с другими структурами

8. LinkedHashSet - O(1) с порядком

Set<Integer> set = new LinkedHashSet<>();
set.add(3);
set.add(1);
set.add(2);

// HashSet: порядок случайный [1, 3, 2]
// LinkedHashSet: порядок вставки [3, 1, 2]

// Временная сложность - так же O(1) в среднем
// Но с дополнительным двусвязным списком для порядка

9. Практические примеры O(n) vs O(1)

// O(n) - неправильное
Set<User> users = new HashSet<>();
users.add(new User(1, "John"));
users.add(new User(2, "Jane"));

User search = new User(1, "John");
boolean found = users.contains(search);
// O(1) если equals() и hashCode() правильные
// O(n) если equals() неправильный!

// Правильный hashCode и equals
class User {
    private int 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 || getClass() != obj.getClass()) return false;
        User user = (User) obj;
        return id == user.id && Objects.equals(name, user.name);
    }
}

10. Best Practices

1. Понимай O(1) в среднем - не гарантирована, зависит от hash
2. Правильно реализуй hashCode() - распредели элементы равномерно
3. Не полагайся на порядок - если нужен порядок -> LinkedHashSet
4. Для отсортированного -> TreeSet (O(log n))
5. Помни про resizing - периодически стоит O(n)
6. hashCode() должен быть быстрым - важно для O(1)
7. Если часто ищешь -> HashSet лучше TreeSet

Краткий вывод: HashSet имеет O(1) add/remove/contains в среднем, но O(n) в худшем при плохом hashCode(). В реальности О(1) очень часто, так как hash-функции обычно хорошие.