Как работает поиск в хеш-таблице?

Алгоритм поиска в хэш-таблице

Поиск в хэш-таблице состоит из трёх этапов: вычисление хэша, определение позиции и поиск в collision chain или по алгоритму probing.

Этапы поиска

1. Вычисление хэша ключа

size_t hash_value = hash_function(key);

2. Определение индекса (bucket'а)

size_t index = hash_value % table_size;  // или побитовое AND для степеней двойки

3. Поиск в bucket'е

• При chaining: проходим по списку элементов
• При open addressing: используем probing алгоритм

Сложность

• Лучший случай: O(1) — прямое попадание в bucket
• Средний случай: O(1 + α), где α = n/m (load factor)
• Худший случай: O(n) — все элементы в одном bucket'е (плохая хэш-функция)

Поиск при Chaining

template<typename K, typename V>
bool find_chaining(const K& key, V& value) {
    // 1. Вычислить индекс
    size_t index = hash_function(key) % table_size;
    
    // 2. Получить указатель на начало цепочки
    Entry* current = table[index];
    
    // 3. Проходим по цепочке
    while (current != nullptr) {
        if (current->key == key) {
            value = current->value;
            return true;  // Найден!
        }
        current = current->next;
    }
    
    return false;  // Не найден
}

// Сложность: O(1) в среднем, O(n) в худшем случае

Поиск при Open Addressing

Linear Probing

bool find_linear_probing(const K& key, V& value) {
    size_t index = hash_function(key) % table_size;
    size_t original_index = index;
    
    // Ищем по линейной последовательности
    while (table[index].is_occupied) {
        if (table[index].key == key) {
            value = table[index].value;
            return true;  // Найден!
        }
        
        index = (index + 1) % table_size;  // Следующая позиция
        
        if (index == original_index) {
            break;  // Полный цикл, элемента нет
        }
    }
    
    return false;  // Не найден
}

Quadratic Probing

bool find_quadratic_probing(const K& key, V& value) {
    size_t original_index = hash_function(key) % table_size;
    size_t index = original_index;
    
    for (size_t i = 1; i < table_size; i++) {
        if (!table[index].is_occupied) {
            return false;  // Пустая позиция = элемента нет
        }
        
        if (table[index].key == key) {
            value = table[index].value;
            return true;  // Найден!
        }
        
        // Квадратичный зонд
        index = (original_index + i * i) % table_size;
    }
    
    return false;  // Не найден
}

Double Hashing

bool find_double_hashing(const K& key, V& value) {
    size_t original_index = hash_function(key) % table_size;
    size_t step = hash_function2(key) % table_size;
    size_t index = original_index;
    
    for (size_t i = 0; i < table_size; i++) {
        if (!table[index].is_occupied) {
            return false;
        }
        
        if (table[index].key == key) {
            value = table[index].value;
            return true;
        }
        
        index = (index + step) % table_size;
    }
    
    return false;
}

Реальный пример: std::unordered_map

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> map;
    
    map["Alice"] = 30;
    map["Bob"] = 25;
    map["Charlie"] = 35;
    
    // Поиск
    auto it = map.find("Bob");
    if (it != map.end()) {
        std::cout << "Found: " << it->second << std::endl;  // 25
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // Или через operator[]
    std::cout << map["Alice"] << std::endl;  // 30
    std::cout << map["David"] << std::endl;  // Создаст новый элемент = 0
}

Оптимизация: Probe Sequence Analysis

// Проблема: clustering при linear probing
// Если первые элементы заняты, следующие ищут долго

hash_function(key) -> 5

table: [_, _, _, 5, 6, 6, 6, 7, _, _]
//                  ^search starts
//          cluster of collisions

// Quadratic probing менее подвержен clustering
// Double hashing ещё лучше

Практическая реализация

template<typename K, typename V>
class SimpleHashMap {
private:
    static constexpr int TABLE_SIZE = 16;
    
    struct Entry {
        K key;
        V value;
        bool occupied = false;
    };
    
    Entry table[TABLE_SIZE];
    
public:
    bool find(const K& key, V& result) {
        size_t h = std::hash<K>{}(key) % TABLE_SIZE;
        size_t step = 1;
        size_t pos = h;
        
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (!table[pos].occupied) {
                return false;  // Пустая позиция = нет элемента
            }
            
            if (table[pos].key == key) {
                result = table[pos].value;
                return true;  // Найден!
            }
            
            pos = (pos + step) % TABLE_SIZE;
        }
        
        return false;  // Таблица полностью проверена
    }
};

int main() {
    SimpleHashMap<int, std::string> map;
    // insert...
    // std::string value;
    // if (map.find(42, value)) { }
}

Влияние Load Factor на поиск

// Load factor α = n / m (элементы / размер таблицы)

// α = 0.25: быстро, мало коллизий
// Среднее проб: ~1.15

// α = 0.50: нормально
// Среднее проб: ~1.5 (linear probing)

// α = 0.75: медленнее
// Среднее проб: ~3.3 (linear probing)

// α = 0.90: очень медленно
// Среднее проб: ~9.5 (linear probing)

// При α > threshold — нужен rehash!

Поиск с удалённым элементом

// При open addressing нельзя просто удалять:
class Entry {
    K key;
    V value;
    bool occupied = false;
    bool deleted = false;  // Маркер удаления
};

bool find_with_deleted(const K& key, V& result) {
    size_t h = hash_function(key) % table_size;
    
    for (int i = 0; i < table_size; i++) {
        size_t pos = (h + i) % table_size;
        
        if (!table[pos].occupied && !table[pos].deleted) {
            return false;  // Пустая, не только удалённая
        }
        
        if (table[pos].occupied && table[pos].key == key) {
            result = table[pos].value;
            return true;
        }
        // if (deleted) — продолжаем поиск
    }
    
    return false;
}

Сравнение методов поиска

Лучшие практики

// 1. Хорошая хэш-функция
size_t good_hash(const std::string& s) {
    size_t hash = 0;
    for (char c : s) {
        hash = hash * 31 + c;  // Распределяет хорошо
    }
    return hash;
}

// 2. Следить за load factor
if (map.load_factor() > 0.75) {
    map.rehash(map.bucket_count() * 2);
}

// 3. Использовать find вместо operator[]
if (map.find(key) != map.end()) {  // Не создаёт новый элемент
    // ...
}

Итог

Поиск в хэш-таблице:

1. Вычислить хэш: hash_function(key)
2. Найти bucket: hash % table_size
3. Проверить элементы: в зависимости от стратегии (chaining/probing)
4. Вернуть результат: O(1) в среднем

Производительность зависит от качества хэш-функции и load factor. При α < 0.75 поиск остаётся O(1).