Tecniche HASH Corso (B) di Programmazione CDL in Informatica I livello A.A. 2003-2004 DIB -...

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


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


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


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 = … = …


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


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


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


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


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


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


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


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]]

Tecniche HASH Corso (B) di Programmazione CDL in Informatica I livello A.A. 2003-2004 DIB -...

Documents

Transcript of Tecniche HASH Corso (B) di Programmazione CDL in Informatica I livello A.A. 2003-2004 DIB -...