Хеш-таблиця в структурі даних: Приклад Python

Що таке хешування?

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

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

У цьому уроці з алгоритму ви дізнаєтесь:

• Що таке хешування?
• Що таке хеш-таблиця?
• Хеш-функції
• Якості гарної хеш-функції
• Зіткнення
• Операції хеш-таблиці
• Приклад Python хеш-таблиці
• Пояснення коду хеш-таблиці
• Приклад словника Python
• Аналіз складності
• Реальні програми
• Переваги хеш-таблиць
• Недоліки хеш-таблиць

Що таке хеш-таблиця?

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

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

Хеш-функції

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

Ми можемо використовувати номер працівника як ключ і призначити дані працівника як значення.

Вищезазначений підхід вимагатиме додаткового вільного місця порядку (m * n ² ), де змінна m - розмір масиву, а змінна n - кількість цифр для номера працівника. Цей підхід створює проблему простору зберігання.

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

Далі наведено приклад простої хеш-функції

h(k) = k1 % m

ТУТ,

• h (k) - хеш-функція, яка приймає параметр k. Параметр k - це значення, для якого ми хочемо обчислити ключ.
• k ₁ % m - алгоритм нашої хеш-функції, де k1 - значення, яке ми хочемо зберегти, а m - розмір списку. Для обчислення ключа ми використовуємо оператор модуля.

Приклад

Припустимо, що у нас є список із фіксованим розміром 3 та наступними значеннями

[1,2,3]

Ми можемо використовувати наведену вище формулу для обчислення позицій, які має займати кожне значення.

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

Крок 1)

Обчисліть позицію, яку буде займати перше значення приблизно так

h (1) = 1% 3

= 1

Значення 1 займе простір в індексі 1

Крок 2)

Обчисліть позицію, яку займе друге значення

h (2) = 2% 3

= 2

Значення 2 займе пробіл в індексі 2

Крок 3)

Обчисліть позицію, яку займе третє значення.

h (3) = 3% 3

= 0

Значення 3 займе пробіл в індексі 0

Остаточний результат

Тепер наша заповнена хеш-таблиця буде такою.

Якості гарної хеш-функції

Хороша хеш-функція повинна мати такі якості.

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

Зіткнення

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

Давайте розглянемо приклад.

Припустимо, у нас є наступний перелік значень

[3,2,9,11,7]

Припустимо, що розмір хеш-таблиці дорівнює 7, і ми будемо використовувати формулу (k ₁ % m), де m - розмір хеш-таблиці.

У наступній таблиці наведено хеш-значення, які будуть створені.

Ключ	Алгоритм хешу (k 1 % м)	Хеш-значення
3	3% 7	3
2	3% 7	2
9	3% 7	2
11	3% 7	4
7	3% 7	0

Як ми бачимо з наведених вище результатів, значення 2 і 9 мають однакове хеш-значення, і ми не можемо зберігати більше одного значення в кожній позиції.

Дану проблему можна вирішити, використовуючи ланцюжок або зондування. У наступних розділах детально обговорюється ланцюжок та зондування.

Мережа

Прив’язка - це техніка, яка використовується для вирішення проблеми зіткнення за допомогою пов’язаних списків, кожен із яких має унікальні індекси.

Наступне зображення візуалізує, як виглядає ланцюговий список

І 2, і 9 займають один і той же індекс, але вони зберігаються як зв’язані списки. Кожен список має унікальний ідентифікатор.

Переваги ланцюгових списків

Нижче наведено переваги ланцюгових списків:

• Прив’язані списки мають кращу ефективність при вставці даних, оскільки порядок вставки - O (1).
• Не потрібно змінювати розмір хеш-таблиці, яка використовує ланцюговий список.
• Він може легко вмістити велику кількість значень, якщо є вільний простір.

Зондування

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

Нижче наведені методи зондування:

Метод	Опис
Лінійне зондування	Як і випливає з назви, цей метод здійснює пошук порожніх слотів лінійно, починаючи з положення, де сталося зіткнення і рухаючись вперед. Якщо кінець списку досягнуто і порожній слот не знайдено. Зондування починається на початку списку.
Квадратичне зондування	Цей метод використовує квадратичні поліноміальні вирази, щоб знайти наступний вільний слот.
Подвійне хешування	Цей метод використовує алгоритм вторинної хеш-функції для пошуку наступного вільного слота.

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

Операції хеш-таблиці

Ось такі операції підтримуються таблицями хешу:

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

Вставка операції з даними

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

Пошук операції з даними

Операція пошуку використовується для пошуку значень у хеш-таблиці з використанням номера індексу. Операція пошуку повертає значення, пов’язане з номером індексу пошуку. Наприклад, якщо ми зберігаємо значення 6 в індексі 2, операція пошуку з індексом No 2 поверне значення 6.

Операція видалення даних

Операція видалення використовується для видалення значення з хеш-таблиці. Для видалення Операція виконується за номером індексу. Після видалення значення номер індексу стає вільним. Його можна використовувати для зберігання інших значень за допомогою операції вставки.

Реалізація хеш-таблиці на прикладі Python

Давайте розглянемо простий приклад, який обчислює хеш-значення ключа

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Пояснення коду хеш-таблиці

ТУТ,

1. Визначає функцію hash_key, яка приймає ключ параметрів і m.
2. Використовує просту операцію модуля для визначення хеш-значення
3. Визначає змінну m, яка ініціалізується до значення 7. Це розмір нашої хеш-таблиці
4. Обчислює та друкує хеш-значення 3
5. Обчислює та друкує хеш-значення 2
6. Обчислює та друкує хеш-значення 9
7. Обчислює та друкує хеш-значення 11
8. Обчислює та друкує хеш-значення 7

Виконання наведеного вище коду дає такі результати.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Приклад словника Python

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

Наступний приклад показує, як можна використовувати тип даних словника в python 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

ТУТ,

1. Визначає словникову змінну співробітник. Назва ключа використовується для зберігання значення John Doe, віку зберігає 36 років, а позиція зберігає значення Business Manager.
2. Отримує значення імені ключа та друкує його в терміналі
3. Оновлює значення позиції ключа до значення Software Engineer
4. Друкує значення імені та позиції ключів
5. Видаляє всі значення, які зберігаються в нашій словниковій змінній співробітник
6. Друкує вартість працівника

Запуск вищезазначеного коду дає такі результати.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Аналіз складності

Хеш-таблиці мають середню часову складність O (1) у найкращому випадку. Найгірший часовий складність - O (n). Найгірший сценарій трапляється, коли багато значень генерують один і той же хеш-ключ, і нам доводиться вирішувати зіткнення шляхом зондування.

Реальні програми

У реальному світі хеш-таблиці використовуються для зберігання даних для

• Бази даних
• Асоціативні масиви
• Набори
• Кеш пам'яті

Переваги хеш-таблиць

Ось плюси / переваги використання хеш-таблиць:

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

Недоліки хеш-таблиць

Ось мінуси використання хеш-таблиць:

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

Короткий зміст:

• Хеш-таблиці використовуються для зберігання даних за допомогою пари ключів і значень.
• Хеш-функція використовує математичний алгоритм для обчислення хеш-значення.
• Зіткнення відбувається, коли одне і те ж хеш-значення генерується для більш ніж одного значення.
• Мережа вирішує колізію, створюючи зв’язані списки.
• Зондування вирішує колізію, знаходячи порожні слоти в хеш-таблиці.
• Лінійне зондування шукає наступний вільний слот, щоб зберегти значення, починаючи з слота, де сталося зіткнення.
• Квадратичне зондування використовує поліноміальні вирази, щоб знайти наступний вільний слот при зіткненні.
• Подвійне хешування використовує алгоритм вторинної хеш-функції, щоб знайти наступний вільний слот при зіткненні.
• Хеш-таблиці мають кращу продуктивність у порівнянні з іншими структурами даних.
• Середня часова складність хеш-таблиць становить O (1)
• Словниковий тип даних у python є прикладом хеш-таблиці.
• Хеш-таблиці підтримують операції вставки, пошуку та видалення.
• Нульове значення не може використовуватися як значення індексу.
• У хеш-функціях не можна уникнути зіткнень. Хороша хеш-функція мінімізує кількість зіткнень, що виникають для покращення продуктивності.