[Teoria] Hash Tables e Open Addressing

[kwb]

Ciao a tutti, sto studiando le tabelle di hash e sono arrivato alla parte delle collisioni.
Vengono trattate le due risoluzioni più comuni: il chaining e l'open addressing

In quest'ultimo non mi è chiara una cosa, e vorrei vedere se ho ben capito come funziona il meccanismo:
Inserito un dato, viene calcolata una chiave di hash, la quale sarà l'indice del mio vettore dove memorizzerò la parola.
Qualora questa cella sia già occupata, provo a guardare se la successiva ( hash key +1 ) è occupata, se non lo è, inserisco li la mia parola.
Bene
Se funziona veramente così, quando poi io devo andare a prendere una parola dalla hash table, devo calcolarmi la mia hash key ( e questo si fa easy ) e poi però se c'è una collisione, come faccio a sapere se la mia parola è finita 1, 2 o 5 slot più avanti della sua reale hash key?
La soluzione più intelligente che mi viene in mente è quella dove, una volta arrivato alla cella, comparo il dato in input con quello che ho e se sono diversi eseguo la comparazione con la cella successiva fino a trovare il giusto dato...
Ok, ma se è così, non è più facile usare un chaining? Dove, la comparazione la devo fare obbligatoriamente se c'è più di una parola in quella cella?

[asrm]

Non so precisamente, però mi verrebbe da dire che se hai un numero prefissato di valori da inserire
in una mappa il chaining comporta uno spreco di spazio, mentre effettivamente l'open addressing
risulta meno efficiente in caso di ricerca. Cmq sì, con l'open addressing se cerchi un determinato
valore associato a una key in una cella e non lo trovi, nel caso in cui l'array è pieno devi farti la scansione di tutto
l'array fino a che non trovi il valore con la key che vuoi partendo dall'indice hash.