Какво е хеширане? Как работят хеш кодовете - с примери

Въведение в хеширането

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

Например, ако имаме списък с 10 000 думи на английски и искаме да проверим дали дадена дума е в списъка, би било неефективно последователното сравняване на думата с всички 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
  • Хеш таблици обяснени