A zgoščena tabela je podatkovna struktura, ki omogoča hitro vstavljanje, brisanje in priklic podatkov. Deluje z uporabo zgoščevalne funkcije za preslikavo ključa v indeks v matriki. V tem članku bomo implementirali zgoščevalno tabelo v Python z uporabo ločenega veriženja za obravnavanje trkov.
Komponente zgoščevanja
Ločeno veriženje je tehnika, ki se uporablja za obravnavanje trkov v zgoščevalni tabeli. Ko se dva ali več ključev preslika v isti indeks v matriki, jih shranimo na povezan seznam pri tem indeksu. To nam omogoča, da shranimo več vrednosti na isti indeks in jih še vedno lahko pridobimo z njihovim ključem.
Način implementacije zgoščene tabele z uporabo ločenega veriženja
Način implementacije zgoščene tabele z uporabo ločenega veriženja:
Ustvari dva razreda: ' Vozlišče ' in ' HashTable '.
' Vozlišče ' bo predstavljal vozlišče na povezanem seznamu. Vsako vozlišče bo vsebovalo par ključ-vrednost in kazalec na naslednje vozlišče na seznamu.
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> |
>
>
Razred 'HashTable' bo vseboval matriko, ki bo vsebovala povezane sezname, kot tudi metode za vstavljanje, pridobivanje in brisanje podatkov iz zgoščene tabele.
Python3
v metodo niza v Javi
class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> |
>
>
' __vroče__ ' metoda inicializira zgoščeno tabelo z dano zmogljivostjo. Nastavi ' zmogljivost ' in ' velikost ' spremenljivk in inicializira matriko na 'Brez'.
Naslednja metoda je ' _hash ' metoda. Ta metoda vzame ključ in vrne indeks v matriki, kjer naj bo shranjen par ključ-vrednost. Za zgoščevanje ključa bomo uporabili Pythonovo vgrajeno funkcijo zgoščevanja in nato uporabili operator modulo, da dobimo indeks v matriki.
Python3
def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> |
>
>
The 'vstavi' bo v zgoščevalno tabelo vstavil par ključ-vrednost. Vzame indeks, kamor naj bo par shranjen z uporabo ' _hash ' metoda. Če na tem indeksu ni povezanega seznama, ustvari novo vozlišče s parom ključ-vrednost in ga nastavi kot glavo seznama. Če je na tem indeksu povezan seznam, iterirajte po seznamu, dokler ne najdete zadnjega vozlišča ali ključ že obstaja, in posodobite vrednost, če ključ že obstaja. Če najde ključ, posodobi vrednost. Če ključa ne najde, ustvari novo vozlišče in ga doda na glavo seznama.
java if izjava
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> |
>
>
The Iskanje metoda pridobi vrednost, povezano z danim ključem. Najprej dobi indeks, kamor naj bo shranjen par ključ-vrednost z uporabo _hash metoda. Nato poišče ključ na povezanem seznamu na tem indeksu. Če najde ključ, vrne povezano vrednost. Če ne najde ključa, sproži a KeyError .
Python3
javascript za spustni meni
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 'Odstrani' metoda odstrani par ključ-vrednost iz zgoščene tabele. Najprej dobi indeks, kamor naj bo par shranjen z uporabo ` _hash ` metoda. Nato poišče ključ na povezanem seznamu na tem indeksu. Če najde ključ, odstrani vozlišče s seznama. Če ne najde ključa, dvigne ` KeyError `.
Python3
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__' metoda, ki vrne nizovno predstavitev zgoščene tabele.
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)> |
>
primer odprtokodnega operacijskega sistema je
>
Tukaj je popolna izvedba razreda '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> |
>
>Izhod
True False 2 4 3>
Časovna kompleksnost in prostorska kompleksnost:
- The časovna zapletenost od vstavi , Iskanje in Odstrani metod v zgoščevalni tabeli z uporabo ločenega veriženja je odvisno od velikosti zgoščevalne tabele, števila parov ključ-vrednost v zgoščevalni tabeli in dolžine povezanega seznama pri vsakem indeksu.
- Ob predpostavki dobre zgoščevalne funkcije in enotne porazdelitve ključev je pričakovana časovna kompleksnost teh metod O(1) za vsako operacijo. Vendar pa je v najslabšem primeru lahko časovna zapletenost O(n) , kjer je n število parov ključ-vrednost v zgoščevalni tabeli.
- Vendar je pomembno, da izberete dobro zgoščevalno funkcijo in ustrezno velikost za zgoščevalno tabelo, da zmanjšate verjetnost kolizij in zagotovite dobro delovanje.
- The kompleksnost prostora zgoščevalne tabele z uporabo ločenega veriženja je odvisna od velikosti zgoščevalne tabele in števila parov ključ-vrednost, shranjenih v zgoščevalni tabeli.
- Zgoščevalna tabela sama zavzame O(m) prostor, kjer je m zmogljivost razpršilne tabele. Vsako vozlišče povezanega seznama zavzame O(1) prostora, na povezanih seznamih pa je lahko največ n vozlišč, kjer je n število parov ključ-vrednost, shranjenih v zgoščevalni tabeli.
- Zato je celotna kompleksnost prostora O(m + n) .
Zaključek:
V praksi je pomembno izbrati ustrezno zmogljivost za zgoščeno tabelo, da uravnotežite porabo prostora in verjetnost kolizij. Če je zmogljivost premajhna, se poveča verjetnost kolizij, kar lahko povzroči poslabšanje delovanja. Po drugi strani pa lahko zgoščena tabela porabi več pomnilnika, kot je potrebno, če je zmogljivost prevelika.