Какво е хеширане?
Хеш е стойност, която има фиксирана дължина и се генерира с помощта на математическа формула. Стойностите на хеш се използват при компресиране на данни, криптология и др. При индексирането на данни се използват хеш стойности, тъй като те имат фиксиран размер на дължината, независимо от стойностите, които са били използвани за генерирането им. Той прави хеш стойности, за да заемат минимално пространство в сравнение с други стойности с различна дължина.
Хеш функцията използва математически алгоритъм за преобразуване на ключа в хеш. Сблъсък възниква, когато хеш функцията генерира една и съща хеш стойност за повече от един ключ.
В този урок по алгоритъм ще научите:
- Какво е хеширане?
- Какво е хеш таблица?
- Хеш функции
- Качества на добра хеш функция
- Сблъсък
- Операции с хеш таблица
- Пример за Python на хеш таблица
- Обяснение на кода на хеш таблицата
- Пример за речник на Python
- Анализ на сложността
- Приложения в реалния свят
- Предимства на хеш таблиците
- Недостатъци на хеш таблиците
Какво е хеш таблица?
А хеш-таблица е структура от данни, която съхранява стойности с помощта на чифт ключове и стойности. На всяка стойност се присвоява уникален ключ, който се генерира с помощта на хеш функция.
Името на ключа се използва за достъп до свързаната с него стойност. Това прави търсенето на стойности в хеш таблица много бързо, независимо от броя на елементите в хеш таблицата.
Хеш функции
Например, ако искаме да съхраняваме записи на служителите и всеки служител е уникално идентифициран с помощта на номер на служител.
Можем да използваме номера на служителя като ключ и да присвоим данните на служителя като стойност.
Горният подход ще изисква допълнително свободно пространство от порядъка на (m * n 2 ), където променливата m е размерът на масива, а променливата n е броят на цифрите за номера на служителя. Този подход въвежда проблем с пространството за съхранение.
Хеш функцията решава горния проблем, като получава номера на служителя и го използва за генериране на целочислена стойност на хеш, фиксирани цифри и оптимизиране на пространството за съхранение. Целта на хеш функцията е да създаде ключ, който ще се използва за препращане към стойността, която искаме да съхраним. Функцията приема стойността, която трябва да бъде запазена, след което използва алгоритъм за изчисляване на стойността на ключа.
Следва пример за проста хеш функция
h(k) = k1 % m
ТУК,
- h (k) е хеш функцията, която приема параметър k. Параметърът k е стойността, за която искаме да изчислим ключа.
- k 1 % 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 1 % m), където m е размерът на хеш таблицата.
Следващата таблица показва хеш стойностите, които ще бъдат генерирани.
| Ключ | Алгоритъм на хеш (k 1 % m) | Стойност на хеш |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11. | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Както можем да видим от горните резултати, стойностите 2 и 9 имат една и съща хеш стойност и не можем да съхраняваме повече от една стойност на всяка позиция.
Даденият проблем може да бъде решен чрез използване на верига или сондиране. Следващите раздели обсъждат подробно вериги и сондиране.
Оковаване
Chaining е техника, която се използва за решаване на проблема с колизия чрез използване на свързани списъци, всеки от които има уникални индекси.
Следващото изображение визуализира как изглежда окован списък
И 2, и 9 заемат един и същ индекс, но се съхраняват като свързани списъци. Всеки списък има уникален идентификатор.
Предимства на веригите списъци
По-долу са предимствата на верижните списъци:
- Окованите списъци имат по-добра производителност при вмъкване на данни, тъй като редът на вмъкване е O (1).
- Не е необходимо да преоразмерявате хеш таблица, която използва верижен списък.
- Той може лесно да побере голям брой стойности, стига да има свободно място.
Сондиране
Другата техника, която се използва за разрешаване на сблъсък, е сондирането. Когато използваме метода на сондиране, ако възникне сблъсък, можем просто да продължим напред и да намерим празен слот, за да съхраним нашата стойност.
Следват методите за сондиране:
| Метод | Описание |
| Линейно сондиране | Точно както подсказва името, този метод търси празни слотове линейно, започвайки от позицията, в която е възникнал сблъсък и се движи напред. Ако е достигнат краят на списъка и не е намерен празен слот. Сондирането започва в началото на списъка. |
| Квадратично сондиране | Този метод използва квадратни полиномиални изрази, за да намери следващия наличен свободен слот. |
| Двойно хеширане | Тази техника използва алгоритъм на вторична хеш функция, за да намери следващия свободен свободен слот. |
Използвайки горния пример, хеш таблицата след използване на сондиране ще се появи, както следва:
Операции с хеш таблица
Ето операциите, поддържани от хеш таблици:
- Вмъкване - тази операция се използва за добавяне на елемент към хеш таблицата
- Търсене - тази операция се използва за търсене на елементи в хеш таблицата с помощта на ключа
- Изтриване - тази операция се използва за изтриване на елементи от хеш таблицата
Вмъкване на операция с данни
Операцията за вмъкване се използва за съхраняване на стойности в хеш таблицата. Когато нова стойност се съхранява в хеш таблицата, на нея се присвоява номер на индекс. Индексният номер се изчислява с помощта на хеш функция. Хеш функцията разрешава всякакви сблъсъци, които възникват при изчисляване на индексния номер.
Търсене на операция с данни
Операцията за търсене се използва за търсене на стойности в хеш таблицата с помощта на индексния номер. Операцията за търсене връща стойността, която е свързана с номера на индекса за търсене. Например, ако съхраним стойността 6 в индекс 2, операцията за търсене с индекс номер 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)}')
Обяснение на кода на хеш таблицата
ТУК,
- Определя функция hash_key, която приема ключа за параметри и m.
- Използва проста операция по модул за определяне на хеш стойността
- Определя променлива m, която се инициализира до стойността 7. Това е размерът на нашата хеш таблица
- Изчислява и отпечатва хеш стойността 3
- Изчислява и отпечатва хеш стойността 2
- Изчислява и отпечатва хеш стойността 9
- Изчислява и отпечатва хеш стойността 11
- Изчислява и отпечатва хеш стойността 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)
ТУК,
- Определя речник променлива служител. Името на ключа се използва за съхраняване на стойността John Doe, възрастта съхранява 36 години и позицията съхранява стойността Business Manager.
- Извлича стойността на името на ключа и го отпечатва в терминала
- Актуализира стойността на ключовата позиция до стойността Софтуерен инженер
- Отпечатва стойностите на името и позицията на ключовете
- Изтрива всички стойности, които се съхраняват в нашата речникова променлива служител
- Отпечатва стойността на служителя
Изпълнението на горния код води до следните резултати.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Анализ на сложността
Хеш таблиците имат средна времева сложност на O (1) в най-добрия случай. Сложността на времето в най-лошия случай е O (n). Най-лошият сценарий възниква, когато много стойности генерират един и същ хеш ключ и ние трябва да разрешим сблъсъка чрез сондиране.
Приложения в реалния свят
В реалния свят хеш таблиците се използват за съхраняване на данни за
- Бази данни
- Асоциативни масиви
- Комплекти
- Кеш памет
Предимства на хеш таблиците
Ето плюсовете / ползите от използването на хеш таблици:
- Хеш таблиците имат висока производителност при търсене на данни, вмъкване и изтриване на съществуващи стойности.
- Сложността във времето за хеш таблици е постоянна, независимо от броя на елементите в таблицата.
- Те се представят много добре дори при работа с големи масиви от данни.
Недостатъци на хеш таблиците
Ето минусите от използването на хеш таблици:
- Не можете да използвате нулева стойност като ключ.
- Сблъсъците не могат да бъдат избегнати при генериране на ключове с използване. хеш функции. Сблъсъци възникват, когато се генерира ключ, който вече се използва.
- Ако функцията за хеширане има много сблъсъци, това може да доведе до намаляване на производителността.
Резюме:
- Хеш таблиците се използват за съхраняване на данни с помощта на двойка ключове и стойности.
- Хеш функцията използва математически алгоритъм за изчисляване на хеш стойността.
- Сблъсък възниква, когато една и съща хеш стойност се генерира за повече от една стойност.
- Chaining решава сблъсъка чрез създаване на свързани списъци.
- Сондирането решава сблъсъка чрез намиране на празни слотове в хеш таблицата.
- Линейното сондиране търси следващия свободен слот, за да съхрани стойността, започвайки от слота, където е възникнал сблъсъкът.
- Квадратичното сондиране използва полиномични изрази, за да намери следващия свободен слот, когато възникне сблъсък.
- Двойното хеширане използва алгоритъм на вторична хеш функция, за да намери следващия свободен слот, когато възникне сблъсък.
- Хеш таблиците имат по-добра производителност в сравнение с други структури от данни.
- Средната времева сложност на хеш таблиците е O (1)
- Речникът на данните в речника в python е пример за хеш таблица.
- Хеш таблиците поддържат операции за вмъкване, търсене и изтриване.
- Нулева стойност не може да се използва като стойност на индекса.
- Сблъсъците не могат да бъдат избегнати в хеш функциите. Добрата хеш функция намалява до минимум броя на сблъсъците, за да се подобри производителността.