3.01 HashMap

HashMap

Le HashMap salvano i dati sottoforma di coppie chiave - valore. Le funzioni di hash accettano una chiave e ritornano un output univoco che è associato solo a quella chiave (o quasi).

Collisioni di Hash

Le collisioni si verificano quando una funzione di hash ritorna lo stesso output per due input diversi. Le collisioni si risolvono con il separate chaining, dove gli elementi vengono inseriti in una lista (quando si verifica una collisione), oppure attraverso il linear probing; in questo caso, in caso di collisione, inseriamo la chiave nella prima posizione utile successiva all'index di Hash. Quando elimino un elemento nel linear probing devo effettuare il re-hashing di tutte le chiavi rimanenti.

Clustering

Un cluster è un blocco di elementi posti uno dopo l'altro, e aggiungendo delle chiavi potremmo andare ad incrementare la grandezza di un cluster.

Resizing

Separate chaining

L'obbiettivo è mantenere N / M = const

• Raddoppio la grandezza M quando N / M >= 8
• Dimezzo la grandezza M quando N / M <= 2
  • Rieffettuo l'hashing

Linear probing

• Raddoppio M quando N / M >= 1/2
• Dimezzo M quando N / M <= 1/8
  • Rieffettuo l'hashing

Time Complexity

• Indexing: O(1)
• Ricerca: O(1)
• Inserimento O(1)