Hash mapy jsou indexované datové struktury. Hashová mapa využívá a hashovací funkce pro výpočet indexu s klíčem do pole segmentů nebo slotů. Jeho hodnota je mapována na bucket s odpovídajícím indexem. Klíč je jedinečný a neměnný. Představte si hash mapu jako skříň se zásuvkami s popisky pro věci v nich uložené. Například ukládání informací o uživateli – za klíč považujeme e-mail a můžeme namapovat hodnoty odpovídající tomuto uživateli, jako je jméno, příjmení atd., do segmentu.
Hash funkce je jádrem implementace hash mapy. Vezme klíč a převede ho do indexu bucketu v bucket listu. Ideální hašování by mělo pro každý klíč vytvořit jiný index. Může však dojít ke kolizím. Když hašování poskytuje existující index, můžeme jednoduše použít segment pro více hodnot připojením seznamu nebo přehašováním.
V Pythonu jsou příklady hash map slovníky. Uvidíme implementaci hash mapy od nuly, abychom se naučili, jak vytvořit a přizpůsobit takové datové struktury pro optimalizaci vyhledávání.
Návrh hash mapy bude obsahovat následující funkce:
- set_val(klíč, hodnota): Vloží pár klíč–hodnota do hash mapy. Pokud hodnota v hash mapě již existuje, aktualizujte hodnotu.
- get_val(klíč): Vrátí hodnotu, na kterou je zadaný klíč mapován, nebo Nebyl nalezen žádný záznam, pokud tato mapa neobsahuje žádné mapování pro klíč.
- delete_val(klíč): Odstraní mapování pro konkrétní klíč, pokud mapa hash obsahuje mapování pro klíč.
Níže je implementace.
Python3
zásobník v ds
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)> |
>
>
Výstup:
Časová náročnost:
Přístup k indexu paměti trvá konstantní čas a hašování trvá konstantní čas. Složitost hledání hash mapy je tedy také konstantním časem, tedy O(1).
diagram tříd java
Výhody HashMaps
● Rychlý náhodný přístup do paměti pomocí hashovacích funkcí
● Pro přístup k hodnotám může používat záporné a neintegrální hodnoty.
● Klíče mohou být uloženy v setříděném pořadí, takže lze snadno iterovat přes mapy.
Nevýhody HashMaps
● Kolize mohou způsobit velké penalizace a mohou nafouknout časovou složitost na lineární.
● Když je počet klíčů velký, jedna hašovací funkce často způsobuje kolize.
Aplikace HashMaps
● Mají aplikace v implementacích Cache, kde jsou místa v paměti mapována na malé sady.
● Používají se k indexování n-tic v systémech správy databází.
● Používají se také v algoritmech, jako je Rabin Karp pattern matching