sono voci eliminate contati nel fattore di carico di una tabella di hash che utilizzano indirizzamento aperto

Question

Quando si calcola il fattore di carico di una tabella hash con un'implementazione open array-indirizzamento sto usando:

numberOfKeysInArray/sizeOfArray

tuttavia pensato che poiché voci eliminate devono essere contrassegnati come tali (per distinguerli da spazi vuoti), potrebbe avere senso includerli nel numero di tasti.

Il mio pensiero è che per quanto riguarda la stima del numero medio di sonde per trovare una voce, cancellato le voci dovrebbe contare verso il fattore di carico, ma per quanto riguarda l'inserimento di una nuova chiave non dovrebbero.

Qual è il calcolo corretto:? Compresi chiavi eliminate o no

Answer 1

n, per definizione, fattore di carico è il rapporto del numero di elementi della dimensione dell'array secchio. Vedi per esempio Wikipedia o questa conferenza .

Ci sarebbe anche un problema pratico con il conteggio voci delted nel fattore di carico. La maggior parte delle implementazioni hanno un fattore di carico massimo. Se sorpassi reali il massimo consentito, dimensione della matrice di supporto viene aumentata. Se entrate cancellate conteggiati fattore di carico superiore, ciò potrebbe causare aumento dimensione dell'array inutile per quasi vuoto ma alto sulla tabella contenuti detriti.