A masa hash este o structură de date care permite inserarea, ștergerea și preluarea rapidă a datelor. Funcționează folosind o funcție hash pentru a mapa o cheie la un index dintr-o matrice. În acest articol, vom implementa un tabel hash în Python folosind înlănțuire separată pentru a gestiona coliziunile.
Componentele hashingului
Înlănțuirea separată este o tehnică utilizată pentru a gestiona coliziunile într-un tabel hash. Atunci când două sau mai multe chei se mapează la același index în matrice, le stocăm într-o listă legată la acel index. Acest lucru ne permite să stocăm mai multe valori la același index și să le putem extrage folosind cheia lor.
Mod de implementare Hash Table folosind Separate Chaining
Mod de implementare Hash Table folosind Separate Chaining:
Creați două clase: „ Nodul ' și ' HashTable '.
„ Nodul „clasa va reprezenta un nod într-o listă legată. Fiecare nod va conține o pereche cheie-valoare, precum și un indicator către următorul nod din listă.
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> |
>
>
proprietăți acide
Clasa „HashTable” va conține matricea care va deține listele legate, precum și metode de inserare, preluare și ștergere a datelor din tabelul hash.
Python3
class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> |
>
>
„ __Fierbinte__ metoda inițializează tabelul hash cu o capacitate dată. Acesta stabilește „ capacitate ' și ' mărimea ‘ variabile și inițializează matricea la „Niciuna”.
Următoarea metodă este „ _hash ‘metoda. Această metodă preia o cheie și returnează un index în tabloul în care ar trebui să fie stocată perechea cheie-valoare. Vom folosi funcția hash încorporată a lui Python pentru a hash cheia și apoi vom folosi operatorul modulo pentru a obține un index în matrice.
Python3
ștergeți memoria cache npm
def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> |
>
>
The 'introduce' metoda va insera o pereche cheie-valoare în tabelul hash. Acesta ia indexul unde ar trebui să fie stocată perechea folosind „ _hash ‘metoda. Dacă nu există o listă legată la acel index, acesta creează un nou nod cu perechea cheie-valoare și îl setează ca cap al listei. Dacă există o listă legată la acel index, repetați lista până când este găsit ultimul nod sau cheia există deja și actualizați valoarea dacă cheia există deja. Dacă găsește cheia, actualizează valoarea. Dacă nu găsește cheia, creează un nou nod și îl adaugă în capul listei.
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 căutare metoda preia valoarea asociată cu o anumită cheie. Mai întâi primește indexul în care ar trebui să fie stocată perechea cheie-valoare folosind _hash metodă. Apoi caută cheia în lista legată de la acel index. Dacă găsește cheia, returnează valoarea asociată. Dacă nu găsește cheia, ridică a KeyError .
Python3
fișiere Linux
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 'elimina' metoda elimină o pereche cheie-valoare din tabelul hash. Primește mai întâi indexul unde ar trebui să fie stocată perechea folosind ` _hash ` metoda. Apoi caută cheia în lista legată de la acel index. Dacă găsește cheia, șterge nodul din listă. Dacă nu găsește cheia, se ridică un ` 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__” metodă care returnează o reprezentare șir a tabelului hash.
comparați șirul java
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)> |
>
>
Iată implementarea completă a clasei „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> |
actor shweta tiwari
>
>Ieșire
True False 2 4 3>
Complexitatea timpului și complexitatea spațiului:
- The complexitatea timpului al introduce , căutare și elimina metodele dintr-un tabel hash care utilizează înlănțuirea separată depinde de dimensiunea tabelului de hash, de numărul de perechi cheie-valoare din tabelul de hash și de lungimea listei legate la fiecare index.
- Presupunând o funcție hash bună și o distribuție uniformă a cheilor, complexitatea de timp așteptată a acestor metode este O(1) pentru fiecare operatie. Cu toate acestea, în cel mai rău caz, complexitatea timpului poate fi Pe) , unde n este numărul de perechi cheie-valoare din tabelul hash.
- Cu toate acestea, este important să alegeți o funcție de hash bună și o dimensiune adecvată pentru tabelul de hash pentru a minimiza probabilitatea de coliziuni și pentru a asigura o performanță bună.
- The complexitatea spatiului a unui tabel hash folosind înlănțuire separată depinde de dimensiunea tabelului hash și de numărul de perechi cheie-valoare stocate în tabelul hash.
- Tabelul hash în sine ia O(m) spațiu, unde m este capacitatea tabelului hash. Fiecare nod de listă conectat ia O(1) spațiu și pot exista cel mult n noduri în listele legate, unde n este numărul de perechi cheie-valoare stocate în tabelul hash.
- Prin urmare, complexitatea totală a spațiului este O(m + n) .
Concluzie:
În practică, este important să alegeți o capacitate adecvată pentru tabelul hash pentru a echilibra utilizarea spațiului și probabilitatea de coliziuni. Dacă capacitatea este prea mică, probabilitatea de coliziuni crește, ceea ce poate cauza degradarea performanței. Pe de altă parte, dacă capacitatea este prea mare, tabela hash poate consuma mai multă memorie decât este necesar.