Hash table: differenze tra le versioni

Versione delle 12:28, 28 nov 2009

Versione attuale delle 22:57, 1 ago 2025

(89 versioni intermedie di 49 utenti non mostrate)

Riga 1:

{{Algoritmo

In [[informatica]] una '''hash table''', detta anche '''hash map''', in italiano '''tabella hash''' è una [[struttura dati]] usata per mettere in corrispondenza una data ''chiave'' con un dato ''valore''. Viene usata per l'implementazione di [[Struttura dati#Strutture dati astratte|strutture dati astratte]] associative come Map o [[set (informatica)|Set]].

| classe = [[Struttura dati]]

Può usare qualsiasi tipo di dato come indice e tutte le operazioni si possono fare in tempo circa costante T(n) = ([[notazione O grande|O]](1)).

| immagine = HASHTB08.svg

L'hash table è molto utilizzata nei metodi di ricerca nominati Hashing.

| didascalia = Una piccola rubrica telefonica come esempio di hash table.

L'hashing è un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quali le chiavi di ricerca non presentano queste proprietà. Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece che muoversi nella struttura data in funzione dell'esito dei confronti tra chiavi, si cerca di accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella.

|struttura dati = Tabella Hash|ottimale = Spesso|spazio = O(n)}}

Esistono vari tipi di algoritmi di hashing. L'hashing è un problema classico dell'informatica; molti algoritmi sono stati proposti, studiati a fondo e impiegati in pratica. Due metodi molto diffusi sono l'hashing statico e l'hashing estendibile e lineare, metodi utilizzati anche dai programmi [[DBMS]].

[[Image:HASHTB08.svg|thumb|362px|right|Una piccola rubrica telefonica come esempio di hash table.]]

{{F|programmazione|febbraio 2013}}

==Funzionamento e Implementazione==

In [[informatica]] una '''''hash table''''' o '''''hash map''''', in italiano '''tabella hash''' o '''mappa hash''', è una [[struttura dati]] usata per mettere in corrispondenza una data chiave con un dato valore. Viene usata per l'implementazione di [[Struttura dati#Strutture dati astratte|strutture dati astratte]] associative come le mappe o i [[set (informatica)|set]].

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la ''funzione di hash'': il dato da indicizzare viene trasformato da un'apposita funzione di [[hash]] in un intero compreso tra 0 ed n-1 che viene utilizzato come indice in un [[array]] di lunghezza n. Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di [[hash]] ''perfetta'', ovvero totalmente [[iniettiva]], è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo.

Il caso in cui la funzione hash applicata a due chiavi diverse genera un medesimo indirizzo viene chiamato '''collisione''' e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali. Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme.

Molto spesso però, una buona funzione di hash non può bastare, infatti le prestazioni di una ''hash table'' sono fortemente legate anche al cosiddetto [[fattore di carico (Informatica)|fattore di carico]] (''load factor'') calcolato come Celle libere/Elementi presenti e che ci dice quanta probabilità ha un nuovo elemento di collidere con uno già presente nella tabella. Questa probabilità, in realtà, è più alta di quanto si possa pensare, come ci dimostra il [[paradosso del compleanno]]. È bene dunque mantenere il load factor il più basso possibile (di solito un valore di 0.75 è quello ottimale) per ridurre al minimo il numero di collisioni. Questo può essere fatto, ad esempio, ridimensionando l'array ogni volta che si supera il ''load factor'' desiderato.

È molto utilizzata nei metodi di ricerca nominati ''hashing'' ovvero un'estensione della ricerca indicizzata da chiavi che gestisce problemi di ricerca nei quali le chiavi di ricerca non presentano queste proprietà. Una ricerca basata su hashing è completamente diversa da una basata su confronti: invece di muoversi nella struttura data in funzione dell'esito dei confronti tra chiavi, si cerca di accedere agli elementi nella tabella in modo diretto tramite operazioni aritmetiche che trasformano le chiavi in indirizzi della tabella.

==Gestione delle collisioni==

Esistono vari tipi di algoritmi di hashing. Per quanto affermato, in una tabella di hashing ben dimensionata il costo medio di ricerca di ogni elemento è indipendente dal numero di elementi. L'hashing è un problema classico dell'informatica; molti algoritmi sono stati proposti, studiati a fondo e impiegati in pratica. Due metodi molto diffusi sono l'hashing statico e l'hashing estendibile e lineare, metodi utilizzati anche dai [[Database management system|programmi di gestione delle basi di dati]].

== Descrizione ==

=== Funzionamento e implementazione ===

Il primo passo per realizzare algoritmi di ricerca tramite hashing è quello di determinare la ''funzione di hash'': il dato da indicizzare viene trasformato da un'apposita [[funzione di hash]] in un intero compreso tra <math>0</math> ed <math>m-1</math> che viene utilizzato come indice in un [[array]] di lunghezza m. Supponendo che <math>U</math> sia l'universo delle chiavi e <math>T[0 ... m-1]</math> una tabella hash, una funzione hash h, stabilisce una corrispondenza tra <math>U</math> e le posizioni nella tabella hash, quindi:

<math>h\colon U \rightarrow \{0, 1, \dots, m-1\}</math>

Idealmente, chiavi diverse dovrebbero essere trasformate in indirizzi differenti, ma poiché non esiste la funzione di hash ''perfetta'', ovvero totalmente [[iniettiva]], è possibile che due o più chiavi diverse siano convertite nello stesso indirizzo. Il caso in cui la funzione hash applicata a due chiavi diverse genera un medesimo indirizzo viene chiamato collisione e può essere gestito in vari modi. La scelta di una buona funzione di hash è indispensabile per ridurre al minimo le collisioni e garantire prestazioni sempre ottimali. Il risultato migliore si ha con funzioni pseudo-casuali che distribuiscono i dati in input in modo uniforme.

Molto spesso però, una buona funzione di hash può non bastare: infatti le prestazioni di una ''hash table'' sono fortemente legate anche al cosiddetto fattore di carico (''load factor'') calcolato come

:<math>\frac\text{cardinalità insieme di chiavi da inserire}\text{dimensione massima della struttura}</math>

e che dice quanta probabilità ha un nuovo elemento di collidere con uno già presente nella tabella. Questa probabilità, in realtà, è più alta di quanto si possa pensare, come dimostra il [[paradosso del compleanno]]. È bene dunque mantenere il load factor il più basso possibile (di solito un valore di {{Formatnum:0,75}} è quello ottimale) per ridurre al minimo il numero di collisioni. Ciò può essere fatto, ad esempio, ridimensionando l'array ogni volta che si supera il ''load factor'' desiderato.

=== Gestione delle collisioni ===

Di seguito vengono riportati i metodi più diffusi per la gestione delle collisioni.

* '''Open Hash''' (o indirizzamento aperto)

* '''Scansione lineare''': Quando viene incontrata una collisione non si fa altro che utilizzare l'indice successivo a quello che collide, sino a che non si trova una casella libera.

* '''Hash con concatenazione''' (o con lista di trabocco): per ogni cella della tabella di hash si fa corrispondere invece di un elemento, una [[Lista (informatica)|lista]] (solitamente una [[lista concatenata]]). In questo modo un elemento che collide viene aggiunto alla lista corrispondente all'indice ottenuto.

* '''Scansione quadratica''': Quando viene incontrata una collisione non si fa altro che utilizzare l'indice che collide elevato al quadrato con normalizzazione rispetto alla grandezza della tabella dell'indice ottenuto, sino a che non si trova una casella libera.

* '''Hashing doppio''': se facendo l'hash di una chiave si incontra una collisione, allora si somma all'indice ottenuto il risultato di una nuova funzione hash (generalmente diversa dalla prima e che ha come parametro l'indice ottenuto precedentemente), e si tenta l'inserimento nel nuovo indice cosi' ottenuto, riapplicando la seconda funzione sino a che non si trova una casella libera.

== Open Hash ==

* '''Concatenazione''': per ogni cella della tabella di hash si fa corrispondere invece di un elemento, una [[Lista (informatica)|Lista]] (solitamente una [[LinkedList|lista concatenata]]). In questo modo un elemento che collide viene aggiunto alla lista corrispondente all'indice ottenuto.

Nell'indirizzamento aperto''',''' tutti gli elementi sono memorizzati nella tavola hash stessa; ovvero ogni cella della tavola contiene un elemento dell'insieme dinamico o la costante NULL. Quando cerchiamo un elemento, esaminiamo sistematicamente le celle della tavola finché non troviamo l'elemento desiderato o finché non ci accorgiamo che l'elemento non si trova nella tavola.

Diversamente dal concatenamento, non ci sono liste né elementi memorizzati all'esterno della tavola. Quindi nell'indirizzamento aperto, la tavola hash può "riempirsi" al punto tale che non possono essere effettuati altri inserimenti.

Il vantaggio dell'indirizzamento aperto sta nel fatto che esclude completamente i puntatori, ''calcoliamo'' la sequenza delle celle da esaminare (''ispezione'').

Un concetto importante al riguardo è il cosiddetto hashing uniforme'''.''' Rappresenta l'hashing ideale, ovvero ogni cella della tabella ha la stessa probabilità di contenere un dato elemento.

Esistono diverse tecniche di ispezione, le tre tecniche più comunemente utilizzate sono: ispezione lineare, ispezione quadratica e doppio hashing. Tuttavia, nessuna di queste tecniche soddisfa l'ipotesi di hashing uniforme, in quanto nessuna di esse è in grado di generare più di <math>m^2</math> sequenze di ispezione differenti (anziché <math>m!</math>, come richiede l'hashing uniforme).

=== Tecniche comunemente utilizzate di ispezione ===

==== Ispezione lineare ====

<math>h(k,i) = (h^1 (k) + i)\pmod{m}</math>

Quando si incontra una collisione non si fa altro che utilizzare l'indice successivo a quello che collide, sino a che non si trovi una casella libera.

==== Ispezione quadratica ====

<math>h(k,i) = (h^1 (k) + c_1 i + c_2 i^2)\pmod{m}</math>

Quando si incontra una collisione non si fa altro che utilizzare l'indice che collide elevato al quadrato con normalizzazione rispetto alla grandezza della tabella dell'indice ottenuto, sino a che non si trovi una casella libera.

==== Doppio Hashing ====

<math>h(k,i) = (h_1 (k) + i h_2 (k))\pmod{m}</math> dove, per esempio possiamo porre <math>h_1 (k) = k \pmod{m}</math> e <math>h_2 (k) = 1 + (k \pmod{m^1})</math>.

Se facendo l'hash di una chiave si incontra una collisione, allora si somma all'indice ottenuto il risultato di una nuova funzione hash (generalmente diversa dalla prima e che ha come parametro l'indice ottenuto precedentemente), e si tenta l'inserimento nel nuovo indice così ottenuto, riapplicando la seconda funzione sino a che non si trovi una casella libera.

== Hashing statico ==

== Hashing statico ==

Nell'hashing statico si utilizza il concetto di bucket, che è l'insieme di pagine contenenti le etichette dei record di dati.

Se una pagina bucket primaria è piena, viene creata una pagina di overflow. Per cercare l'etichetta corrispondente alla chiave <math>k</math> (<math>M =</math> numero di bucket) si utilizza la seguente formula di [[hash]]

<math>h(k) = \mbox{bucket}</math> a cui appartiene l'etichetta.

La funzione di hash <math>h</math> agisce sul campo della chiave di ricerca del record <math>r</math> e deve distribuire i valori su <math>0,...,M-1</math> (<math>M</math> bucket). Le prestazioni della ricerca dipendono molto dalla funzione <math>h</math>.

Riga 29 ⟶ 69:

===Esempio di funzione hash===

<math>h(k) = (a*k+b) mod \bmod{M}</math> (con <math>a</math> e <math>b</math> costanti)

== Hashing estendibile ==

Riga 36 ⟶ 76:

Nell'hashing estendibile si parla di profondità di directory e si intende il numero minimo di bit che permette di rappresentare il numero di elementi contenuti nella directory.

== Hashing lineare ==

L'hashing lineare, come accenatoaccennato nel paragrafo precendenteprecedente, permette di risolvere il problema delle lunghe catene di overflow senza l'utilizzo delle directory.

L'idea di base è quella di utilizzare una famiglia di funzioni hash h0<math>h_0,h1h_1,... hnh_n</math> dove hi<math>h_i</math> ha un range che è la metà di quello di hi<math>h_i+1</math>. Questo vuol dire che il range di h1<math>h_1</math> è <math>2^1 N</math>

=== Esempio ===

Se <math>N = 32</math> allora il numero mininominimo di bit per la rappresentazione del numero è 5. Quindi h0<math>h_0 = h mod\bmod 2^0 N</math> cioè h0<math>h_0 = h mod\bmod 32</math>

La prossima funzione h2<math>h_2</math> avrà range <math>5 + 1</math> e potrà rapprensetarerappresentare i bucket da 0 a 63. La funzione di hash sarà come segue h1<math>h_1 = h mod\bmod 2 ^ 1 * 32</math>

==Bilanciamento spazio/tempo==

Riga 49 ⟶ 89:

| align="center" | '''Spazio''' || align="center" | '''Tempo'''

|-

| align="center" | <math>m = 1</math> || align="center" | [[<math>O-grande|O]](n)</math>

|-

| align="center" | <math>m < n</math> || align="center" | [[O-grande|<math>O]](1 + &\alpha;)</math>

|-

| align="center" | <math>m »\gg n</math> || align="center" | [[<math>O-grande|O]](1)</math>

|}

Ad ''<math>n''</math> corrisponde il numero di elementi presenti nell'array, ad ''<math>m''</math> il numero di posti disponibili mentre &<math>\alpha;</math> è il fattore di carico.

==Analisi del costo di scansione==

Il numero di passi da effettuare per una scansione completa della tabella è data nel caso medio da:

Il numero di passi ad effettuare una scansione completa della tabella è data nel caso medio da:

{| border=1 cellspacing=1 align="center" cellpadding="1"

Riga 70 ⟶ 109:

|}

dove &<math>\alpha;</math> è il [[fattore di carico]].

==Bibliografia==

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, ''Introduzione agli algoritmi''. Jackson Libri, 2003, ISBN 88-256-1421-7.

== Voci correlate ==

Riga 76 ⟶ 118:

==Altri progetti==

{{interprogetto|preposizione=sull'}}

== Collegamenti esterni ==

{{Interprogetto|commons=Category:Hash tables}}

* {{Collegamenti esterni}}

* {{FOLDOC|hash coding|hash coding}}

* {{Cita web|url=http://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/hash.pdf|titolo=Note su tabelle hash|cognome=Luccio|nome=Fabrizio|wkautore=Fabrizio Luccio|lingua=italiano|formato=pdf|accesso=20 giugno 2017}}

{{strutture dati}}

[[Categoria:Strutture dati]]

{{Controllo di autorità}}

{{Portale|informatica}}

[[Categoria:Strutture dati]]

[[cs:Hašovací tabulka]]

[[Categoria:Algoritmi di ricerca]]

[[da:Hashtabel]]

[[de:Hashtabelle]]

[[en:Hash table]]

[[es:Tabla hash]]

[[fa:جدول هش]]

[[fi:Hajautustaulu]]

[[fr:Table de hachage]]

[[he:טבלת גיבוב]]

[[hr:Hash tablica]]

[[ja:ハッシュテーブル]]

[[lt:Dėstymo lentelė]]

[[nl:Hashtabel]]

[[nn:Hashtabell]]

[[no:Hashtabell]]

[[pl:Tablica mieszająca]]

[[pt:Tabela de dispersão]]

[[ru:Хеш-таблица]]

[[sk:Hašovacia tabuľka]]

[[sr:Хеш табела]]

[[sv:Hashtabell]]

[[th:ตารางแฮช]]

[[zh:哈希表]]