Хеш таблица в структурата на данните: Python Пример
Сара Чен
Какво е хеширане?
Хешът е стойност с фиксирана дължина и се генерира с помощта на математическа формула. Хеш стойностите се използват при компресиране на данни, криптология и т.н. При индексирането на данни хеш стойностите се използват, защото имат фиксиран размер на дължина, независимо от стойностите, които са били използвани за генерирането им. Той кара хеш стойностите да заемат минимално място в сравнение с други стойности с различна дължина.
Хеш функцията използва математически алгоритъм за преобразуване на ключа в хеш. Сблъсък възниква, когато хеш функция произвежда една и съща хеш стойност за повече от един ключ.
Какво е хеш таблица?
A ХЕШ ТАБЛИЦА е структура от данни, която съхранява стойности, използвайки двойка ключове и стойности. На всяка стойност се присвоява уникален ключ, който се генерира с помощта на хеш функция.
Името на ключа се използва за достъп до свързаната с него стойност. Това прави търсенето на стойности в хеш-таблица много бързо, независимо от броя на елементите в хеш-таблицата.
Hash функции
Например, ако искаме да съхраняваме записи на служители и всеки служител е уникално идентифициран с помощта на номер на служител.
Можем да използваме номера на служителя като ключ и да присвоим данните на служителя като стойност.
Горният подход ще изисква допълнително свободно пространство от порядъка на (m * n2) където променливата m е размерът на масив, а променливата n е броят на цифрите за номера на служителя. Този подход създава проблем с пространството за съхранение.
Хеш функцията решава горния проблем, като получава номера на служителя и го използва за генериране на хеш цяло число, фиксирани цифри и оптимизиране на пространството за съхранение. Целта на хеш функцията е да създаде ключ, който ще се използва за препратка към стойността, която искаме да съхраним. Функцията приема стойността, която трябва да бъде запазена, след което използва алгоритъм за изчисляване на стойността на ключа.
Следното е пример за проста хеш функция
h(k) = k1 % m
ТУК,
- h(k) е хеш функцията, която приема параметър k. Параметърът k е стойността, за която искаме да изчислим ключа.
- k1 % 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 и ще използваме формулата (k1 % m), където m е размерът на хеш-таблицата.
Следната таблица показва хеш стойностите, които ще бъдат генерирани.
| ключ | Алгоритъм за хеширане (k1 % m) | Хеш стойност |
|---|---|---|
| 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).
- Не е необходимо да преоразмерявате хеш таблица, която използва верижен списък.
- Той може лесно да побере голям брой стойности, стига да има свободно място.
Сондиране
Другата техника, която се използва за разрешаване на сблъсък, е сондирането. Когато използваме метода на сондиране, ако възникне сблъсък, можем просто да продължим и да намерим празен слот, за да съхраним нашата стойност.
Методите за сондиране са следните:
| Начин на доставка | Descriptйон |
|---|---|
| Линейно сондиране | Точно както подсказва името, този метод търси празни слотове линейно, започвайки от позицията, където е настъпил сблъсъкът и се движи напред. Ако краят на списъка е достигнат и не е намерен празен слот. Сондирането започва от началото на списъка. |
| Квадратично сондиране | Този метод използва изрази на квадратен полином, за да намери следващия наличен свободен слот. |
| Double хеширане | Тази техника използва вторичен алгоритъм за хеш функция, за да намери следващия свободен наличен слот. |
Използвайки нашия горен пример, хеш-таблицата след използване на сондиране ще изглежда както следва:
Операции с хеш таблици
Ето ги Operaфункции, поддържани от хеш таблици:
- вмъкване - това Operation се използва за добавяне на елемент към хеш-таблицата
- Търсене - това Operation се използва за търсене на елементи в хеш-таблицата с помощта на ключа
- Изтриване - това Operation се използва за изтриване на елементи от хеш-таблицата
Операция за вмъкване на данни
Операцията за вмъкване се използва за съхраняване на стойности в хеш-таблицата. Когато нова стойност се съхрани в хеш-таблицата, й се присвоява индексен номер. Индексният номер се изчислява с помощта на хеш функцията. Хеш функцията разрешава всички сблъсъци, които възникват при изчисляване на индексния номер.
Операция за търсене на данни
Операцията за търсене се използва за търсене на стойности в хеш-таблицата с помощта на номера на индекса. Операцията за търсене връща стойността, която е свързана с номера на индекса за търсене. Например, ако съхраним стойността 6 в индекс 2, операцията за търсене с индекс номер 2 ще върне стойността 6.
Операция за изтриване на данни
Операцията за изтриване се използва за премахване на стойност от хеш таблица. За да изтриете Operaцията се извършва с помощта на номера на индекса. След като дадена стойност бъде изтрита, индексният номер се освобождава. Може да се използва за съхраняване на други стойности чрез операцията за вмъкване.
Внедряване на хеш таблица с Python Пример
Нека да разгледаме прост пример, който изчислява хеш стойността на ключ
def hash_key( key, m):
return key % m
m = 7
print(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, която приема параметрите key и m.
- Използва проста модулна операция за определяне на хеш стойността
- Дефинира променлива m, която се инициализира със стойност 7. Това е размерът на нашата хеш таблица
- Изчислява и отпечатва хеш стойността на 3
- Изчислява и отпечатва хеш стойността на 2
- Изчислява и отпечатва хеш стойността на 9
- Изчислява и отпечатва хеш стойността на 11
- Изчислява и отпечатва хеш стойността на 7
Изпълнението на горния код води до следните резултати.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Пример за речник
Python идва с вграден тип данни, наречен речник. Речникът е пример за хеш таблица. Той съхранява стойности с помощта на двойка ключове и стойности. Хеш стойностите се генерират автоматично за нас и всички сблъсъци се разрешават за нас във фонов режим.
Следващият пример показва как можете да използвате тип данни от речник в 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). Най-лошият сценарий възниква, когато много стойности генерират един и същ хеш ключ и трябва да разрешим сблъсъка чрез изследване.
Приложения от реалния свят
В реалния свят хеш-таблиците се използват за съхраняване на данни за
- Данни
- Асоциативни масиви
- Комплекти
- Кеш памет
Предимства на хеш таблиците
Ето плюсовете/ползите от използването на хеш таблици:
- Хеш таблиците имат висока производителност при търсене на данни, вмъкване и изтриване на съществуващи стойности.
- Времевата сложност за хеш таблиците е постоянна, независимо от броя на елементите в таблицата.
- Те се представят много добре дори когато работят с големи набори от данни.
Недостатъци на хеш таблиците
Ето недостатъците на използването на хеш таблици:
- Не можете да използвате нулева стойност като ключ.
- Сблъсъците не могат да бъдат избегнати при генериране на ключове с помощта на. хеш функции. Сблъсъци възникват, когато се генерира ключ, който вече се използва.
- Ако функцията за хеширане има много сблъсъци, това може да доведе до намаляване на производителността.
Oбобщение
- Хеш таблиците се използват за съхраняване на данни с помощта на двойка ключове и стойности.
- Хеш функцията използва математически алгоритъм за изчисляване на хеш стойността.
- Сблъсък възниква, когато една и съща хеш стойност се генерира за повече от една стойност.
- Верижното свързване разрешава сблъсък чрез създаване на свързани списъци.
- Пробването разрешава сблъсък чрез намиране на празни слотове в хеш-таблицата.
- Линейното сондиране търси следващия свободен слот за съхраняване на стойността, започвайки от слота, където е настъпил сблъсъкът.
- Квадратното сондиране използва полиномиални изрази, за да намери следващия свободен слот, когато възникне сблъсък.
- Double хеширането използва алгоритъм на вторична хеш функция, за да намери следващия свободен слот, когато възникне сблъсък.
- Хеш таблиците имат по-добра производителност в сравнение с други структури от данни.
- Средната времева сложност на хеш таблиците е O (1)
- Тип данни от речник в python е пример за хеш таблица.
- Хеш таблиците поддържат операции за вмъкване, търсене и изтриване.
- Нулева стойност не може да се използва като стойност на индекс.
- Сблъсъците не могат да бъдат избегнати в хеш функциите. Добрата хеш функция минимизира броя на възникващите сблъсъци, за да подобри производителността.
