Цикл статей: Алгоритмы, изучение, примеры на C и Python, нюансы использования

Если ты хочешь мгновенный доступ к данным по ключу, — забудь про списки и переборы.​

Что такое хеш-таблица?​

• хранит пары ключ → значение
• ищет, вставляет и удаляет за O(1) в среднем
• основана на хеш-функции — преобразовании ключа в индекс массива

⚙ Как работает​

Если два разных ключа попали в одно и то же место — это коллизия.
Её решают с помощью цепочек (списки внутри массива) или открытой адресации

Нажмите, чтобы раскрыть...

Пример на Python (встроенный dict)​

# Создание хеш-таблицы
table = {}

# Вставка
table["user42"] = "Alice"
table["user17"] = "Bob"

# Чтение
print(table["user42"])  # Alice

# Удаление
del table["user17"]

Простейшая реализация хеш-таблицы на Python​

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

Простая хеш-таблица на C (цепочки)​

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

#define SIZE 10

typedef struct Item {
    char* key;
    char* value;
    struct Item* next;
} Item;

Item* table[SIZE];

int hash(const char* key) {
    int sum = 0;
    while (*key) sum += *key++;
    return sum % SIZE;
}

void put(const char* key, const char* value) {
    int idx = hash(key);
    Item* node = malloc(sizeof(Item));
    node->key = strdup(key);
    node->value = strdup(value);
    node->next = table[idx];
    table[idx] = node;
}

const char* get(const char* key) {
    int idx = hash(key);
    Item* node = table[idx];
    while (node) {
        if (strcmp(node->key, key) == 0)
            return node->value;
        node = node->next;
    }
    return NULL;
}

Как устроены хорошие хеш-таблицы: правила, размер, хеш-функции​

Размер таблицы: больше — не значит лучше​

Почему размер должен быть простым или нечётным​

index = hash(key) % table_size

• Хорошо: простое число (101, 1009, 10007)
• Неплохо: нечётное число (99, 199)
• Плохо: 64, 128, 256, 512 (степени 2)

⚙ Лучшая хеш-функция — быстрая и равномерная​

• Быстрой
• Давать равномерное распределение
• Учитывать все биты ключа

unsigned long hash(const char *str) {
    unsigned long h = 5381;
    int c;
    while ((c = *str++))
        h = ((h << 5) + h) + c; // h * 33 + c
    return h;
}

• Создаём новый массив в 2× больше
• Перехешируем все ключи в новую таблицу

• Проще реализовать
• Удаление проще
• Подходят при большом количестве коллизий

• Экономия памяти (нет указателей)
• Сложнее удаление
• Работает хорошо при загрузке < 0.7

Золотые правила хеш-таблицы​

• Размер таблицы ≈ 2× записей
• Размер — простое или нечётное число
• ⚙ Хорошая хеш-функция (djb2, murmur, siphash)
• Рехешировать при загрузке > 0.7
• Продумать стратегию разрешения коллизий (цепочки или адресация)

Вывод​

• размер,
• хеш-функцию,
• коллизионную стратегию.

Где используются хеш-таблицы​

• Реализация dict, set в Python
• Поиск по ключу в словарях, индексах, БД
• Кеши и быстрый доступ к данным
• Поиск уникальных элементов и частот
• Хеширование паролей (в связке с криптографией)

Сложность операций​

В среднем — O(1), если хорошая хеш-функция и мало коллизий

Нажмите, чтобы раскрыть...

Вывод​