Metodo dell'indirizzamento aperto per le Tabelle Hash

Un metodo per gestire le collisioni quando si ha a che fare con le tabelle hash è chiamato indirizzamento aperto. Al contrario delle liste di collisioni che mirano a memorizzare più oggetti aventi le stesse celle di destinazione in un'unica cella mediante delle liste, il metodo dell'indirizzamento aperto, in caso di collisione di due oggetti, scansisce la tabella mediante un indice i...
La scansione dipende dal metodo utilizzato, come vedremo in seguito. Un algoritmo generico per le Tabelle Hash implementate con l'indirizzamento aperto è il seguente:

classe TabellaHashAperta 
dati:
vettore v di dimensione dim in cui ogni cella contiene una coppia (dato,chiave)
da implementare:
funzione f che determina il tipo di indirizzamento usato
operazioni elementari:
insert(elemento e,chiave k)
for i=0 to dim-1 do
   if(v[f(k,i)].elemento=null) then
      v[f(k,i)]<-----(e,k)
      return 
errore tabella piena //se non esco mai con return


search(chiave k)----->elemento
for i=0 to m-1 do
   if(v[f(k,i)].chiave=k)then
      return v[f(k,i)].elemento
return null //non ho trovato l'elemento con la chiave k

L'indirizzamento aperto (e quindi la funzione f(k,i) ) può essere di vari tipi:

• Scansione lineare: definita da tale che i sia compresa tra 0 e minore di dim.
• Scansione quadratica: definita datale che i sia compresa tra 0 e minore di dim.
• Hashing doppio: definito da mod dim. Con h1 e h2 due funzioni hash.