Indirizzamento aperto

Un modo alternativo per risolvere le collisioni consiste nel memorizzare gli elementi con lo stesso hash nella tabella insieme agli altri, per poi cercarli attraverso l'ispezione di T[h(k)]:

• Se la cella equivale a k la ricerca ha successo
• Se equivale a NIL la ricerca termina con insuccesso
• Se è diversa da k si trova il prossimo indice dall'ordine di ispezione, cioè il numero di ispezioni fatte

Si vuole quindi che la funzione hash rappresenti la posizione di $k$ in T dopo $i$ ispezioni fallite: $$h(k,i):U\times \{0,...,m-1\}\to \{0,...,m-1\}$$ con la condizione che per ogni $k$ la funzione assuma tutti i valori, così che ogni cella possa essere usata.

Implementazione

In queste versioni delle operazioni, per semplicità, gli elementi di T sono solamente le chiavi stesse.

• Inserimento

  insert(T, k)
    i = j = 0
    found = false
    while not found and i < m
      j = h(k, i)
      if T[j] == NIL or T[j] == DELETED
        T[j] = k
        found = true
      else
        i++
    if found
      return j
    return NIL
  

• Ricerca

  search(T, k)
    i = j = 0
    found = false
    do
      j = h(k, i)
      if T[j] == k
        found = true
      else
        i++
    while not found and i < m and T[j] != NIL
    if found
      return j
    return NIL
  

• Cancellazione

  delete(T, k)
    T[search(T, k)] = DELETED
  

  Il motivo per cui si usa DELETED invece che NIL è che quest'ultimo serve ad indicare la fine della catena di ricerca, e quindi porterebbe alla perdita dei valori sulle $i$ successive.

  Lo svantaggio di questo metodo è che il tempo di ricerca non dipende più da $\alpha =\frac{n}{m}$.

Metodi di ispezione

Come per il concatenamento, una funzione $h$ ideale rispetterebbe le proprietà dell'hashing uniforme così che, dato un $k$, ogni $h(k,i)$ è distribuito uniformemente sulle $m$ celle.

Dato che è difficile rispettarle, vengono adottate delle approssimazioni.

Ispezione lineare

$$h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$$ dove $h^{\prime }:U\to \{0,1,...,m-1\}$ è detta funzione hash ausiliaria.

Questo metodo è semplice, ma genera la stessa sequenza di ispezioni per le $k$ diverse con lo stesso $h^{\prime }(k)$.

Ispezione quadratica

$$h(k,i)=(h^{\prime }(k)+c_1\cdot i+c_2\cdot i^2)\mathrm{mod}m$$ dove $h^{\prime }$ è l'hash ausiliaria e $c_1,c_2\in \{1,...,m-1\}$ sono costanti, con buoni valori $c_1=c_2=\frac{1}{2}$ e $m=2^p$.

Anche in questo caso genera la stessa sequenza di ispezioni per $k$ diverse con $h^{\prime }(k)$ uguali.

Doppio hashing

$$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$$ dove $h_{1,2}$ sono hash ausiliarie, di cui $h_1$ marca la cella di partenza mentre $h_2$ definisce lo step delle ispezioni.

Questo metodo genera sequenze diverse di ispezione, dato che dipendono da $h_2\ne h_1$.

Per generare sequenze su tutti i valori della tabella, $h_2(k)$ dev'essere relativamente primo con $m$:

• Si usa $m=2^p$ pari e si definisce $h_2(k)$ come sempre dispari, e.g. $h_2(k)=2\cdot h^{\prime }(k)+1$
• Si usa $m$ primo e $h_2(k)$ minore di $m$, e.g. $h_1(k)=k\mathrm{mod}m$, $h_2(k)=1+(k\mathrm{mod}{m}^{\prime })$ per $m^{\prime }<m$

Tempo di ricerca

Al contrario del concatenamento, l'indice di prestazione $\alpha =\frac{n}{m}\in [0,1]$ perchè $n=|K|\le m$.

Se $\alpha <1$ esiste almeno una cella vuota su cui la ricerca senza successo si può fermare, quindi:

• $P(i=0)=1$ perchè la prima ispezione è sempre effettuata
• $P(i=1)=\frac{n}{m}$ ovvero la probabilità che la cella su $i=0$ sia occupata
• $P(i=2)=\frac{n}{m}\cdot \frac{n-1}{m-1}$ perchè anche la cella su $i=1$ sia occupata
• $P(i=3)=\frac{n}{m}\cdot \frac{n-1}{m-1}\cdot \frac{n-2}{m-2}$ perchè anche la cella su $i=2$ sia occupata

Di conseguenza il valore atteso di $i$, ovvero il numero medio di ispezioni, è al massimo¹: $$\begin{array}{rl}E(i)& =0\cdot P(i=0)+1\cdot P(i=1)+...\\ & \le \sum _{k=0}^{\infty }{\alpha }^k=\frac{1}{1-\alpha }\end{array}$$ e lo stesso vale per l'inserimento, dato che cerca una cella vuota.

Nella ricerca con successo invece, il numero medio di ispezioni è $\frac{1}{\alpha }\log \frac{1}{1-\alpha }$.