HASH MAP V PYTHONE - TECHCODEVIEW.COM

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.

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

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ýkon: