Post on 01-May-2015
transcript
Tecniche HASHTecniche HASH
Corso (B) di ProgrammazioneCorso (B) di ProgrammazioneCDL in Informatica I livelloCDL in Informatica I livelloA.A. 2003-2004A.A. 2003-2004DIB - Università di BariDIB - Università di Bari
dal materiale didattico (aa 2002-03) di. S. Ferilli e testo consigliatp Dromey
Tecniche HashTecniche HashObiettivoObiettivo
Ritrovare un elemento esaminando solo Ritrovare un elemento esaminando solo pochi elementi della tabellapochi elementi della tabella
EsempioEsempio::a: a: |10|12|20|23|27|30|31|39|42|44|45|49|53|57|60||10|12|20|23|27|30|31|39|42|44|45|49|53|57|60|
a(1)a(1) a(8) a(8) a(15) a(15) Trovare il record con campo chiave uguale a 44 Trovare il record con campo chiave uguale a 44
accedendo al massimo a 3 elementi prima di accedendo al massimo a 3 elementi prima di terminare con successoterminare con successo
Tecniche HashTecniche Hash
Caso estremoCaso estremo Trovare l’elemento cercato in Trovare l’elemento cercato in un soloun solo tentativo tentativo
Tutto ciò che si sa è il valore dell’elemento cercatoTutto ciò che si sa è il valore dell’elemento cercato Inserire ciascun elemento in posizione coincidente col Inserire ciascun elemento in posizione coincidente col
suo valoresuo valore Poco praticoPoco pratico Esempio: Esempio: Numeri telefonici di 7 cifreNumeri telefonici di 7 cifre
10000000 di elementi per memorizzarne solo 15!10000000 di elementi per memorizzarne solo 15! Ottimizzazione dell’occupazione di memoriaOttimizzazione dell’occupazione di memoria
Array di dimensione vicina al numero massimo di Array di dimensione vicina al numero massimo di elementi che saranno memorizzatielementi che saranno memorizzati
Tecniche HashTecniche HashFunzioni di AccessoFunzioni di Accesso
Necessità di ricondurre ciascun valore ad un Necessità di ricondurre ciascun valore ad un indice valido dell’arrayindice valido dell’array
Normalizzazione dei datiNormalizzazione dei dati EsempioEsempio: 15 elementi, valore massimo nella lista 60: 15 elementi, valore massimo nella lista 60
Applicare alla chiave la seguente trasformazione:Applicare alla chiave la seguente trasformazione:Chiave diviso 4 & ArrotondamentoChiave diviso 4 & Arrotondamento
Potrebbe Potrebbe non essere notonon essere noto il massimo valore degli il massimo valore degli elementi che si tratterannoelementi che si tratteranno Impossibile stabilire a priori una funzione di Impossibile stabilire a priori una funzione di
normalizzazionenormalizzazione Necessità di un metodo più generaleNecessità di un metodo più generale
Tecniche HashTecniche HashFunzioni di AccessoFunzioni di Accesso
Soluzione miglioreSoluzione migliore Sufficiente una Sufficiente una trasformazionetrasformazione delle chiavi delle chiavi
che dia un indice valido dell’arrayche dia un indice valido dell’array
EsempioEsempio:: array indicizzato da 1 a 15array indicizzato da 1 a 15 Calcolare il modulo 15 della chiaveCalcolare il modulo 15 della chiave
Compreso fra 0 e 14Compreso fra 0 e 14 Aggiungere un’unitàAggiungere un’unità
Valori compresi fra 1 e 15Valori compresi fra 1 e 15
Tecniche HashTecniche HashFunzioni di AccessoFunzioni di Accesso
h: K h: K {0, 1, 2, …, {0, 1, 2, …, mm–1}–1} KK insieme dei valori distinti che il campo insieme dei valori distinti che il campo
chiave può assumerechiave può assumere mm dimensione del vettore in cui si intende dimensione del vettore in cui si intende
memorizzare gli elementi della tabellamemorizzare gli elementi della tabella
KK sottoinsieme dei numeri naturali sottoinsieme dei numeri naturali Possibile funzione di accesso:Possibile funzione di accesso:
h(k) = k MOD mh(k) = k MOD m Sempre compreso fra 0 e Sempre compreso fra 0 e mm – 1 – 1
Tecniche HashTecniche HashRappresentazione della ChiaveRappresentazione della Chiave
KK Non sottoinsieme dei numeri naturali Non sottoinsieme dei numeri naturali Insieme di stringhe alfanumericheInsieme di stringhe alfanumeriche
La funzione hash è numericaLa funzione hash è numerica Per applicarla ad una chiave non numerica, bisogna Per applicarla ad una chiave non numerica, bisogna
associare alla chiave un valore numericoassociare alla chiave un valore numerico
Necessità di definire funzioni hash generaliNecessità di definire funzioni hash generali Associazione di un valore numerico ad Associazione di un valore numerico ad
una chiave di qualunque tipouna chiave di qualunque tipo Applicazione della funzione hash Applicazione della funzione hash
numerica a tale valorenumerica a tale valore
Tecniche HashTecniche HashRappresentazione della ChiaveRappresentazione della Chiave
Un possibile metodo di codificazioneUn possibile metodo di codificazione Considerare la rappresentazione binaria della chiave Considerare la rappresentazione binaria della chiave kk, ,
binbin((kk)) Se la chiave non è numerica, è data dalla concatenazione Se la chiave non è numerica, è data dalla concatenazione
della rappresentazione binaria di ciascun carattere che la della rappresentazione binaria di ciascun carattere che la componecompone
Calcolare il numero intero positivo corrispondente alla Calcolare il numero intero positivo corrispondente alla rappresentazione binaria della chiave, rappresentazione binaria della chiave, intint((binbin((kk))))
EsempioEsempio:: K = AK = A44 con A = {‘A’,’B’,…,’Z’}con A = {‘A’,’B’,…,’Z’}
BB AA RR IIASCII ASCII 10000101000010 10000011000001 10100101010010 10010011001001
int(bin(k)) = ord(‘B’) int(bin(k)) = ord(‘B’) · 128· 12833 + + ord(‘A’) ord(‘A’) · 128· 12822 + + ord(‘R’) ord(‘R’) · 128 + · 128 + ord(‘I’)ord(‘I’) = = 66 66 · 128· 12833 + + 65 65 · 128· 12822 + + 82 82 · 128 · 128 + + 7373 = … = …
Tecniche HashTecniche HashRappresentazione della ChiaveRappresentazione della Chiave
Un altro metodo di codificaUn altro metodo di codifica Lasciare invariate le altre cifre numeriche e Lasciare invariate le altre cifre numeriche e
trasformare le lettere A, B, …, Z nei numeri trasformare le lettere A, B, …, Z nei numeri decimali 11, 12, …, 36decimali 11, 12, …, 36
Sommare i numeri associati ai caratteri che Sommare i numeri associati ai caratteri che compongono la chiavecompongono la chiave
EsempioEsempio::A.S.L. ‘BA16’A.S.L. ‘BA16’
12 12 · 36· 3633 + + 11 11 · 36· 3622 + + 1 1 · 36 + 6 = · 36 + 6 = 574.170 574.170
Tecniche HashTecniche HashCollisioniCollisioni
Associazione, da parte di una Associazione, da parte di una trasformazione, della stessa posizione a trasformazione, della stessa posizione a chiavi distintechiavi distinte SinonimiSinonimi
EsempioEsempio:: (chiave MOD 15) + 1(chiave MOD 15) + 1 Posizione 1 Posizione 1 30, 45, 6030, 45, 60 Posizione 9 Posizione 9 23, 5323, 53 Posizione 13 Posizione 13 12, 27, 42, 12, 27, 42,
5757
Ciascuna posizione dell’array può Ciascuna posizione dell’array può contenere al più un elementocontenere al più un elemento Ridurre al massimo le collisioniRidurre al massimo le collisioni Gestirle quando si verificanoGestirle quando si verificano
Tecniche HashTecniche HashCollisioniCollisioni
Funzioni di Funzioni di hashing perfettohashing perfetto (evitano del tutto i (evitano del tutto i duplicati) rare, anche per grandi tabelleduplicati) rare, anche per grandi tabelle EsempioEsempio: : paradosso del compleannoparadosso del compleanno
Dato un gruppo di 23 persone, ci sono più del 50% di Dato un gruppo di 23 persone, ci sono più del 50% di probabilità che due di esse siano nate nello stesso probabilità che due di esse siano nate nello stesso giorno dell’annogiorno dell’anno
In altre parole, se scegliamo una funzione aleatoria In altre parole, se scegliamo una funzione aleatoria che trasforma 23 chiavi in un indirizzo di una tabella che trasforma 23 chiavi in un indirizzo di una tabella di 365 elementi, la probabilità che due chiavi NON di 365 elementi, la probabilità che due chiavi NON collidano è solo 0.4927 (meno della metà)collidano è solo 0.4927 (meno della metà)
Individuare una funzione di accesso che porti Individuare una funzione di accesso che porti ad un numero ridotto di collisioni è un ad un numero ridotto di collisioni è un problema complessoproblema complesso
Tecniche HashTecniche HashCollisioniCollisioni
EsempioEsempio 41413131 10 105050 possibili funzioni da un insieme possibili funzioni da un insieme KK di 31 di 31
elementi in un insieme {1, 2, …, 41} di 41 posizionielementi in un insieme {1, 2, …, 41} di 41 posizioni Solo 41 Solo 41 ·· 40 40 ·· 39 39 ·· … … ·· 11 = 41!/10! 11 = 41!/10! 10 1043 43 ingettiveingettive
Daranno valori distinti per ciascun argomentoDaranno valori distinti per ciascun argomento Solo una ogni 10 milioni eviterà le collisioniSolo una ogni 10 milioni eviterà le collisioni
Scelta dipendente dai particolari valori in KScelta dipendente dai particolari valori in K Occorre studiare Occorre studiare
Buone funzioni di accessoBuone funzioni di accesso Valide strategie per gestire le collisioniValide strategie per gestire le collisioni
Tecniche HashTecniche HashCollisioniCollisioni
Scelta di Scelta di mm critica critica Influenza fortemente il numero di Influenza fortemente il numero di
possibili collisionipossibili collisioni bb base di rappresentazione della chiave base di rappresentazione della chiave
mm = = bbnn è una scelta insoddisfacente è una scelta insoddisfacente Resto della divisione composto sempre dalle Resto della divisione composto sempre dalle nn
cifre di più basso ordine della chiavecifre di più basso ordine della chiave Meglio utilizzare come divisore un Meglio utilizzare come divisore un
numero primo di valore vicino al numero numero primo di valore vicino al numero di elementi che si desiderano riservare di elementi che si desiderano riservare per il vettoreper il vettore
Tecniche HashTecniche HashCollisioniCollisioni
EsempiEsempi Chiave rappresentata in base 10, Chiave rappresentata in base 10, mm = 1000 = 1000
Il resto sarà rappresentato dalle 3 cifre di più Il resto sarà rappresentato dalle 3 cifre di più basso ordine della chiavebasso ordine della chiave Tutte le chiavi che terminano per 893 daranno luogo Tutte le chiavi che terminano per 893 daranno luogo
a collisioni o sinonimiea collisioni o sinonimie2893 MOD 1000 = 1893 MOD 1000 = 8932893 MOD 1000 = 1893 MOD 1000 = 893
Chiave rappresentata in base 2, Chiave rappresentata in base 2, mm = 2 = 2pp
Due numeri con gli stessi Due numeri con gli stessi pp bit finali darebbero bit finali darebbero sempre luogo ad una collisionesempre luogo ad una collisione
Tecniche HashTecniche HashCollisioniCollisioni
Numero di collisioni ridotto drasticamente se Numero di collisioni ridotto drasticamente se accettiamo uno spreco del accettiamo uno spreco del 20%20% di memoria di memoria extraextra EsempioEsempio:: array di 19 elementi invece che di array di 19 elementi invece che di
15 15 (indicizzati da 0 a 18)(indicizzati da 0 a 18)Posizione 0 Posizione 0 57 57 Posizione 8 Posizione 8 27 27Posizione 1 Posizione 1 20, 39 20, 39 Posizione 10 Posizione 10 10 10Posizione 3 Posizione 3 60 60 Posizione 11 Posizione 11 30, 49 30, 49Posizione 4 Posizione 4 23, 42 23, 42 Posizione 12 Posizione 12 12, 31 12, 31Posizione 6 Posizione 6 44 44 Posizione 15 Posizione 15 53 53Posizione 7 Posizione 7 45 45
Collisioni non eliminate del tuttoCollisioni non eliminate del tutto
Tecniche HashTecniche HashGestione delle CollisioniGestione delle Collisioni
Memorizzazione dei valori che collidonoMemorizzazione dei valori che collidono Necessità di mantenere alta anche Necessità di mantenere alta anche
l’efficienza media nel ritrovamentol’efficienza media nel ritrovamento TecnicheTecniche
A scansione internaA scansione interna Sinonimi memorizzati nella stessa tabellaSinonimi memorizzati nella stessa tabella
A scansione esternaA scansione esterna Uso di aree di traboccoUso di aree di trabocco
Tecniche HashTecniche HashTecnica a Scansione InternaTecnica a Scansione Interna
Possono esistere molte locazioni “libere” Possono esistere molte locazioni “libere” nella tabellanella tabella Individuate da un valore speciale “vuoto”Individuate da un valore speciale “vuoto” Utilizzabili per memorizzare gli elementi che Utilizzabili per memorizzare gli elementi che
collidonocollidono Possibile criterioPossibile criterio
Assegnare ad un elemento che collide con Assegnare ad un elemento che collide con un altro la successiva posizione disponibileun altro la successiva posizione disponibile
Tecniche HashTecniche HashMetodo di Scansione LineareMetodo di Scansione Lineare
((Linear probingLinear probing)) Ricerca del prossimo elemento vuoto Ricerca del prossimo elemento vuoto
effettuata esaminando le posizioni contigue effettuata esaminando le posizioni contigue successive secondo la seguente funzione successive secondo la seguente funzione linearelineare in in ii::
posposii (h(k) + i) mod m (h(k) + i) mod m i i 1 1 Posizione a cui si accede la Posizione a cui si accede la ii-esima volta che -esima volta che
una posizione del vettore viene trovata una posizione del vettore viene trovata occupataoccupata
Per Per i = 0:i = 0: pospos00 = h(k) = h(k) Posizione iniziale da controllarePosizione iniziale da controllare
Tecniche HashTecniche HashMetodo di Scansione LineareMetodo di Scansione Lineare
GeneralizzazioneGeneralizzazioneposposii (h(k) + h (h(k) + h · · i) MOD mi) MOD m i i 1 1
hh numero intero positivo primo con numero intero positivo primo con mm Garanzia che la scansione tocchi tutte le Garanzia che la scansione tocchi tutte le
posizioni del vettore prima di riconsiderare posizioni del vettore prima di riconsiderare posizioni già esaminateposizioni già esaminate
Inconveniente: Inconveniente: fenomeno dell’fenomeno dell’agglomerazioneagglomerazione Sequenza di indirizzi scanditi per la chiave Sequenza di indirizzi scanditi per la chiave kk
uguale a quella per le chiavi uguale a quella per le chiavi k’k’ tali che tali cheh(k’) = h(k) + n h(k’) = h(k) + n ·· h h
Tecniche HashTecniche Hash
EsempioEsempio Se la posizione 12 è già occupata dalla chiave Se la posizione 12 è già occupata dalla chiave
12, allora al 31 assegneremo la prima posizione 12, allora al 31 assegneremo la prima posizione libera in avanti, ovvero la 13libera in avanti, ovvero la 13
57 20 39 60 23 42 44 45 47 10 30 12 31 49 5357 20 39 60 23 42 44 45 47 10 30 12 31 49 53
Numero medio di passi compiuti per posizionare tutti Numero medio di passi compiuti per posizionare tutti i 15 elementi: 21/15 i 15 elementi: 21/15 1.41.4 11 elementi posizionati in un solo passo11 elementi posizionati in un solo passo 3 elementi in 2 passi3 elementi in 2 passi 1 solo elemento in 4 passo1 solo elemento in 4 passo
Tecniche HashTecniche HashMemorizzazione degli ElementiMemorizzazione degli Elementi
Dalla chiave di ricerca deriva un valore hash Dalla chiave di ricerca deriva un valore hash usando la funzione modulo (dimensione usando la funzione modulo (dimensione tabella)tabella) posizione posizione chiave MOD m chiave MOD m
Se la posizione indicata dalla funzione hash è Se la posizione indicata dalla funzione hash è già occupata, compi una ricerca lineare in già occupata, compi una ricerca lineare in avanti a partire dalla posizione correnteavanti a partire dalla posizione corrente se tabella(posizione) se tabella(posizione) chiave allora … chiave allora …
Se si raggiunge la fine della tabella senza aver Se si raggiunge la fine della tabella senza aver trovato una posizione libera la ricerca deve trovato una posizione libera la ricerca deve riprendere dall’inizioriprendere dall’inizio Posizione Posizione (posizione + 1) MOD m (posizione + 1) MOD m
Tecniche HashTecniche HashCondizioni di terminazione e controlliCondizioni di terminazione e controlli
posizioneposizione (la ricerca inizia da qui) (la ricerca inizia da qui)
la ricerca di una posizione libera termina quila ricerca di una posizione libera termina qui
2 possibili condizioni di terminazione 2 possibili condizioni di terminazione della ricercadella ricerca Si incontra una cella “vuota”Si incontra una cella “vuota” Si arriva alla posizione di partenza della Si arriva alla posizione di partenza della
ricerca dopo aver controllato tutti gli ricerca dopo aver controllato tutti gli elementielementi
2 controlli (uno per ogni condizione)2 controlli (uno per ogni condizione)
xx
Tecniche HashTecniche HashRiduzione controlliRiduzione controlli
Possibilità di ridurre tale numero attraverso Possibilità di ridurre tale numero attraverso un artificioun artificio Se la posizione indicata dalla funzione Se la posizione indicata dalla funzione
hash è già occupata, vi si pone il valore hash è già occupata, vi si pone il valore ““cella vuotacella vuota”” La condizione 2 (tabella piena) non si potrà mai La condizione 2 (tabella piena) non si potrà mai
verificareverificare La ricerca terminerà forzatamente per via della La ricerca terminerà forzatamente per via della
condizione 1condizione 1 Alla fine si dovrà ripristinare la situazione Alla fine si dovrà ripristinare la situazione
preesistentepreesistente
Tecniche HashTecniche HashRiduzione controlliRiduzione controlli
Bisognerà distinguere la vera causa della Bisognerà distinguere la vera causa della terminazione della ricercaterminazione della ricerca Perché effettivamente è stata trovata una cella vuotaPerché effettivamente è stata trovata una cella vuota Perché la tabella era pienaPerché la tabella era piena
In tal caso si dovrà segnalare l’errore di “tabella In tal caso si dovrà segnalare l’errore di “tabella piena”piena”
Uso di una variabile booleana Uso di una variabile booleana erroreerrore Vera nel caso in cui la tabella sia piena e non abbia Vera nel caso in cui la tabella sia piena e non abbia
spazio per effettuare l’inserimentospazio per effettuare l’inserimento
Tecniche HashTecniche HashAlgoritmo per l’OrdinamentoAlgoritmo per l’Ordinamento
calcola l’indice hash in base alla chiave da memorizzarecalcola l’indice hash in base alla chiave da memorizzareerrore errore false falsesese l’indice associato alla chiave corrisponde ad un elemento l’indice associato alla chiave corrisponde ad un elemento
“vuoto” “vuoto” alloraalloraponi l’elemento da memorizzare in tabellaponi l’elemento da memorizzare in tabella
altrimentialtrimentiponi in posizione iniziale il valore “vuoto”poni in posizione iniziale il valore “vuoto”ripetiripeti
calcola la posizione successiva (modulo calcola la posizione successiva (modulo dimensione tabella)dimensione tabella)finchéfinché non trovi un elemento “vuoto” non trovi un elemento “vuoto”sese la posizione dell’elemento “vuoto” coincide con la posizione dell’elemento “vuoto” coincide con quella iniziale quella iniziale alloraallora
segnala l’errore (errore segnala l’errore (errore true) true)altrimentialtrimenti
poni in tabella l’elemento da memorizzareponi in tabella l’elemento da memorizzareripristina il valore modificato della tabellaripristina il valore modificato della tabella
Tecniche HashTecniche HashAccessoAccesso
Dopo aver memorizzato la tabella, possiamo Dopo aver memorizzato la tabella, possiamo effettuare la ricerca mediante funzioni di effettuare la ricerca mediante funzioni di accessoaccesso Il ritrovamento avverrà con lo stesso procedimentoIl ritrovamento avverrà con lo stesso procedimento
Altrettanto validoAltrettanto valido
Data la chiave dell’elemento da cercare, si Data la chiave dell’elemento da cercare, si genera un indirizzo mediante la funzione hashgenera un indirizzo mediante la funzione hash Se a tale indirizzo si trova la chiave cercata allora la Se a tale indirizzo si trova la chiave cercata allora la
ricerca si può arrestare immediatamente ricerca si può arrestare immediatamente Altrimenti bisogna procedere per ricerca lineare come Altrimenti bisogna procedere per ricerca lineare come
nella fase di memorizzazionenella fase di memorizzazione
Tecniche HashTecniche Hash
3 condizioni di terminazione della ricerca3 condizioni di terminazione della ricerca Si trova la chiave cercata in tabellaSi trova la chiave cercata in tabella
Esito positivoEsito positivo Si incontra una cella “vuota”Si incontra una cella “vuota”
Esito negativoEsito negativo (elemento non trovato) (elemento non trovato) Si arriva alla posizione di partenza della ricerca dopo Si arriva alla posizione di partenza della ricerca dopo
aver controllato tutti gli elementiaver controllato tutti gli elementi Esito negativoEsito negativo (elemento non trovato) (elemento non trovato)
3 controlli (uno per ogni condizione)3 controlli (uno per ogni condizione) Possibilità di ridurre tale numero attraverso un Possibilità di ridurre tale numero attraverso un
artificio analogo a quello per evitare il controllo artificio analogo a quello per evitare il controllo tabella pienatabella piena
Tecniche HashTecniche HashArtificio per la riduzione dei controlliArtificio per la riduzione dei controlli
Dopo aver confrontato la chiave cercata Dopo aver confrontato la chiave cercata con la posizione indicata dalla funzione con la posizione indicata dalla funzione hash e aver scoperto che non sono uguali si hash e aver scoperto che non sono uguali si pone nella posizione di partenza della pone nella posizione di partenza della ricerca proprio la chiave cercataricerca proprio la chiave cercata La condizione 3 di elemento non trovato non La condizione 3 di elemento non trovato non
si potrà mai verificaresi potrà mai verificare In caso di tabella piena ed elemento non In caso di tabella piena ed elemento non
trovato, la ricerca terminerà forzatamente trovato, la ricerca terminerà forzatamente per la condizione 1per la condizione 1
Alla fine si dovrà ripristinare la situazione Alla fine si dovrà ripristinare la situazione preesistentepreesistente
Tecniche HashTecniche HashCausa della terminazione Causa della terminazione
Bisognerà distinguere la vera causa della Bisognerà distinguere la vera causa della terminazione della ricerca:terminazione della ricerca: Perché effettivamente esisteva la chiave in tabellaPerché effettivamente esisteva la chiave in tabella Perché la chiave non esisteva e la tabella era pienaPerché la chiave non esisteva e la tabella era piena
In tal caso si dovrà segnalare che l’elemento non è In tal caso si dovrà segnalare che l’elemento non è stato trovatostato trovato
Necessità di 2 variabili booleaneNecessità di 2 variabili booleane AttivoAttivo
Falsa quando si trova o la chiave o una posizione Falsa quando si trova o la chiave o una posizione vuotavuota
TrovatoTrovato Vera solo nel caso in cui si trovi la chiaveVera solo nel caso in cui si trovi la chiave
Tecniche HashTecniche HashAlgoritmo di RicercaAlgoritmo di Ricerca
calcola l’indice hash come “chiave modulo dimensione calcola l’indice hash come “chiave modulo dimensione tabella”tabella”
imposta imposta attivoattivo e e trovatotrovato in modo da terminare la ricerca in modo da terminare la ricercasese la chiave si trova nella posizione indicata dall’indice hash la chiave si trova nella posizione indicata dall’indice hash
alloraalloraponi le condizioni per la terminazioneponi le condizioni per la terminazione
altrimentialtrimentiponi la chiave nella posizione data dall’indice hashponi la chiave nella posizione data dall’indice hash
mentrementre non è soddisfatta alcuna condizione di terminazione non è soddisfatta alcuna condizione di terminazionecalcola l’indice successivo modulo dimensionecalcola l’indice successivo modulo dimensionesese la chiave si trova nella posizione corrente la chiave si trova nella posizione corrente alloraallora
Poni le condizioni di terminazione e valuta Poni le condizioni di terminazione e valuta se se trovatotrovato è vera è veraaltrimentialtrimenti
sese la posizione è vuota segnala la terminazione la posizione è vuota segnala la terminazioneripristina il valore modificato della tabellaripristina il valore modificato della tabella
Tecniche HashTecniche HashProgramma PascalProgramma Pascal
beginbeginattivo := true; trovato := false; attivo := true; trovato := false; start := chiave MOD dimensione; posizione := start;start := chiave MOD dimensione; posizione := start;ifif tabella[start] = chiave tabella[start] = chiave thenthen begin begin attivo := false; trovato := true; temp := tabella[start] attivo := false; trovato := true; temp := tabella[start] endendelseelse beginbegin temp := tabella[start]; tabella[start] := chiave temp := tabella[start]; tabella[start] := chiave endend;;whilewhile attivo attivo dodo beginbegin posizione := posizione + 1 MOD dimensione;posizione := posizione + 1 MOD dimensione; ifif tabella[posizione] = chiave tabella[posizione] = chiave thenthen beginbegin
attivo := false; attivo := false; ifif posizione <> start posizione <> start thenthen trovato := true trovato := true endend
elseelse ifif tabella[posizione] = vuoto tabella[posizione] = vuoto thenthen attivo := false attivo := false
endend;;tabella[start] := temptabella[start] := tempendend..
Tecniche HashTecniche HashConsiderazioniConsiderazioni
Prestazione valutabile in termini del numero di Prestazione valutabile in termini del numero di elementi della tabella che devono essere elementi della tabella che devono essere esaminati prima della terminazione della esaminati prima della terminazione della ricercaricerca Funzione del Funzione del fattore di caricofattore di carico
Percentuale di posizioni occupate in tabellaPercentuale di posizioni occupate in tabella Si dimostra che, sotto opportune ipotesi statistiche, Si dimostra che, sotto opportune ipotesi statistiche,
sono esaminati mediamente ½[1 + 1/(1 – sono esaminati mediamente ½[1 + 1/(1 – )] )] elementi prima che la ricerca termini con successoelementi prima che la ricerca termini con successo Per Per = 0.8 si hanno mediamente 3 accessi, = 0.8 si hanno mediamente 3 accessi,
qualunque sia la dimensione della tabellaqualunque sia la dimensione della tabella Il costo per una ricerca infruttuosa è maggiore, Il costo per una ricerca infruttuosa è maggiore,
mediamente ½[1 + 1/(1 – mediamente ½[1 + 1/(1 – ))22]]