sont entrées supprimées comptés dans le facteur de charge d'une table de hachage en utilisant l'adressage ouvert

Question

Lors du calcul du facteur de charge d'une table de hachage avec une implémentation de tableau ouvert adressage J'utilise:

numberOfKeysInArray/sizeOfArray

mais il me est apparu que, puisque les entrées supprimées doivent être marqués comme tels (pour les distinguer des espaces vides), il peut être judicieux de les inclure dans le nombre de touches.

Ma pensée est que dans la mesure où l'estimation du nombre moyen de sondes pour trouver une entrée, supprimé les entrées doivent compter pour le facteur de charge, mais pour autant que l'insertion d'une nouvelle clé qu'ils ne devraient pas.

Quel est le calcul correct: y compris les clés supprimées ou pas

Answer 1

n, par définition, le facteur de charge est le rapport du nombre d'éléments à la taille de l'ensemble du godet. Voir par exemple Wikipedia ou cette conférence .

Il y aurait aussi un problème pratique avec le comptage des entrées delted du facteur de charge. La plupart des implémentations ont un facteur de charge maximale. Si Surpasse réelle maximale autorisée, la taille de la matrice de support est augmentée. Si les entrées supprimées en compte dans le facteur de charge plus élevée, cela pourrait provoquer une augmentation inutile de la taille du tableau pour un presque vide mais élevé sur la table des matières de débris.