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/...
Vous devez vous connecter pour publier un commentaire.
Hash-tables ne pourrait prétendre à "amorti de la constante de temps de l'insertion" si, par exemple, le redimensionnement a été en constante augmentation. Dans ce cas, le coût de redimensionnement (qui croît avec la taille de la table de hachage) serait le coût d'une insertion linéaire dans le nombre total d'éléments à insérer. Parce que le redimensionnement devient de plus en plus cher avec la taille de la table, il a de se produire "de moins en moins souvent" pour garder le coût amorti de l'insertion constante.
La plupart des implémentations de permettre à la moyenne seau occupation de croître jusqu'à une limite fixée à l'avance avant de la redimensionner (n'importe où entre 0,5 et 3, qui sont toutes des valeurs acceptables). Avec cette convention, juste après le redimensionnement de la moyenne seau occupation devient la moitié de cette limite. Redimensionnement par le doublement de garde de la moyenne seau d'occupation dans une bande de largeur *2.
Sous-remarque: en raison de regroupement statistique, vous avez à prendre une moyenne seau occupation aussi faible que 0,5 si vous voulez qu'un grand nombre de seaux pour avoir au plus un des éléments (vitesse maximale de trouver en ignorant les effets complexes de la taille de la mémoire cache), ou aussi haut que 3 si vous voulez un nombre minimum de vider les seaux (qui correspondent à l'espace perdu).
J'avais lu une discussion très intéressante sur la stratégie de croissance sur ce site... juste ne peut pas le retrouver.
Tout
2
est couramment utilisé, il a été démontré qu'il n'était pas la meilleure valeur. On a souvent cité le problème est qu'il n'a pas à faire face bien avec les allocateurs de régimes (qui, souvent, répartir la puissance de deux blocs), puisqu'il serait toujours besoin d'une réaffectation tandis qu'un petit nombre pourrait en fait être réaffectés dans le même bloc (simulation en place de la croissance) et donc d'être plus rapide.Ainsi, par exemple, la
VC++
de la Bibliothèque Standard utilise un facteur de croissance de1.5
(dans l'idéal, devrait être le nombre d'or si un premier ajustement de l'allocation de mémoire de la stratégie est en cours d'utilisation) après une longue discussion sur la liste de diffusion. Le raisonnement est expliqué ici:Bien sûr, il doit être adaptée à la stratégie d'allocation de mémoire.
realloc
de garder l'élément dans la même taille de seau... mais vraiment ce que nous voyons ici est une limitation dans lestd::allocator
design => lorsque vous demandez à N octets de la mémoire, elle ne doit pas seulement vous donner un bloc de mémoire d'au moins N octets, mais aussi de savoir combien d'octets du bloc de contenircomputePushBackCapacity
. D'abord augmente en fonction de seau tailles quand il est petit (en pratique il suffit d'un facteur de croissance de 2), puis croît de 1,5 quand il est de taille moyenne, et enfin augmente de 2 à nouveau (je suppose que pour utiliser toute la mémoire pages).That leaves a gap
, quel est l'écart-vous dire par là? Je suis en train d'utiliser les liens les gars, vous a donné, mais la plupart sont expirés.malloc
alloué 2 octets 4 octets, et vous vous demandez maintenant 8 octets, il ne peut pas combiner les 2+4 pour satisfaire la répartition, de sorte qu'il a besoin d'une nouvelle marque de 8 octets. Et la prochaine fois, comme vous le demande 16 octets, il ne peut pas les combiner 2+4+8 pour satisfaire la répartition, etc... Maintenant, de petite taille c'est peu probable, cependant, à de plus grandes tailles (MO-gamme et ci-dessus), alors il ne se passera. Les promoteurs de l'utilisation de 1.5 par conséquent, faire le cas que avec la version 1.5 de recyclage:2+4 >= 6 = 4*1.5
.Une raison pour doubler la taille qui est spécifique à hachage de conteneurs, c'est que si la capacité du bac est toujours une puissance de deux, alors au lieu d'utiliser un objectif général de modulo pour la conversion d'un hachage d'un décalage, le même résultat peut être obtenu avec le décalage de bits. Modulo est une opération lente pour les mêmes raisons que la division entière est lente. (Si la division entière est "lent" dans le contexte de tout ce qui se passe dans un programme de cours dépend mais c'est certainement plus lent que les autres de base de l'arithmétique des nombres entiers.)
Le doublement de la mémoire lors de l'expansion de tout type de collection est souvent utilisé stratégie pour prévenir la fragmentation de la mémoire et de ne pas avoir à réaffecter trop souvent. Comme vous le soulignez, il pourrait y avoir des raisons pour avoir un premier nombre d'éléments. Quand en sachant que votre application et vos données, vous pouvez également être en mesure de prédire la croissance du nombre d'éléments, et donc de choisir un autre (plus grande ou plus petite), facteur de croissance que doublé.
Le général implémentations trouve dans les bibliothèques sont exactement cela: Général implémentations. Ils doivent se concentrer sur d'être un choix raisonnable dans une variété de situations différentes. Si l'on connaît le contexte, il est presque toujours possible d'écrire un plus spécialisées et plus efficace la mise en œuvre.
Si vous ne savez pas combien de objets vous allez vous retrouver à l'aide de (disons N),
en doublant l'espace que vous allez faire le journal2N réaffectations au plus.
Je suppose que si vous choisissez un bon initiale "n", vous augmentez les chances
que 2*n + 1 va produire des nombres premiers dans la suite de réaffectations.
Le même raisonnement s'applique pour le doublement de la taille que pour les vector/liste de tableaux implémentations, voir cette réponse.