Хеш-таблицы: как работают и зачем нужны

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

Тебе нужны хеш-таблицы — одна из самых быстрых структур данных.

---

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


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

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


1. Ключ (например, строка "user42") подаётся в хеш-функцию
2. Хеш-функция возвращает число (индекс) в массиве
3. Значение сохраняется в этом месте

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

---

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


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

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

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

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

🟢 Python сам обрабатывает коллизии, перестраивает таблицу при необходимости, всё это — в dict.

---

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


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 (цепочки)​


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;
}

🟢 Это примитив: нет удаления, нет расширения, но работает — и показывает суть.

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


Хеш-таблицы (hash tables) — мощная структура, но только если она правильно настроена.
Здесь разберём, какой размер таблицы выбрать, как выбрать хеш-функцию, и что такое коллизии и когда нужно рехешировать.


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


1747409082255.png


📌 Формула:
table_size ≈ 2 * num_elements

---

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


Если используешь:
Код: 
index = hash(key) % table_size

и table_size — степень двойки (например, 64, 128),
то плохая хеш-функция создаёт массовые коллизии.

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

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


Хеш-функция должна быть:
  • Быстрой
  • Давать равномерное распределение
  • Учитывать все биты ключа

✅ Пример: djb2 (C)

C: 
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;
}

---

🔁 Когда рехешировать таблицу

Показатель заполненности:
load_factor = count / table_size

Если load_factor > 0.7 — пора увеличивать таблицу.

✅ Рехеширование:
  • Создаём новый массив в 2× больше
  • Перехешируем все ключи в новую таблицу
---
🧱 Коллизии: цепочки или открытая адресация?

1747409062358.png


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

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

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

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

💬 Вывод​


Хеш-таблица даёт O(1) доступ, только если ты правильно подобрал:
  • размер,
  • хеш-функцию,
  • коллизионную стратегию.
Иначе она превращается в простой список, только более сложный и прожорливый.

---

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

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

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

1747409161998.png


В среднем — O(1), если хорошая хеш-функция и мало коллизий
Нажмите, чтобы раскрыть...

---

📎 Вывод​

Хеш-таблицы — один из мощнейших инструментов в арсенале программиста.
В задачах, где нужен быстрый доступ по ключу, они дают практически мгновенный поиск.

💬 А ты писал когда-нибудь свою хеш-таблицу или всегда использовал dict? Пиши свой опыт ниже!