⛓️30. Хеш-таблицы. Коллизии. Способы разрешения коллизий. Метод цепочек.

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

data_1["BMSTU"] = "МГТУ"
DATA_2[3.14] = "Pi"

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

h("a") -> 1
h("b") -> 2
h("c") -> 3

//пример реализации хэш-функции
long hash_function(char* str) {
    long i = 0;
    for (int j = 0; str[j]; j++)
        i += str[j];
    return i % CAPACITY;
}

//пример структуры хэш-таблицы
typedef struct Ht_item Ht_item;
struct Ht_item {
    char* key;
    char* value;
};

Преимущества хэш-таблиц:

• Сложность алгоритма: О(n)

• Быстрый поиск

• Равномерное распределение в памяти

Недостатки хэш-таблиц:

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

Коллизия хэш-функции - получение одинакового индекса для разных ключей.

Существует 2 основных типа борьбы с коллизиями:

• Метод цепочек

• Открытая адресация ~ линейное зондирование(пробирование) ~ квадратичное зондирование(пробирование) ~ двойное хэширование

Метод цепочек

Проще понять этот метод на примере реализации при разрешении коллизий:

• на ключ 002 претендуют два значения, которые организуются в линейный список.

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

• Простыми словами: в хэш-таблице вместо ключа хранится массив ключей.

Такой метод используется в большинстве современных языков программирования(Python, Java и т.д.).