Hash mapy sú indexované dátové štruktúry. Hash mapa využíva a hašovacia funkcia na výpočet indexu pomocou kľúča do poľa segmentov alebo slotov. Jeho hodnota je priradená k segmentu s príslušným indexom. Kľúč je jedinečný a nemenný. Predstavte si hašovaciu mapu ako skrinku so zásuvkami so štítkami na veci, ktoré sú v nich uložené. Napríklad ukladanie informácií o používateľovi – e-mail považujte za kľúč a hodnoty zodpovedajúce tomuto používateľovi, ako je meno, priezvisko atď., môžeme namapovať do segmentu.
Hash funkcia je jadrom implementácie hash mapy. Vezme kľúč a preloží ho do indexu vedra v zozname. Ideálne hašovanie by malo pre každý kľúč vytvoriť iný index. Môžu však nastať kolízie. Keď hašovanie poskytuje existujúci index, môžeme jednoducho použiť segment pre viacero hodnôt pripojením zoznamu alebo prehashovaním.
avl strom
V Pythone sú slovníky príkladmi hash máp. Uvidíme implementáciu hašovacej mapy od začiatku, aby sme sa naučili, ako vytvoriť a prispôsobiť takéto dátové štruktúry na optimalizáciu vyhľadávania.
Návrh hash mapy bude obsahovať nasledujúce funkcie:
- set_val(kľúč, hodnota): Vloží pár kľúč – hodnota do hašovacej mapy. Ak už hodnota v hašovacej mape existuje, aktualizujte hodnotu.
- get_val(key): Vráti hodnotu, na ktorú je zadaný kľúč namapovaný, alebo Ak táto mapa neobsahuje žiadne mapovanie pre kľúč, nenašiel sa žiadny záznam.
- delete_val(key): Odstráni mapovanie pre konkrétny kľúč, ak hašovacia mapa obsahuje mapovanie pre kľúč.
Nižšie je uvedená implementácia.
Python3
arraylist a linkedlist
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)> |
>
>
triedenie vloženia v jazyku Java
Výkon:
Časová zložitosť:
Prístup k indexu pamäte trvá konštantne a hašovanie trvá konštantne. Zložitosť vyhľadávania hašovacej mapy je teda tiež konštantný čas, teda O(1).
Výhody HashMaps
● Rýchly náhodný prístup do pamäte pomocou hašovacích funkcií
● Na prístup k hodnotám môže používať záporné a neintegrálne hodnoty.
● Kľúče môžu byť uložené v zoradenom poradí, a preto je možné ľahko iterovať cez mapy.
Nevýhody HashMaps
● Kolízie môžu spôsobiť veľké penalizácie a môžu zväčšiť časovú zložitosť na lineárnu.
● Keď je počet kľúčov veľký, jedna hašovacia funkcia často spôsobuje kolízie.
Aplikácie HashMaps
reťazec na int
● Majú aplikácie v implementáciách Cache, kde sú miesta v pamäti mapované na malé sady.
● Používajú sa na indexovanie n-tic v systémoch správy databáz.
● Používajú sa aj v algoritmoch, ako je porovnávanie vzorov Rabin Karp