A hašovacia tabuľka je dátová štruktúra, ktorá umožňuje rýchle vkladanie, mazanie a získavanie dát. Funguje pomocou hašovacej funkcie na mapovanie kľúča na index v poli. V tomto článku implementujeme hašovaciu tabuľku v Pythone pomocou samostatného reťazenia na riešenie kolízií.
Komponenty hašovania
Oddelené reťazenie je technika používaná na riešenie kolízií v hašovacej tabuľke. Keď sa dva alebo viac kľúčov mapuje na rovnaký index v poli, uložíme ich do prepojeného zoznamu v tomto indexe. To nám umožňuje uložiť viacero hodnôt do rovnakého indexu a stále ich budeme môcť získať pomocou ich kľúča.
Spôsob implementácie tabuľky hash pomocou samostatného reťazenia
Spôsob implementácie tabuľky hash pomocou samostatného reťazenia:
Vytvorte dve triedy: „ Uzol „a“ HashTable '.
' Uzol ‘ trieda bude predstavovať uzol v prepojenom zozname. Každý uzol bude obsahovať pár kľúč – hodnota, ako aj ukazovateľ na ďalší uzol v zozname.
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> |
abstraktné metódy
>
>
Trieda „HashTable“ bude obsahovať pole, ktoré bude obsahovať prepojené zoznamy, ako aj metódy na vkladanie, získavanie a odstraňovanie údajov z tabuľky hash.
Python3
vlc na stiahnutie z youtube
class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> |
>
>
' __horúce__ ‘ metóda inicializuje hašovaciu tabuľku s danou kapacitou. Nastavuje „ kapacita „a“ veľkosť ‘ premenné a inicializuje pole na ‘Žiadne’.
Ďalšou metódou je „ _hash „metóda. Táto metóda vezme kľúč a vráti index v poli, kde má byť uložený pár kľúč – hodnota. Na hashovanie kľúča použijeme vstavanú hašovaciu funkciu Pythonu a potom použijeme operátor modulo na získanie indexu v poli.
Python3
def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> |
>
>
The 'vložiť' metóda vloží pár kľúč – hodnota do hašovacej tabuľky. Prevezme index, kde by mal byť pár uložený pomocou „ _hash „metóda. Ak v tomto indexe nie je žiadny prepojený zoznam, vytvorí nový uzol s párom kľúč – hodnota a nastaví ho ako hlavu zoznamu. Ak v tomto indexe existuje prepojený zoznam, iterujte zoznamom, kým sa nenájde posledný uzol alebo kým už kľúč neexistuje, a ak kľúč už existuje, aktualizujte hodnotu. Ak nájde kľúč, aktualizuje hodnotu. Ak kľúč nenájde, vytvorí nový uzol a pridá ho na začiatok zoznamu.
Python3
def> insert(>self>, key, value):> >index>=> self>._hash(key)> >if> self>.table[index]>is> None>:> >self>.table[index]>=> Node(key, value)> >self>.size>+>=> 1> >else>:> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >current.value>=> value> >return> >current>=> current.>next> >new_node>=> Node(key, value)> >new_node.>next> => self>.table[index]> >self>.table[index]>=> new_node> >self>.size>+>=> 1> |
>
linux zadarmo ipconfig
>
The Vyhľadávanie metóda načíta hodnotu spojenú s daným kľúčom. Najprv získa index, kde by mal byť uložený pár kľúč-hodnota pomocou _hash metóda. Potom vyhľadá v prepojenom zozname v tomto indexe kľúč. Ak nájde kľúč, vráti priradenú hodnotu. Ak nenájde kľúč, vyvolá a KeyError .
Python3
def> search(>self>, key):> >index>=> self>._hash(key)> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >return> current.value> >current>=> current.>next> >raise> KeyError(key)> |
>
>
The 'odstrániť' metóda odstráni pár kľúč – hodnota z hašovacej tabuľky. Najprv získa index, kde má byť pár uložený, pomocou ` _hash ` metóda. Potom vyhľadá v prepojenom zozname v tomto indexe kľúč. Ak nájde kľúč, odstráni uzol zo zoznamu. Ak nenájde kľúč, vyvolá „ KeyError `.
Python3
odstráňte prvý znak v programe Excel
def> remove(>self>, key):> >index>=> self>._hash(key)> > >previous>=> None> >current>=> self>.table[index]> > >while> current:> >if> current.key>=>=> key:> >if> previous:> >previous.>next> => current.>next> >else>:> >self>.table[index]>=> current.>next> >self>.size>->=> 1> >return> >previous>=> current> >current>=> current.>next> > >raise> KeyError(key)> |
>
>
„__str__“ metóda, ktorá vracia reťazcovú reprezentáciu hašovacej tabuľky.
Python3
def> __str__(>self>):> >elements>=> []> >for> i>in> range>(>self>.capacity):> >current>=> self>.table[i]> >while> current:> >elements.append((current.key, current.value))> >current>=> current.>next> >return> str>(elements)> |
>
>
Tu je úplná implementácia triedy „HashTable“:
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> > > class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> > >def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> > >def> insert(>self>, key, value):> >index>=> self>._hash(key)> > >if> self>.table[index]>is> None>:> >self>.table[index]>=> Node(key, value)> >self>.size>+>=> 1> >else>:> >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >current.value>=> value> >return> >current>=> current.>next> >new_node>=> Node(key, value)> >new_node.>next> => self>.table[index]> >self>.table[index]>=> new_node> >self>.size>+>=> 1> > >def> search(>self>, key):> >index>=> self>._hash(key)> > >current>=> self>.table[index]> >while> current:> >if> current.key>=>=> key:> >return> current.value> >current>=> current.>next> > >raise> KeyError(key)> > >def> remove(>self>, key):> >index>=> self>._hash(key)> > >previous>=> None> >current>=> self>.table[index]> > >while> current:> >if> current.key>=>=> key:> >if> previous:> >previous.>next> => current.>next> >else>:> >self>.table[index]>=> current.>next> >self>.size>->=> 1> >return> >previous>=> current> >current>=> current.>next> > >raise> KeyError(key)> > >def> __len__(>self>):> >return> self>.size> > >def> __contains__(>self>, key):> >try>:> >self>.search(key)> >return> True> >except> KeyError:> >return> False> > > # Driver code> if> __name__>=>=> '__main__'>:> > ># Create a hash table with> ># a capacity of 5> >ht>=> HashTable(>5>)> > ># Add some key-value pairs> ># to the hash table> >ht.insert(>'apple'>,>3>)> >ht.insert(>'banana'>,>2>)> >ht.insert(>'cherry'>,>5>)> > ># Check if the hash table> ># contains a key> >print>(>'apple'> in> ht)># True> >print>(>'durian'> in> ht)># False> > ># Get the value for a key> >print>(ht.search(>'banana'>))># 2> > ># Update the value for a key> >ht.insert(>'banana'>,>4>)> >print>(ht.search(>'banana'>))># 4> > >ht.remove(>'apple'>)> ># Check the size of the hash table> >print>(>len>(ht))># 3> |
dvojito prepojený zoznam
>
>Výkon
True False 2 4 3>
Časová a priestorová zložitosť:
- The časová zložitosť z vložiť , Vyhľadávanie a odstrániť metódy v hašovacej tabuľke používajúce samostatné reťazenie závisí od veľkosti hašovacej tabuľky, počtu párov kľúč – hodnota v hašovacej tabuľke a dĺžky prepojeného zoznamu v každom indexe.
- Za predpokladu dobrej hašovacej funkcie a rovnomernej distribúcie kľúčov je predpokladaná časová náročnosť týchto metód O(1) pre každú operáciu. V najhoršom prípade však môže byť časová náročnosť O(n) , kde n je počet párov kľúč – hodnota v hašovacej tabuľke.
- Je však dôležité vybrať si dobrú hašovaciu funkciu a vhodnú veľkosť hašovacej tabuľky, aby sa minimalizovala pravdepodobnosť kolízií a zabezpečil sa dobrý výkon.
- The priestorovú zložitosť hašovacej tabuľky pomocou samostatného reťazenia závisí od veľkosti hašovacej tabuľky a počtu párov kľúč – hodnota uložených v hašovacej tabuľke.
- Samotná hašovacia tabuľka berie O (m) priestor, kde m je kapacita hašovacej tabuľky. Každý uzol prepojeného zoznamu trvá O(1) priestor a v prepojených zoznamoch môže byť najviac n uzlov, kde n je počet párov kľúč-hodnota uložených v hašovacej tabuľke.
- Preto je celková zložitosť priestoru O(m + n) .
Záver:
V praxi je dôležité zvoliť vhodnú kapacitu pre hašovaciu tabuľku, aby sa vyrovnalo využitie priestoru a pravdepodobnosť kolízií. Ak je kapacita príliš malá, zvyšuje sa pravdepodobnosť kolízií, čo môže spôsobiť zhoršenie výkonu. Na druhej strane, ak je kapacita príliš veľká, hašovacia tabuľka môže spotrebovať viac pamäte, ako je potrebné.