Discussione:Hash table

hashing doppio

hei non sono molto certo di una correzione che ho fatto quindi chiedo a chi e' piu' esperto di rettificare eventualmente.

Riguardo all'hashing doppio in caso di collisione, secondo l'articolo vecchio, semplicemente si applicava una funizione hash all'indice collidente per trovarne un altro libero. Cito: "Hashing doppio: se facendo l'hash di un indice si incontra una collisione allora si applica una nuova funzione di hash all'indice ottenuto sino a che non si trova una casella libera."

Invece secondo quanto detto dal mio professore di algoritmica, quanto ottenuto dalla seconda funzione e' necessariamente sommato all'indice collidente ottenuto con la prima, ed e' il valore della somma ad essere utilizzato come nuovo indice-tentativo. Per questo ho cambiato in: "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."

siccome sono formalismi non sono certo della loro universalita', per cui la mia potrebbe essere una modifica inutile da eliminare :) Lik 15:32, 12 gen 2006 (CET)

Ciao, ricordati di firmare le discussioni. La tua versione sembra essere quella corretta. Cito dal Cormen, Introduction to Algorithms:

Double hashing uses a hash function of the form

$h(k,i)=(h1(k)+ih2(k))$ mod $m$

where $h1$ and $h2$ are auxiliary hash functions. The initial probe is to position $T[h1(k)]$; successive probe positions are offset from previous positions by the amount $h2(k)$, modulo $m$. Thus, unlike the case of linear or quadratic probing, the probe sequence here depends in two ways upon the key $k$, since the initial probe position, the offset, or both, may vary. --Jack (sa vût?) 20:16, 9 gen 2006 (CET)

fattore di carico

il link alla parola "fattore di carico" porta a una pagina che non contiene informazioni riguardanti l'accezione informatica. — Questo commento senza la firma utente è stato inserito da Ahasvero (discussioni · contributi) 16:14, 12 set 2007‎ (CEST).