Хеш-карти — це індексовані структури даних. Хеш-карта використовує a хеш-функція щоб обчислити індекс із ключем у масиві сегментів або слотів. Його значення відображається на сегменті з відповідним індексом. Ключ унікальний і незмінний. Подумайте про хеш-карту як про шафу з ящиками з ярликами для речей, які в них зберігаються. Наприклад, зберігання інформації про користувача – розглядайте електронну пошту як ключ, і ми можемо зіставляти значення, що відповідають цьому користувачу, як-от ім’я, прізвище тощо, у відро.
Хеш-функція є ядром реалізації хеш-карти. Він приймає ключ і перетворює його на індекс сегмента в списку сегментів. Ідеальне хешування має створювати інший індекс для кожного ключа. Однак можуть виникнути зіткнення. Коли хешування дає існуючий індекс, ми можемо просто використовувати сегмент для кількох значень, додавши список або повторно хешуючи.
У Python словники є прикладами хеш-карт. Ми побачимо реалізацію хеш-карти з нуля, щоб навчитися створювати та налаштовувати такі структури даних для оптимізації пошуку.
шаблони проектування java
Дизайн хеш-карти включатиме такі функції:
- set_val(ключ, значення): Вставляє пару ключ-значення в хеш-карту. Якщо значення вже існує в хеш-карті, оновіть значення.
- get_val(ключ): Повертає значення, на яке зіставлено вказаний ключ, або Запис не знайдено, якщо ця карта не містить зіставлення для ключа.
- delete_val(ключ): Видаляє відображення для певного ключа, якщо хеш-карта містить відображення для ключа.
Нижче наведено реалізацію.
Python3
аміша патель
class> HashTable:> ># Create empty bucket list of given size> >def> __init__(>self>, size):> >self>.size>=> size> >self>.hash_table>=> self>.create_buckets()> >def> create_buckets(>self>):> >return> [[]>for> _>in> range>(>self>.size)]> ># Insert values into hash map> >def> set_val(>self>, key, val):> > ># Get the index from the key> ># using hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be inserted> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key to be inserted,> ># Update the key value> ># Otherwise append the new key-value pair to the bucket> >if> found_key:> >bucket[index]>=> (key, val)> >else>:> >bucket.append((key, val))> ># Return searched value with specific key> >def> get_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key being searched> >if> record_key>=>=> key:> >found_key>=> True> >break> ># If the bucket has same key as the key being searched,> ># Return the value found> ># Otherwise indicate there was no record found> >if> found_key:> >return> record_val> >else>:> >return> 'No record found'> ># Remove a value with specific key> >def> delete_val(>self>, key):> > ># Get the index from the key using> ># hash function> >hashed_key>=> hash>(key)>%> self>.size> > ># Get the bucket corresponding to index> >bucket>=> self>.hash_table[hashed_key]> >found_key>=> False> >for> index, record>in> enumerate>(bucket):> >record_key, record_val>=> record> > ># check if the bucket has same key as> ># the key to be deleted> >if> record_key>=>=> key:> >found_key>=> True> >break> >if> found_key:> >bucket.pop(index)> >return> ># To print the items of hash map> >def> __str__(>self>):> >return> ''.join(>str>(item)>for> item>in> self>.hash_table)> hash_table>=> HashTable(>50>)> # insert some values> hash_table.set_val(>'[email protected]'>,>'some value'>)> print>(hash_table)> print>()> hash_table.set_val(>'[email protected]'>,>'some other value'>)> print>(hash_table)> print>()> # search/access a record with key> print>(hash_table.get_val(>'[email protected]'>))> print>()> # delete or remove a value> hash_table.delete_val(>'[email protected]'>)> print>(hash_table)> |
>
>
Вихід:
різниця між $ і $$
Часова складність:
Доступ до індексу пам’яті займає постійний час, а хешування – постійний час. Отже, складність пошуку хеш-карти також є постійним часом, тобто O(1).
Переваги HashMaps
● Швидкий доступ до довільної пам'яті за допомогою хеш-функцій
● Може використовувати від’ємні та нецілісні значення для доступу до значень.
arraylist java sort
● Ключі можна зберігати в сортованому порядку, тому можна легко переглядати карти.
Недоліки HashMaps
бінарне дерево проти bst
● Зіткнення можуть призвести до великих штрафів і можуть підірвати часову складність до лінійної.
● Якщо кількість ключів велика, одна хеш-функція часто викликає конфлікти.
Застосування HashMaps
● Вони мають програми в реалізаціях кешу, де розташування пам’яті відображаються на невеликі набори.
● Вони використовуються для індексування кортежів у системах керування базами даних.
● Вони також використовуються в таких алгоритмах, як зіставлення шаблону Рабіна Карпа