• Non ci sono risultati.

Tabelle hash

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Tabelle hash"

Copied!
8
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 8 pagine )

Testo completo

(1)

Tabelle hash

(2)

Tabelle hash

●

Soluzione standard per il problema del dizionario dinamico:

–

Insert(S,x): aggiungi chiave x ad S

–

Search(S,x): determina se x appartiene ad S

(3)

Tabelle hash

●

Soluzione standard per il problema del dizionario dinamico:

–

Insert(S,x): aggiungi chiave x ad S

–

Search(S,x): determina se x appartiene ad S

Hashing è una possibile soluzione.

Gestione dei Conflitti tramite:

(4)

Inserzione/Ricerca

4 \ 3

1 \

7 2 \

h: U → T

(5)

Inserzione/Ricerca

4 \ 3

1 \

7 2 \

h: U → T

h(9)

key:9

(6)

Inserzione/Ricerca

4 \ 3

1

7 2 \

h: U → T

h(9) key:9

9 /

(7)

Prototipo

typedef struct lista_el { int dato;

struct lista_el *succ;

} elemento;

int main() {

elemento ** tabella = NULL;

int n, dimensione;

...

dimensione = 2*n;

tabella =

(elemento **)malloc(dimensione*sizeof(elemento*));

if(tabella == NULL) exit(1);

for(i=0; i < dimensione; i++)

(8)

Prova Esame

●

http://ornellaia.isti.cnr.it:8888/

Riferimenti

Scarica adesso ( PDF - 8 pagine - 95.35 KB )

Documenti correlati

Alcune istruzioni R per le tabelle di contingenza

## vettori contenenti le etichette delle variabili riga e colonna rownames(AS)[1]; rownames(AS)[2]. dim(AS) ## vettore con due

Alcune istruzioni R per le tabelle di contingenza

## vettori contenenti le etichette delle variabili riga e colonna rownames(AS)[1]; rownames(AS)[2]. dim(AS) ## vettore con due

Hashing e Tabelle Hash

• Con un appropriato dimensionamento della tabella hash, è possibile avere nel caso medio un costo (1) per tutte le operazioni. ‣ Intuitivamente, le liste di trabocco sono

1 Funzioni di hash modulari

Se si considera ogni chiave c come un intero (di |c| bit), è possibile trasformarla in un indirizzo considerando il resto della divisione (modulo) per M :. H(c) =

Tabelle hash

• quando, in seguito a un inserimento, si ha α = 1 (cioè ogni lista contiene in media 1 elemento), si crea una nuova tabella di dimensione 2M (cioè doppia), vi si trasferiscono i

TABELLE HASH - esercizi

Data una tabella hash T in cui le collisioni sono risolte con le liste di trabocco, definire una procedura di ricerca di una chiave che sposti la chiave cercata, se presente

Lezione 10 Tabelle Hash

Scrivere un programma che legga da tastiera una sequenza di n interi NON distinti e li inserisca senza duplicati in una tabella hash di dimensione 2n posizioni utilizzando

Indice delle tabelle Indice delle tabelle Indice delle tabelle Indice delle tabelle

[3] Vehlow J., Bergfeldt B., Hunsinger H., Jay K., Mark F., Tange L., Drohmann D., and Fisch H., Recycling of Bromine from Plastics Containing Brominated Flame Retardants in