Методы рехеширования

Модуль "Хеш-таблицы" • урок 2 из 4 • ~30 минут

Природа коллизий в хеш-таблицах

Когда разные ключи при вычислении хеш-функции получают один и тот же индекс в массиве, возникает конфликт, называемый коллизией. Поскольку число возможных входных ключей практически безгранично, а размер массива таблицы ограничен, коллизии математически неизбежны (следствие принципа Дирихле):

Метод цепочек (Chaining)

Это классический, наиболее надежный и интуитивно понятный способ. Массив хеш-таблицы (называемый массивом корзин или buckets) хранит не сами записи, а указатели на связные списки. Если вычисленный хеш-индекс для двух разных ключей совпадает, новый элемент просто вставляется в список, соответствующий этому индексу.

• Вставка (Insertion): в среднем выполняется за строгое время O(1), поскольку новый узел выгоднее всего добавлять прямо в голову связного списка корзины, не обходя существующие элементы. Так можно, если проверка дубликатов не требуется: сама по себе она стоит O(1 + α), потому что заставляет пройти корзину до конца.
• Поиск и удаление (Search / Deletion): требуют обхода списка внутри конкретной корзины. В среднем время составляет O(1 + α), где α - коэффициент заполнения. В аномально худшем случае, если хеш-функция выродилась и направила все ключи в одну корзину, поиск деградирует до O(N).

Открытая адресация (Open Addressing)

При открытой адресации мы полностью отказываемся от дополнительных динамических структур: все без исключения элементы хранятся непосредственно в массиве хеш-таблицы. Если при вставке ключа вычисленный индекс h оказывается уже занят другим элементом, алгоритм инициирует последовательность проб - проверяет другие ячейки таблицы по детерминированному математическому правилу до тех пор, пока не обнаружит пустой слот.

Четыре стратегии пробирования:

1. Линейное пробирование (Linear Probing): при коллизии в домашней ячейке h (так называют ячейку, куда ключ ведет напрямую по хешу) последовательно проверяются ячейки (h + 1) mod N, (h + 2) mod N и так далее по кругу. Это простейший метод, обладающий превосходной локальностью кэша процессора, но страдающий от первичной кластеризации - слияния соседних занятых ячеек в длинные "массивы-пробки", что резко увеличивает среднее число проб.
2. Квадратичное пробирование (Quadratic Probing): интервал между проверяемыми ячейками возрастает квадратично: (h + 1²) mod N, (h + 2²) mod N, (h + 3²) mod N. Это эффективно разрывает первичные кластеры, но требует тщательного выбора размера таблицы N.
3. Случайное рехеширование: к вычисленному индексу добавляется случайная величина, масштабированная под длину таблицы. Главное условие - последовательность обязана восстанавливаться при поиске, иначе положенный ключ уже не найти. Поэтому берут не настоящий случай, а псевдослучайные числа линейного конгруэнтного датчика с фиксированным начальным значением (в C это srand()). Этот метод важен как теоретический эталон: формулы в математическом блоке ниже выведены именно для него, и в сравнительной таблице он стоит эталонной строкой. На практике его вытеснило двойное хеширование, дающее то же рассеивание дешевле и без генератора.
4. Двойное хеширование (Double Hashing): шаг смещения вычисляется с помощью второй, независимой хеш-функции h₂(k). Последовательность проб имеет вид (h₁(k) + i · h₂(k)) mod N. Этот метод практически полностью устраняет как первичную, так и вторичную кластеризацию, приближая распределение к идеальному случайному пробированию.

Методы рехеширования: сравнение цепочек и открытой адресации

На иллюстрации ниже показано принципиальное различие двух архитектурных подходов: в методе цепочек корзины хранят указатели на списки, а в открытой адресации все элементы живут строго внутри массива:

Сравнительный анализ методов разрешения коллизий

Выбор оптимального метода разрешения коллизий зависит от архитектурных ограничений системы: доступной оперативной памяти, характера нагрузки (часто ли происходят удаления) и критичности кэш-промахов процессора.

Реализации на языке C

Рассмотрим индустриальные реализации обоих подходов на языке C. В коде наглядно демонстрируется управление памятью при цепочках и работа с маркерами удалений (Tombstone) при открытой адресации.

1. Реализация метода цепочек (Chaining)

В этой реализации каждая корзина таблицы содержит указатель на односвязный список. Вставка нового элемента происходит за константное время O(1) в голову списка:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// Структура узла связного списка в корзине
typedef struct Node {
    char *key;
    int value;
    struct Node *next; // Указатель на следующий элемент при коллизии
} Node;

// Структура хеш-таблицы
typedef struct {
    Node *buckets[TABLE_SIZE];
} HashTableChaining;

// Хеш-функция djb2 (Dan Bernstein)
unsigned int hash_function(const char *key) {
    unsigned long int hash = 5381;
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c
    }
    return hash % TABLE_SIZE;
}

// Инициализация таблицы
void init_table(HashTableChaining *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->buckets[i] = NULL;
    }
}

// Вставка или обновление ключа
void insert_chaining(HashTableChaining *ht, const char *key, int value) {
    unsigned int index = hash_function(key);
    Node *current = ht->buckets[index];
    
    // Проверяем, существует ли уже такой ключ в цепочке
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value; // Обновляем значение
            return;
        }
        current = current->next;
    }
    
    // Коллизия (или новая корзина): выделяем память под новый узел
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    
    // Вставляем в голову связного списка за O(1)
    new_node->next = ht->buckets[index];
    ht->buckets[index] = new_node;
}

// Поиск значения по ключу
int* search_chaining(HashTableChaining *ht, const char *key) {
    unsigned int index = hash_function(key);
    Node *current = ht->buckets[index];
    
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return &(current->value);
        }
        current = current->next;
    }
    return NULL; // Ключ не найден
}

2. Реализация открытой адресации с квадратичным рехешированием

Индустриальная реализация с открытой адресацией. Код использует размер таблицы N = 997 (простое число) и алгоритм квадратичного пробирования без операции умножения: на каждом шаге смещение d увеличивается на 2 (d = 1, 3, 5, 7...), что дает накопленные квадратичные сдвиги (1, 4, 9, 16...). В реализации полноценно поддержаны метки "удален" (tombstones):

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define N 997       // Размер таблицы обязательно должен быть простым числом!
#define WORD_LEN 64

typedef char Word[WORD_LEN];

typedef struct {
    Word key;
    size_t count;
    bool is_deleted; // Метка "удален" (tombstone) для корректного удаления
} Item_T;

typedef Item_T Table[N];

// Очистка таблицы
void table_create(Table T) {
    for (int i = 0; i < N; i++) {
        T[i].key[0] = '\0';
        T[i].count = 0;
        T[i].is_deleted = false;
    }
}

// Поиск или вставка ключа с квадратичным рехешированием
Item_T* search_or_insert_quadratic(Table T, Word key) {
    int i = 0;
    long int h = 0;
    
    // Вычисляем хеш-индекс h по методу Горнера
    while (key[i] != '\0') {
        h = (256 * h + (unsigned char)key[i]) % N;
        i++;
    }
    
    int d = 1;              // Начальный шаг пробирования
    int probes = 0;         // Счетчик попыток
    int first_tombstone = -1; // Индекс первой встреченной метки "удален"
    
    while (probes < N) {
        // 1. Нашли искомый ключ (и он не удален)
        if (!T[h].is_deleted && strcmp(T[h].key, key) == 0) {
            T[h].count++;
            return &T[h];
        }
        // 2. Встретили метку удаленного элемента (tombstone)
        else if (T[h].is_deleted) {
            if (first_tombstone == -1) {
                first_tombstone = h; // Запоминаем для переиспользования памяти
            }
        }
        // 3. Встретили абсолютно пустую ячейку - цепочка пробирования закончилась!
        else if (T[h].key[0] == '\0') {
            // Если по пути была метка удаления, вставляем в нее (оптимизация кластеров)
            int target = (first_tombstone != -1) ? first_tombstone : h;
            
            strncpy(T[target].key, key, WORD_LEN - 1);
            T[target].key[WORD_LEN - 1] = '\0';
            T[target].count = 1;
            T[target].is_deleted = false;
            return &T[target];
        }
        
        // Коллизия! Выполняем шаг квадратичного рехеширования
        // h = (h + d) % N, где d возрастает как 1, 3, 5... (дает сдвиги 1, 4, 9, 16...)
        h = (h + d) % N;
        d += 2;
        probes++;
    }
    
    printf("Ошибка: переполнение таблицы (превышен Load Factor)\n");
    return NULL;
}

// Корректное удаление с установкой метки "удален"
bool delete_key(Table T, Word key) {
    int i = 0;
    long int h = 0;
    while (key[i] != '\0') {
        h = (256 * h + (unsigned char)key[i]) % N;
        i++;
    }
    
    int d = 1, probes = 0;
    while (probes < N) {
        if (T[h].key[0] == '\0') return false; // Элемента в таблице нет
        
        if (!T[h].is_deleted && strcmp(T[h].key, key) == 0) {
            T[h].is_deleted = true; // Ставим метку "удален"!
            return true;
        }
        h = (h + d) % N;
        d += 2;
        probes++;
    }
    return false;
}