UN tabella hash è una struttura dati che consente l'inserimento, la cancellazione e il recupero rapido dei dati. Funziona utilizzando una funzione hash per mappare una chiave su un indice in un array. In questo articolo implementeremo una tabella hash in Python utilizzando concatenamenti separati per gestire le collisioni.
Componenti dell'hashing
Il concatenamento separato è una tecnica utilizzata per gestire le collisioni in una tabella hash. Quando due o più chiavi vengono mappate allo stesso indice nell'array, le memorizziamo in un elenco collegato in quell'indice. Ciò ci consente di archiviare più valori nello stesso indice e di essere comunque in grado di recuperarli utilizzando la relativa chiave.
Modo per implementare la tabella hash utilizzando il concatenamento separato
Modo per implementare la tabella hash utilizzando il concatenamento separato:
Crea due classi: ' Nodo ' E ' HashTable '.
IL ' Nodo La classe rappresenterà un nodo in un elenco collegato. Ogni nodo conterrà una coppia chiave-valore, nonché un puntatore al nodo successivo nell'elenco.
Python3
class> Node:> >def> __init__(>self>, key, value):> >self>.key>=> key> >self>.value>=> value> >self>.>next> => None> |
>
>
La classe 'HashTable' conterrà l'array che conterrà gli elenchi collegati, nonché i metodi per inserire, recuperare ed eliminare i dati dalla tabella hash.
Python3
class> HashTable:> >def> __init__(>self>, capacity):> >self>.capacity>=> capacity> >self>.size>=> 0> >self>.table>=> [>None>]>*> capacity> |
>
>
IL ' __caldo__ Il metodo ‘ inizializza la tabella hash con una determinata capacità. Imposta il ' capacità ' E ' misurare ' variabili e inizializza l'array su 'None'.
Il metodo successivo è il ' _hash ' metodo. Questo metodo accetta una chiave e restituisce un indice nell'array in cui deve essere archiviata la coppia chiave-valore. Utilizzeremo la funzione hash incorporata di Python per eseguire l'hashing della chiave e quindi utilizzare l'operatore modulo per ottenere un indice nell'array.
Python3
def> _hash(>self>, key):> >return> hash>(key)>%> self>.capacity> |
>
>
IL 'inserire' Il metodo inserirà una coppia chiave-valore nella tabella hash. Prende l'indice in cui la coppia deve essere archiviata utilizzando il comando ' _hash ' metodo. Se non è presente alcun elenco collegato in quell'indice, crea un nuovo nodo con la coppia chiave-valore e lo imposta come capo dell'elenco. Se è presente un elenco collegato in corrispondenza di quell'indice, scorrere l'elenco finché non viene trovato l'ultimo nodo o la chiave esiste già e aggiorna il valore se la chiave esiste già. Se trova la chiave, aggiorna il valore. Se non trova la chiave, crea un nuovo nodo e lo aggiunge in testa alla lista.
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> |
metodo java tostring
>
>
IL ricerca Il metodo recupera il valore associato a una determinata chiave. Per prima cosa ottiene l'indice in cui deve essere archiviata la coppia chiave-valore utilizzando il file _hash metodo. Quindi cerca la chiave nell'elenco collegato in quell'indice. Se trova la chiave, restituisce il valore associato. Se non trova la chiave, rilancia a Errore chiave .
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)> |
>
>
IL 'rimuovere' Il metodo rimuove una coppia chiave-valore dalla tabella hash. Per prima cosa ottiene l'indice in cui la coppia dovrebbe essere archiviata utilizzando il metodo ` _hash `metodo. Quindi cerca la chiave nell'elenco collegato in quell'indice. Se trova la chiave, rimuove il nodo dall'elenco. Se non trova la chiave, solleva un ` Errore chiave `.
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__’ metodo che restituisce una rappresentazione di stringa della tabella hash.
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)> |
>
>
Ecco l'implementazione completa della classe '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> |
>
>Produzione
True False 2 4 3>
Complessità temporale e complessità spaziale:
- IL complessità temporale del inserire , ricerca E rimuovere I metodi in una tabella hash che utilizzano concatenamenti separati dipendono dalla dimensione della tabella hash, dal numero di coppie chiave-valore nella tabella hash e dalla lunghezza dell'elenco collegato su ciascun indice.
- Supponendo una buona funzione hash e una distribuzione uniforme delle chiavi, la complessità temporale prevista di questi metodi è O(1) per ogni operazione. Tuttavia, nel peggiore dei casi, la complessità temporale può diminuire SU) , dove n è il numero di coppie chiave-valore nella tabella hash.
- Tuttavia, è importante scegliere una buona funzione hash e una dimensione adeguata per la tabella hash per ridurre al minimo la probabilità di collisioni e garantire buone prestazioni.
- IL complessità spaziale di una tabella hash che utilizza un concatenamento separato dipende dalla dimensione della tabella hash e dal numero di coppie chiave-valore archiviate nella tabella hash.
- La tabella hash stessa accetta O(m) spazio, dove m è la capacità della tabella hash. Ogni nodo dell'elenco collegato prende O(1) spazio e possono esserci al massimo n nodi negli elenchi collegati, dove n è il numero di coppie chiave-valore archiviate nella tabella hash.
- Pertanto, la complessità spaziale totale è O(m + n) .
Conclusione:
In pratica, è importante scegliere una capacità adeguata per la tabella hash per bilanciare l’utilizzo dello spazio e la probabilità di collisioni. Se la capacità è troppo piccola, aumenta la probabilità di collisioni, che possono causare un degrado delle prestazioni. D'altra parte, se la capacità è troppo grande, la tabella hash può consumare più memoria del necessario.