Структура данных — Хеш-таблица
Хеш-таблица — это структура данных, которая сопоставляет ключи с определёнными позициями в массиве с помощью хеш-функции, тем самым обеспечивая среднюю временную сложность O(1) для операций поиска, вставки и удаления.
Хеш-функция и хеш-коллизия
Красный слот = коллизия! key=1 и key=11 отображаются в одну и ту же позицию
Хеш-функцияЦель разработки хеш-функции — преобразовывать произвольный ввод (ключи) в целое число (индекс массива) в пределах фиксированного диапазона.
Хорошая хеш-функция должна быстро вычисляться и давать равномерно распределённые результаты.
Однако, поскольку вместимость хеш-таблицы всегда ограничена,хеш-коллизии— два разных ключа, отображаемые в одну и ту же позицию, — неизбежное явление.
Методы разрешения коллизий
Метод цепочек
В каждом слоте хранится связный список; ключи, вызвавшие коллизию, добавляются в него.
Преимущества: простая реализация, простое удаление
Недостатки: накладные расходы на указатели, неоптимальное использование кэша
Коэффициент заполнения может превышать 1.0
Открытая адресация
При коллизии зондируется следующий пустой слот
Преимущества: нет указателей, кэш-дружественно
Недостатки: удаление требует ленивой пометки
Коэффициент загрузки должен быть ≤ 0.7
| Метод | Принцип | Преимущества | Недостатки |
|---|---|---|---|
| Метод цепочек | Каждый слот хранит связанный список; коллизирующие ключи добавляются в связанный список | Простая реализация, лёгкое удаление, коэффициент загрузки может быть больше 1 | Дополнительные накладные расходы на указатели, неэффективно по кэшу |
| Открытая адресация | При коллизии найдите следующий пустой слот в массиве согласно правилам пробирования | Указатели не нужны, кэш-дружественно | Сложное удаление (требуется ленивое удаление), коэффициент загрузки должен контролироваться |
При открытой адресации при удалении элемента нельзя просто очистить слот, иначе это нарушит цепочку поиска для последующих элементов. Обычный подход — использовать «ленивое удаление»: помечать позицию как «удалённую», а не «пустую».
Реализация методом цепочек
Пример
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* ёмкость хеш-таблицы */
/* узел хеш-таблицы */
struct HashNode {
int key;
int value;
struct HashNode* next; /* указатель на следующий узел в том же слоте */
};
/* хеш-функция: простой метод по модулю */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* Вставка пары ключ-значение (цепочки)
Временная сложность: O(1) в среднем, O(n) в худшем случае (все ключи отображаются в один и тот же слот) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* Вставка в начало */
table[index] = newNode;
}
/* Поиск: получить значение по ключу
Сначала вычислить хеш-значение, чтобы найти слот, затем пройти по связанному списку, чтобы найти совпадающий ключ */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* Найдено */
}
cur = cur->next;
}
return -1; /* Не найдено */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* Инициализировать все слоты пустыми */
insert(table, 1, 100); /* ключ=1, значение=100, индекс=1 */
insert(table, 2, 200); /* ключ=2, значение=200, индекс=2 */
insert(table, 11, 300); /* ключ=11, значение=300, индекс=1 — коллизия с ключом=1! */
printf("key=1 → %d\n", search(table, 1)); /* Вывод: 100 */
printf("key=2 → %d\n", search(table, 2)); /* Вывод: 200 */
printf("key=11 → %d\n", search(table, 11)); /* Вывод: 300 (метод цепочек корректно обработал коллизию) */
printf("key=99 → %d\n", search(table, 99)); /* Вывод: -1 (не найдено) */
return 0;
}
Сценарии применения
| Сценарий | Описание |
|---|---|
| Словарь/Карта | Хранение и быстрый поиск пар ключ-значение, например, dict в Python, HashMap в Java |
| Системы кэширования | Внутренняя реализация систем кэширования, таких как LRU Cache |
| Индексация баз данных | Хеш-индексация обеспечивает поиск за O(1) для запросов на равенство |
| Таблица символов компилятора | Хранит сопоставление имён переменных, имён функций и их типов |