Pourquoi la table de hachage des expansions fait généralement par le doublement de la taille?

J'ai fait un peu de recherche sur les tables de hachage, et je continue à courir à travers la règle d'or que quand il y a un certain nombre d'entrées (soit max ou par l'intermédiaire d'un facteur de charge de 75%) de la table de hachage doit être élargi.

Presque toujours, la recommandation est de doubler (ou double plus 1, c'est à dire, 2n+1) la taille de la table de hachage. Cependant, je n'ai pas été en mesure de trouver une bonne raison pour cela.

Pourquoi le double de la taille, plutôt que, disons, de l'augmenter de 25%, ou d'augmenter la taille de le prochain nombre premier, ou à côté de k nombres premiers (par exemple, trois)?

Je sais déjà que c'est souvent une bonne idée de choisir une première table de hachage de taille qui est un nombre premier, au moins si votre fonction de hachage utilise le module comme universel de hachage. Et je sais que c'est pourquoi il est généralement recommandé de le faire 2n+1 au lieu de 2n (par exemple, http://www.concentric.net/~Ttwang/tech/hashsize.htm)

Cependant, comme je l'ai dit, je n'ai pas vu de réelle explication de doubler ou de doubler les-plus-un est en fait un bon choix plutôt que d'une autre méthode de choisir une taille pour la nouvelle table de hachage.

(Et oui j'ai lu l'article de Wikipedia sur les tables de hachage 🙂 http://en.wikipedia.org/wiki/Hash_table

  • Je crois que la question fondamentale derrière celui-ci peut être formulée d'une façon plus générique et n'est pas un problème spécifique pour les tables de hachage seulement. Comme: "pourquoi faire de nombreuses collections redimensionner eux-mêmes par le doublement de la taille de leur tableau interne?" Pour une bonne explication, voir Pete Kirkham de réponse: stackoverflow.com/questions/1424826/why-is-vector-array-doubled/...
InformationsquelleAutor Chirael | 2010-03-03