Що таке хешування? Як працюють хеш-коди - на прикладах

Введення в хешування

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

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

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

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

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

Потім цей так званий хеш-код (або просто хеш) можна використовувати як спосіб звузити наш пошук при пошуку об’єкта на карті.

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

Як працює хешування

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

Хеш-таблиці повинні підтримувати 3 функції.

  • вставка (ключ, значення)
  • отримати (ключ)
  • видалити (ключ)

Суто як приклад, щоб допомогти нам зрозуміти цю концепцію, припустимо, що ми хочемо зіставити список рядкових ключів із рядковими значеннями (наприклад, зіставити список країн з їхніми столицями).

Отже, скажімо, ми хочемо зберігати дані в таблиці на карті.

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

Для простоти у нас буде два масиви: один для наших ключів і один для значень.

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

Наприклад, Куба має хеш-код (довжину) 4. Таким чином, ми зберігаємо Кубу на 4-му місці в масиві ключів, а Гавану - у 4-му індексі масиву значень тощо. І в результаті ми отримуємо наступне:

Зараз у цьому конкретному прикладі все працює досить добре. Наш масив повинен бути достатньо великим, щоб вмістити найдовший рядок, але в цьому випадку це лише 11 слотів.

Ми витрачаємо трохи місця, оскільки, наприклад, у наших даних немає ні 1-літерних ключів, ні клавіш між 8 і 10 літерами.

Але в цьому випадку марно витрачений простір теж не такий вже й поганий. Визначення довжини рядка є приємним і швидким, як і процес пошуку значення, пов’язаного з даним ключем (звичайно, швидше, ніж виконувати до п’яти порівнянь рядків).

Але що робити, якщо наш набір даних має рядок, що має більше 11 символів?

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

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

Обробка зіткнень

Для обробки колізій використовуються два основні методи.

  1. Окремий ланцюжок
  2. Відкрита адресація

Окремий ланцюжок

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

Щоб знайти предмет, спочатку переходимо до відра, а потім порівнюємо ключі. Це популярний метод, і якщо використовується список посилань, хеш ніколи не заповнюється. Вартість за get(k)це в середньому O(n)де n - кількість ключів у відрі, загальна кількість ключів - N.

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

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

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

Методи відкритої адресації

  • [Лінійне зондування
  • Квадратичне зондування
  • Подвійне хешування

Як використовувати хешування у коді.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
: ракета:

Запустити код

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
: ракета:

Запустити код

Більше інформації про хешування

  • Безкодовий посібник з хешування та хеш-таблиць
  • Як реалізувати просту хеш-таблицю в JavaScript
  • Пояснення хеш-таблиць