Пояснена хеш-таблиця: що це таке і як її реалізувати

Хеш-таблиця, також відома як хеш-карта, - це структура даних, яка відображає ключі до значень. Це одна частина техніки, яка називається хешування, інша з яких є хеш-функцією. Хеш-функція - це алгоритм, який виробляє індекс того, де значення можна знайти або зберегти в хеш-таблиці.

Деякі важливі примітки про хеш-таблиці:

  1. Значення не зберігаються у відсортованому порядку.
  2. Ви враховуєте можливі зіткнення. Зазвичай це робиться за допомогою техніки, яка називається ланцюгом. Мережеве з'єднання означає створення пов'язаного списку значень, ключі якого зіставляються з певним індексом.

Впровадження хеш-таблиці

Основна ідея хешування - розподілити пари ключ / значення по масиву заповнювачів або "сегментів" у хеш-таблиці.

Хеш-таблиця - це, як правило, масив пов'язаних списків. Коли ви хочете вставити пару ключ / значення, спочатку потрібно скористатися функцією хешування, щоб зіставити ключ з індексом у хеш-таблиці. Отримавши ключ, хеш-функція може запропонувати індекс, де значення можна знайти або зберегти:

index = f(key, array_size)

Це часто робиться у два етапи:

hash = hashfunc(key) index = hash % array_size

Використання цього методу hashне залежить від розміру хеш-таблиці. hashзводиться до індексу - числа від 0 до початку масиву та array_size - 1до кінця масиву - за допомогою оператора modulo (%).

Розглянемо такий рядок S:

string S = “ababcd”

Вам потрібно порахувати частоту всіх символів у S. Найпростіший спосіб зробити це - переглядати всі можливі символи і підраховувати частоту кожного, по одному.

Це працює, але це повільно - часова складність такого підходу дорівнює O (26 * N), при Nцьому розмір рядка Sпомножується на 26 можливих символів від AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Вихід:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Давайте поглянемо на рішення, яке використовує хешування.

Візьміть масив і скористайтесь хеш-функцією для хешування 26 можливих символів з індексами масиву. Потім повторіть Sі збільште значення поточного символу рядка з відповідним індексом для кожного символу.

Складність цього підходу хешування становить O (N), де N - розмір рядка.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Вихідні дані

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Хеш-зіткнення

Оскільки ваша хеш-карта, ймовірно, буде значно меншою за обсяг даних, які ви обробляєте, колізійних зіткнень не уникнути. Існує два основних підходи до вирішення колізій: ланцюгова та відкрита адресація .

Мережа

Як вже згадувалося раніше, ланцюгова ланцюг означає, що кожна пара ключ / значення в хеш-таблиці має значення пов'язаного списку даних, а не однієї комірки.

Наприклад, уявімо, що ключ 152 містить значення "Джон Сміт". Якщо значення "Сандра Ді" додано до того самого ключа, "Сандра Ді" додається як інший елемент до ключа 152, відразу після "Джон Сміт".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Основним недоліком ланцюжка є збільшення трудомісткості. Замість 0 (1), як у звичайній хеш-таблиці, кожен пошук займе більше часу, оскільки нам потрібно пройти кожен зв’язаний список, щоб знайти правильне значення.

Відкрита адресація

Відкрита адресація означає, що, як тільки значення зіставлене з ключем, який вже зайнятий, ви рухаєтеся вздовж клавіш хеш-таблиці, поки не знайдете порожнє. Наприклад, якщо "Джон Сміт" був зіставлений із 152, "Сандра Ді" буде відображена до наступного відкритого індексу:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Основним недоліком відкритої адресації є те, що під час пошуку значень вони можуть не знаходитись на ключовій карті, на яку ви їх очікуєте. Натомість вам потрібно пройти різні частини хеш-таблиці, щоб знайти значення, яке ви шукаєте.