Безкодовото ръководство за хеширане и хеш таблици

Ако сте програмирали преди, със сигурност сте попаднали на хеширане и хеш таблици. Много разработчици са използвали хеш таблици под една или друга форма и начинаещите разработчици трябва да научат тази основна структура от данни. Има само един проблем:

Всички уроци, с които се сблъсквате, със сигурност ще обсъждат хеширане и хеш таблици в JavaScript, Python или друг език за програмиране.

Това означава, че може да разберете малко за това как работи хеширането и как да използвате хеш таблица в [вмъкнете език тук], но може да пропуснете принципите на това как работи.

Не би ли било чудесно, ако можем да научим за хеширането, без да знаем конкретен език? Ако знаете как работи хеширането и какво е хеш таблица, езикът не трябва да има значение.

Това е безкодовият подход и в тази публикация ще ви науча всичко за хеширането и хеш таблиците, независимо кой език за програмиране използвате в момента. Независимо дали сте младши или старши разработчик, всеки ще научи нещо от тази публикация.

И така, какво е хеш функция?

Преди да влезем във всички изискани неща, нека ви кажа какво е хеширане. За да го улесним, нека си представим, че имаме черна кутия:

Тази черна кутия е специална. Тя се нарича функционална кутия. Ще го наречем функционално поле, тъй като това поле ще преобразува независима променлива на входа към зависима променлива на изхода (звучи като извинение, но ме понася)

Нашата функционална кутия работи по следния начин: ако поставим буква в кутията, ще получим номер. Тъй като нашата кутия е функционална кутия, може да има само един изход за всеки вход в кутията.

Нашата функционална кутия ще вземе писмо от AJ на входа и ще изведе съответно число от 0 до 9 на изхода. Така че, ако въведем C, ще получим 2 на изхода.

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

Така че по същество всичко, което прави хеширането, е, че използва функция за картографиране на данни към представителна цифрова или буквено-цифрова стойност. За хеш функцията, независимо от размера на входа, изходът винаги ще остане същият.

Какво ще кажете за хеш таблици?

Така че в този момент може би се чудите какво е хеш таблица. Хеш таблиците използват хеширане, за да формират структура от данни.

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

Тази система за организиране на данни води до много бърз начин за ефективно намиране на данни. Това е така, тъй като тъй като всеки ключ е съпоставен с уникална стойност - след като познаем ключ, можем незабавно да намерим свързаната стойност.

Хеш таблиците са изключително бързи и имат сложност във времето, която е в порядъка на O (1).

Объркан? Погледнете тази диаграма, където имаме множество функционални полета, генериращи хеш стойности.

В този сценарий всеки знак на входа (всеки е ключ) има приложен хеш функция към него и хеш функцията в функционалното поле генерира хеш стойност. След това тази получена стойност се преобразува в индекс в свързания списък или масив, използван за реализиране на хеш таблицата.

Получената структура ще изглежда така:

Хеш сблъсъци

Това е подходящ момент да поговорим за сблъсък в хеш функции и хеш таблици.

Функцията в математиката е идеална с това, че елемент във входа се преобразува точно в един елемент в изхода.

В хеш функцията обаче не винаги е така. Понякога различните хеш стойности във входа могат да дадат същата хеш стойност в изхода. Когато това се случи, получавате това, което е известно като хеш сблъсък.

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

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

Като такъв се използва метод, известен като верига. При веригирането, ако хеш таблицата връща една и съща хеш стойност за множество елементи, ние просто „веригираме“ елементите заедно със същите хеш стойности при един и същ индекс в хеш таблицата.  

По този начин, вместо да се реализира като масив с индекс, ние реализираме хеш таблицата, използвайки свързан списък, където всеки елемент е списък, а не просто да му е присвоена единична стойност.

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

Хеширането същото ли е като криптиране или кодиране?

Много хора са склонни да свързват хеширането с криптиране или кодиране. Така че хеширането е хеширане? Същото ли е като кодирането?

Виждате ли, при криптирането бъркаме данни, така че само някой с ключа, необходим за дешифриране на данните, ще има достъп до тях. Когато използваме шифровъчен шифър, ние не само правим данните криптирани, но също така искаме да дешифрираме данните в даден момент. При криптиране искаме да възстановим оригиналните данни.

Хеширането, от друга страна, взема данни и извежда изход с цел потвърждаване на целостта на данните. При хеширането нямаме намерение да възстановяваме първоначалните данни.

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

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

Хешовете и хеш таблиците имат многобройни приложения! Те включват:

  1. Криптосистеми
  2. Циклични проверки на резервирането
  3. Търсачки
  4. Бази данни
  5. Съставители

Или всяка система, която има сложен процес на търсене.

Обобщавайки

В тази публикация разгледахме основите на хеширането, без да пишем нито един ред код! Това беше лесно, нали? Безкодовият подход е много по-лесен начин за изучаване на тези основни теми.

Научихме, че хеш функциите могат да се използват за преобразуване на обекти в буквено-цифров изход с фиксирана дължина. Също така научихме, че хеш таблиците са системи за търсене ключ-стойност и макар да работят добре, не са перфектни и понякога страдат от сблъсъци.

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

Хареса ли ви безкодовия подход? Искате ли да отидете по-далеч?

Научете за хеш таблиците и други структури от данни и алгоритми в книгата „Безкодови структури от данни и алгоритми“. Ще получите разширение на разгледаното в тази публикация и ще научите за много повече теми, всички без да пишете нито един ред код!

Безкодови структури от данни и алгоритми - Научете DSA, без да пишете един ред код | Армстронг Суберо | Apress Тази книга ви представя нова перспектива за алгоритмите и структурите на данни, напълно безплатна. Научете за алгоритмите за структура на данни (DSA), без никога да се налага да отваряте редактора на кода, да използвате компилатор или да разглеждате интегрирана среда за разработка (IDE) .... Armstrong Subero Search Menu Cart V Количката ви в момента е празна. Вход Акаунт Вход за лавица Apress Access