sont supprimés entrées comptées 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 je me sers: me

numberOfKeysInArray/sizeOfArray 

mais il est apparu que puisque les entrées supprimées doivent être marquées comme telles (pour les distinguer des espaces vides), il peut être judicieux de les inclure dans le nombre de clés. Je pense qu'en ce qui concerne l'estimation du nombre moyen de sondes pour trouver une entrée, les entrées supprimées devraient être prises en compte dans le facteur de charge, mais pas dans le cas d'une nouvelle clé.

Quel est le bon calcul: y compris les clés supprimées ou non?

Answer 1

Non, par définition, le facteur de charge est le rapport entre le nombre d'éléments et la taille du groupe de godets. Voir par exemple Wikipedia ou this lecture.

Il y aurait aussi un problème pratique avec le comptage des entrées supprimées dans le facteur de charge. La plupart des implémentations ont un facteur de charge maximum. Si la valeur réelle dépasse le maximum autorisé, la taille de la matrice de sauvegarde est augmentée. Si les entrées supprimées comptaient pour un facteur de charge plus élevé, cela pourrait entraîner une augmentation inutile de la taille du tableau pour un tableau de contenu de débris presque vide mais élevé.