Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Introduciamo una nuova struttura dati che ci permette di superare entrambe le limitazioni di una tabella

realizzata tramite array.

Limitazioni della tabella: le chiavi devono essere numeri interi in un intervallo prefissato

Introdurremo una funzione di hash che assegna dei valori numerici (interi in un intervallo prefissato) a delle chiavi

generiche

Seconda limitazione della tabella: la memoria non viene utilizzata in maniera efficiente

Useremo un array di bucket (“secchi”), cosicché ogni indice dell'array possa essere associato a più elementi del

dizionario

Il Codice hash

CODICE HASH : È una funzione che ha come dominio l’insieme delle chiavi generiche

in esame e come codominio un sottoinsieme dei numeri interi.

(In Java la classe Object mette a disposizione il metodo hashCode che restituisce un int con buone proprietà

di distribuzione uniforme.

Se il metodo hashCode non viene ridefinito, esso associa ad un oggetto un valore numerico calcolato in base all’indirizzo

dell’oggetto in memoria. L’esistenza di questo metodo rende possibile l’utilizzo

di qualsiasi oggetto come chiave.)

Un codice hash per stringhe trasformare una stringa in un numero Intero)

(

Ricordiamo il significato della notazione posizionale nella rappresentazione di un numero intero

Ciascuna cifra rappresenta un numero che dipende dal suo valore intrinseco e dalla sua posizione

Usiamo la stessa convenzione per una stringa, dove ogni carattere rappresenta un numero che dipende

 Dal suo valore come carattere nella codifica Unicode

 Dalla sua posizione nella stringa

Il valore numerico associato ad una stringa è quindi calcolato in questo modo:

Per la base spesso si usa un numero primo come valore di base (ad esempio 31), perché questo “mescola” bene i valori,

ovvero stringhe diverse hanno con buona probabilità codici hash diversi.

In alternativa la base sarà (come per la notazione posizionale di interi) il numero di simboli diversiche per la codifica

16

Unicode è 2 = 65536.

C'è ancora un problema: l’intervallo di variabilità delle chiavi deve essere noto a priori per dimensionare la tabella.

Affrontiamo il problema in questo modo:

 Prefissiamo la dimensione della tabella in modo arbitrario

 Quindi definiamo di conseguenza l’intervallo di variabilità delle chiavi utilizzabili: il valore massimo consentito è

la lunghezza della tabella

MAPPA DI COMPRESSIONE : È una funzione di trasformazione delle chiavi che modifica la funzione h in modo che

1

tutti i valori numerici associati alle chiavi ricadano all’interno dell’intervallo prefissato.

Il codominio di h è il sottoinsieme [0, N - 1] dei numeri interi, dove N coincide con la dimensione della tabella.

2

FUNZIONE DI HASH : È la composizione delle funzioni h (codice hash) e h (mappa di compressione)

1 2

Una funzione di hash ha:

 Dominio: l’insieme delle chiavi che identificano univocamente i dati da inserire nel dizionario

 Codominio: l’insieme degli indici validi per accedere ad elementi della tabella

Il risultato dell’applicazione della funzione di hash ad una chiave si chiama chiave ridotta.

Una tabella che usa chiavi ridotte si chiama tabella hash (hash table).

Bucket in una tabella hash

HASH

: Quando due elementi hanno chiavi diverse ma uguali chiavi ridotte.

Per come è definita, una funzione di hash è generalmente non biunivoca perché il dominio ha dimensione maggiore del

codominio.


PAGINE

2

PESO

458.28 KB

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Informatica 1
Corso di laurea: Corso di laurea in ingegneria dell'informazione
SSD:
Università: Padova - Unipd
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher enricopava di informazioni apprese con la frequenza delle lezioni di Informatica 1 e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Padova - Unipd o del prof Avanzini Federico.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Informatica 1

Informatica I - array bidimensionali e array paralleli
Appunto
Informatica I - Object Oriented Programming OOP e obiettivi e principi di design
Appunto
Informatica I - come realizzare una classe in java
Appunto
Informatica I - il computer e la programmazione
Appunto