Hash - 12/06/2014

Posted by On Filed under Algoritmi e strutture dati

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Svolgimento

Caso A:

  1. 23 mod 17 = 6 → 6[0] = 23
  2. 40 mod 17 = 6 → 6[1] = 40
  3. 15 mod 17 = 15 → 15[0] = 15
  4. 58 mod 17 = 7 → 7[0] = 58
  5. 85 mod 17 = 0 → 0[0] = 85

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23, 40; 7: 58; 8:; 9:; 10:; 11:; 12:; 13:; 14:; 15: 15; 16:;

Caso B

  1. i = 0, k = 23: (23 mod 17 + 0 * 2*23 mod 5) mod 17 = 6
  2. i = 1, k = 40: (40 mod 17 + 1 * 2*40 mod 5) mod 17 = 6: c'è una collisione, quindi si scorre fino al numero 7
  3. i = 2, k = 15: (15 mod 17 + 2 * 2*15 mod 5) mod 17 = 15
  4. i = 3, k = 58: (58 mod 17 + 3 * 2*58 mod 5) mod 17 = 10
  5. i = 4, k = 85: (85 mod 17 + 4 * 2*85 mod 5) mod 17 = 0

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23; 7: 40; 8:; 9:; 10: 58; 11:; 12:; 13:; 14:; 15: 15; 16:;