Какая сложность операций в Hashtable?

Временная сложность операций в Hashtable

Hashtable — это одна из самых старых реализаций хеш-таблицы в Java. Рассмотрим сложность всех основных операций.

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

O(1) — в среднем (average case):

• put(key, value) — вставка элемента
• get(key) — получение значения
• remove(key) — удаление элемента
• containsKey(key) — проверка наличия ключа
• containsValue(value) — проверка наличия значения

O(n) — в худшем случае (worst case):

• put(key, value) — при множественных коллизиях хеширования
• get(key) — при множественных коллизиях хеширования
• remove(key) — при множественных коллизиях хеширования

// Пример операций в Hashtable
Hashtable<String, Integer> map = new Hashtable<>();

// O(1) average case
map.put("Alice", 25);    // Вставка
Integer age = map.get("Alice"); // Получение — O(1)
map.remove("Alice");     // Удаление — O(1)

// O(n) worst case — при плохой функции хеширования
// Если все элементы хешируются в одну ячейку

Почему это происходит?

Внутренняя структура Hashtable:

// Hashtable использует массив "buckets"
private Entry<?, ?>[] table; // Массив с ячейками
private int count;            // Количество элементов

public synchronized V put(K key, V value) {
    // 1. Вычисляем хеш код ключа O(1)
    int hash = hash(key);
    
    // 2. Находим индекс в массиве O(1)
    int index = (hash & 0x7FFFFFFF) % table.length;
    
    // 3. Ищем ключ в цепочке O(k), где k — количество коллизий
    for (Entry<K, V> e = table[index]; e != null; e = e.next) {
        if (e.hash == hash && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }
    
    // 4. Если ключа нет, добавляем новый элемент O(1)
    Entry<K, V> e = new Entry<>(hash, key, value, table[index]);
    table[index] = e;
    count++;
    
    if (count >= threshold) {
        rehash(); // O(n) — перестроение таблицы
    }
    return null;
}

Анализ сложности

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

При хорошем распределении хешей элементы равномерно распределяются по ячейкам. Каждая ячейка содержит мало элементов (в идеале 0-2).

// Хорошее распределение: мало коллизий
Hashtable<Integer, String> map = new Hashtable<>();
for (int i = 0; i < 1000; i++) {
    map.put(i, "Value_" + i); // Каждый put — O(1)
}

Worst Case (худший случай) — O(n):

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

// Плохое распределение: все в одной ячейке
class BadKey {
    @Override
    public int hashCode() {
        return 0; // Все элементы хешируются в одно значение!
    }
}

Hashtable<BadKey, String> map = new Hashtable<>();
for (int i = 0; i < 1000; i++) {
    map.put(new BadKey(), "Value_" + i); // Каждый put может быть O(n)
}

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

Операции обхода

O(n) — всегда:

• keySet() — получение множества ключей
• values() — получение коллекции значений
• entrySet() — получение множества пар ключ-значение
• Итерация по элементам

Hashtable<String, Integer> map = new Hashtable<>();
map.put("Alice", 25);
map.put("Bob", 30);

// O(n) — нужно просмотреть все элементы
for (String key : map.keySet()) {
    System.out.println(key);
}

// O(n) — нужно просмотреть все элементы
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Rehashing (перестроение таблицы)

O(n) — при необходимости расширения

Когда количество элементов превышает порог (load factor), таблица увеличивается, и все элементы перехешируются.

private void rehash() {
    int oldCapacity = table.length;
    Entry<?, ?>[] oldTable = table;

    // Новый размер в 2 раза больше
    int newCapacity = (oldCapacity << 1) + 1;
    table = new Entry[newCapacity];
    threshold = (int)(newCapacity * loadFactor);
    count = 0;

    // Перехешируем все элементы O(n)
    for (int i = oldCapacity; i-- > 0;) {
        for (Entry<K, V> old = oldTable[i]; old != null;) {
            Entry<K, V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K, V>)table[index];
            table[index] = e;
        }
    }
}

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

Хорошая производительность (O(1)):

Hashtable<Integer, String> map = new Hashtable<>();

long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    map.put(i, "Value_" + i); // O(1) в среднем
}
long end = System.currentTimeMillis();
System.out.println("Time: " + (end - start) + "ms"); // ~100ms

Плохая производительность (O(n)):

Hashtable<String, Integer> map = new Hashtable<>();

// Если создать объекты с одинаковым hashCode()
for (int i = 0; i < 1000; i++) {
    map.put("Key" + i, i); // Каждый put может быть O(n)!
}
long end = System.currentTimeMillis(); // Может занять секунды

Load Factor (коэффициент заполнения)

// Load factor по умолчанию 0.75
// Это означает: если заполнено более 75% ячеек,
// произойдёт rehashing

int capacity = 16;
int maxElements = (int)(capacity * 0.75); // 12 элементов

// После добавления 13-го элемента
// Hashtable перестроится с новым capacity = 33

Почему Hashtable устарела?

Problematic aspects:

1. Synchronized всегда — медленнее HashMap в однопоточных приложениях
2. Грубая синхронизация — весь метод заблокирован, медленнее ConcurrentHashMap
3. Плохая масштабируемость — при высокой конкурентности

// ❌ Плохо — полная синхронизация
public synchronized V put(K key, V value) {
    // Весь метод заблокирован
}

// ✅ Хорошо — сегментная синхронизация (ConcurrentHashMap)
// Только нужный сегмент заблокирован
public V put(K key, V value) {
    // Только один сегмент заблокирован
}

Вывод

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

• Average case: O(1) для put, get, remove
• Worst case: O(n) при плохом распределении хешей
• O(n) всегда для обхода элементов и rehashing

Не используй Hashtable! Используй:

• HashMap — для однопоточных приложений
• ConcurrentHashMap — для многопоточных приложений
• LinkedHashMap — если нужен порядок вставки
• TreeMap — если нужна сортировка (O(log n) операции)