Hashing a indirizzamento aperto

[mathix1]

premetto che stavolta ho letto piu testi e anche varie slide di algoritmi su google, ma continuo a non capire alcune cose:

Scansione lineare:
ho da inserire in una tabella di cardinalità 7 questi elementi: 7, 9, 16, 28, 15
la funzione hash è h(x) = n mod m

ora il mio dubbio è questo:
con la scansione lineare devo usare la funzione hash per ogni elemento o solo per il primo?

7 mod 7 = 0
9 mod 7 = 2
16 mod 7 = 2 <--- la cella 2 è già occupata quindi metto il 16 nella prima cella successiva libera cioè la 3
28 mod 7 = 0 <--- la cella 0 è già occupata quindi metto nella cella successiva libera, cioè 1
15 mod 7 = 1 <---è occupata quindi passa alla prima cella successiva libera, cioè la 4.

e mi ritrovo con 7, 28, 9, 16, 15

oppure calcolo 7 mod 7 = 0, quindi riempio la tabella a partire da 0 mettendo in successione 7,9,16,28,15 ? (credo sia questo metodo del libro di cormen)
e per la cancellazione invece calcolo n mod 7, e se la cella e vuota prendo la successiva piena?

[apatriarca]

In realtà il Cormen modifica la funzione di hash in modo che abbia come secondo argomento il numero di prove di inserimento o ricerca già effettuate. La funzione di hash ha quindi in questo modo la forma:
\( h : X \times {0, \dots, m-1} \to {0, \dots, m-1} \)
dove \(X\) è l'insieme dei valori assumibili dalla chiave. Nel tuo caso hai quindi (visto che dici che cerchi la prima posizione libera successiva) \( h(x, i) = x + i \mod m \). A questo punto nell'algoritmo di inserimento si cerca di inserire \(x\) prima in \(h(x, 0)\), poi in \(h(x,1)\) e così via fino a \(h(x, m-1)\). Se nessuna di quelle posizioni è vuota allora l'inserimento non è possibile. Il metodo è quindi quello del tuo primo esempio. Quello in cui la funzione di hash veniva calcolata ad ogni inserimento. Nota che è anche possibile usare funzioni di hash diverse e quindi visitare i nodi in modo diverso. Per esempio si potrebbe anche usare una tabella di hash come \( h(x, i) = x - p \, i \mod m \) dove \(p\) è primo. Prendiamo per esempio \(p = 3\). In questo caso avremmo:
\( 7 \mod 7 = 0 \) e quindi inseriamo il \(7\) nella posizione \(0\),
\(9 \mod 7 = 2 \) e quindi inseriamo il \(9\) nella posizione \(2\),
\(16 \mod 7 = 2 \) e quindi dobbiamo andare avanti a cercare..
\(16+3 \mod 7 = 5 \) e quindi inseriamo il \(16\) nella posizione \(5\),
\(28 \mod 7 = 0 \) e quindi dobbiamo andare avanti a cercare..
\(28+3 \mod 7 = 3 \) e quindi inseriamo il \(28\) nella posizione \(3\),
\(15 \mod 7 = 1 \) e quindi inseriamo il \(15\) nella posizione \(1\).
Nota ora che nonostante la semplice modifica nella ricerca, aggiustando la funzione di hash usata, abbiamo ridotto il numero di celle visitate. Con questa funzione abbiamo infatti visitato \(7\) celle in tutto, mentre con la funzione di hash da te usata avevamo bisogno di visitarne \(10\) (se non ho sbagliato i conti).

[mathix1]

non mi è chiara però la cancellazione, se dovessi cancellare le chiavi 7 e poi 28, si fa nel modo seguente??

(uso il carattere _ per indicare le celle vuote)
|7|28|9|16|15|_|_ |
eliminando 7 ci ritroviamo con questa tabella |_|28|9|16|15|_|_|
spostiamo tutte le celle a sinistra
|28|9|16|15|_|_|_|
e cancelliamo anche il 28 e spostiamo tutto a sinistra
|9|16|15|_|_|_|_|

se si, questo procedimento di cancellazione vale anche per l'hashing doppio e l'hashing quadratico?
il docente ha fatto solo l'esempio qui sopra e solo sul lineare.

[apatriarca]

Ma non puoi spostarlo in questo modo perché gli elementi non sono più nelle posizioni date dal metodo di inserimento. Inoltre spostare tutti gli elementi è un'operazione abbastanza costosa. Non puoi però neanche semplicemente cancellare l'elemento in quella posizione perché se no la ricerca dovrebbe visitare tutte le celle e diventare quindi lineare. La soluzione è quindi quella di segnare la cella come "eliminata"*. Segno con una x le celle eliminate. Parto quindi con
|7|28|9|16|15|_|_|
e cerco di eliminare il 7, lo trovo subito nella sua posizione di hash e allora lo segno da eliminare
|x|28|9|16|15|_|_|
In questo modo la funzione di inserimento può inserire al suo posto qualche valore e la funzione di ricerca sa di dover eliminare il valore ma non fermarsi nella ricerca. Se a questo punto vogliamo eliminare il 28 cerchiamo prima nella posizione 0 e notando che è eliminata la saltiamo passando alla posizione successiva, cioè 1, e lo eliminiamo ottenendo alla fine quindi
|x|x|9|16|15|_|_|
Questa soluzione vale ovviamente anche per gli altri due tipi di hashing.

* Possiamo ad esempio avere un array di unsigned char lungo \( \left\lceil m / 8 \right\rceil \) che contenga un bit per ogni cella.

[mathix1]

e con questo thread penso di aver risolto tutti i dubbi che mi erano rimasti su algoritmi.

se passerò l'esame è grazie ai tuoi preziosi consigli, grazie mille

[apatriarca]

In realtà l'open hashing non è usato molto spesso quando si desidera eliminare gli elementi manualmente. Se si implementa infatti la rimozione, inserimento e ricerca non dipendono più dal fattore di carico. Considera ad esempio il caso in cui tutti gli elementi siano stati eliminati. In questo caso il fattore di carico è zero, ma una ricerca dovrebbe comunque visitare tutti gli elementi prima di stabilire che una chiave non sia presente.

Un caso in cui queste idee sono molto usate è invece l'implementazione di cache (in hardware o in software). Supponi di dover accedere ad una grossa quantità di dati (nell'ordine anche di centinaia di GB) in modo più o meno casuale. Le memorie RAM moderne non sono in grado di tenere tutti questi dati in memoria ed è impensabile accedere in continuazione al file attraverso le normali funzioni di I/O del C (se il file fosse poi compresso si dovrebbe anche in decomprimere in continuazione). Quello che si fa normalmente è (oltre ad usare tecniche particolari di I/O come Memory-mapped files) creare una cache che mantenga in memoria i dati caricati (elaborati o meno a seconda dei casi). La cache ha spesso una dimensione fissa ed è necessario avere metodi efficienti per stabilire se un particolare dato è presente nella cache e per inserire un nuovo elemento (cancellandone potenzialmente uno già presente). Si possono usare diverse strategie per farlo. Un primo metodo potrebbe ad esempio essere quello di usare una lista di priorità di dimensione massima fissata, ma, soprattutto in hardware, è comune fare uso di funzioni di hash in modo equivalente all'open hashing che hai imparato. Spesso il numero massimo di posizioni cercate è inferiore al numero di posizioni e nel caso in cui tutte le posizioni visitate siano piene si sostituisce uno degli elementi prima presenti. Se hai mai sentito parlare di full o 2-way o 4-way associative cache (riferito soprattutto ai processori) si riferisce esattamente a questo.