Combien de seaux de hachage

Question

Si je remarque qu'une table de hachage (ou toute autre structure de données construite sur une table de hachage) est en train de se remplir, à quel moment devez-vous créer une nouvelle table avec plusieurs compartiments. Et étant donné n éléments dans le tableau jusqu’à présent, comment calculez-vous le nombre de compartiments à utiliser dans le nouveau?

Alors disons que j'ai 100 seaux. Devrais-je le réorganiser quand il contient 50 articles? 500? 5000? Ou devrais-je chercher le seau le plus complet et la clé à ce sujet? Puis, quand j'atteins ce point, quelle est la taille de la nouvelle table de hachage?

Dans le même ordre d'idées, si vous connaissez à l'avance le nombre d'éléments à inclure, existe-t-il un moyen de calculer le nombre de compartiments pour obtenir une bonne performance moyenne?

Je sais que la vraie réponse dépend de nombreux autres facteurs, tels que l'importance de la vitesse par rapport à la taille dans un exemple spécifique, mais je recherche des lignes de guildes générales.

Je sais aussi que je ne devrais pas optimiser ce genre de chose à moins qu'un bon profilage indique qu'il s'agit d'un goulot d'étranglement. Je pense juste à un projet qui utiliserait beaucoup de tables de hachage et je me suis demandé comment aborder cela.

Answer 1

Une bonne règle du pouce (pas toujours idéale, bon, juste une règle du pouce) est de re-hacher si la table de hachage est remplie à 80%. Cela signifie que si vous avez 100 seaux et 80 articles à l'intérieur, peu importe le nombre de collisions que vous avez subies auparavant, il est temps d'augmenter votre capacité.

Combien devriez-vous l'augmenter? Eh bien, il n'y a pas non plus de valeur parfaite. La solution la plus simple consiste à doubler la capacité à chaque augmentation. Donc, cela passe à 200, 400, 800, etc. Si vous pensez que c'est trop (après tout, la mémoire passagère passera de 8 Mo à 16 Mo alors que la table de hachage devient très volumineuse et vous risquez de ne jamais remplir les 16 Mo), choisissez un facteur de croissance plus petit. Au moins 1/3 est recommandé (il passe de 100 à 133) Je le laisserais peut-être le laisser croître de 50% à chaque fois comme compromis.

Notez que tout cela dépend également de la manière dont les collisions sont gérées. Un moyen simple de les gérer (mon favori personnel) consiste à stocker les éléments dans une liste chaînée en cas de collision. Si 3 éléments sont placés sur la même clé, il ne reste plus que 3 comparaisons pour le trouver. Étant donné que les listes chaînées sont très inefficaces pour la recherche, vous pouvez augmenter la capacité plus tôt, par exemple. si 60% de la capacité est utilisée pour garder le hashtable rapide. OTOH, vous pouvez faire quelque chose de plus sophistiqué et garder des statistiques sur le nombre de collisions. Tant que vous n’avez pratiquement pas de collision (si vous avez une très bonne fonction de hachage), il n’est pas nécessaire de re-hacher, même si 99% de sa capacité est utilisée. De même, si vous gérez les collisions de manière sophistiquée (chaque nœud est par exemple une table triée et que vous pouvez effectuer une recherche binaire à l'intérieur de celles-ci), votre recherche pourrait quand même être assez rapide si la table est chargée à 200% (vous avez donc deux fois plus d'éléments comme capacité). Dans ce cas, vous pouvez conserver des statistiques sur la taille de la table triée la plus grande et, lorsqu'elle devient plus grande que, par exemple, 8 entrées, vous pensez que cela devient trop lent, puis vous recommencez.

Le re-hachage est très lent, il devrait donc être évité aussi souvent que possible. Ainsi, si vous avez besoin de ré-hachage, ne vous contentez pas d'augmenter la capacité, sinon vous devrez ré-hacher de nouveau très bientôt lorsque vous ajouterez plus d'éléments. Ainsi, lorsque vous devez modifier le hachage, augmenter considérablement la capacité par rapport au nombre d'éléments actuellement dans le tableau, tout le reste correspond à une capacité insuffisante.

Answer 2

Généralement, vous recherchez le facteur de charge (de manière informelle, vous l'avez déjà dit) qui est formellement défini comme & # 945; & nbsp; = & nbsp; n . & nbsp; / & nbsp; N , c’est-à-dire le rapport entre les seaux utilisés et les seaux totaux. Pour qu'une table de hachage fonctionne correctement (ou au moins pour raisonner sur ses performances en termes mathématiques), elle doit être & # 945; & Nbsp; & Lt; & Nbsp; 1.

Tout le reste dépend vraiment des tests empiriques: si vous constatez que votre table de hachage ne fonctionne pas correctement à partir de & # 945; & nbsp; > & nbsp; 0,5, alors veillez à rester en dessous de cette valeur. Cette valeur dépend également de votre technique de résolution de collision. Le hachage avec chaînage peut nécessiter d'autres facteurs de charge que le hachage avec un adressage ouvert. Un autre facteur est la localisation en cache. Si votre table devient trop grande, elle ne rentrera pas dans la mémoire principale. Étant donné que votre accès au tableau est aléatoire, le chargement à partir du cache peut devenir un goulot d'étranglement.

Answer 3

Il existe généralement deux types de tables de hachage: ouvert et fermé.

Dans une table de hachage ouverte, vous trouvez le bon compartiment en fonction du hachage, puis vous créez une liste d'éléments suspendus à ce dernier.

Dans une table de hachage fermée, vous trouvez le compartiment initial à l'aide de la valeur de hachage. S'il est occupé, vous recherchez la valeur suivante. Dans le cas simpliste, vous pouvez le faire en recherchant le prochain seau gratuit, ou vous pouvez créer une seconde valeur de hachage à partir de votre élément et procéder étape par étape (vous devez toutefois vous assurer que la taille des tables de hachage est optimale, de sorte que vous visiterez tous les objets). les seaux).

Une hashtable ouverte n'est généralement pas redimensionnée. Vous définissez la taille initiale comme étant ce que vous jugez raisonnable pour le problème. Comme d'autres l'ont souligné, vous pouvez redimensionner une table de hachage ouverte, mais il est désormais très difficile de raisonner sur les performances de cette structure de données. Si vous redimensionnez lorsque la longueur d'un compartiment est égale à L, vous risquez de redimensionner uniquement les éléments L de l'ensemble de la table de hachage, ce qui est très inefficace.

Une table de hachage fermée est redimensionnée lorsque le facteur de charge (nombre d'éléments dans la table de hachage / nombre de compartiments) atteint une valeur prédéfinie. J'ai tendance à utiliser 80%, mais il est peu probable que la valeur exacte soit trop critique.

L'avantage d'une table de hachage fermée est que le coût amorti de l'insertion d'un élément est toujours égal à O (1) (en supposant une bonne fonction de hachage). L'insertion d'un élément particulier peut être O (N) en raison du coût du redimensionnement, mais cela se fait très rarement.

Answer 4

Dépend du type de table de hachage que vous construisez. Si vous utilisez une table de hachage basée sur un tableau fixe (par opposition aux listes chaînées pour les compartiments), vous devez redimensionner le tableau lorsque la table est pleine ou lorsque vous avez atteint un nombre maximal de sondes (selon que vous vous souciez davantage de la vitesse ou de la vitesse.) Mémoire). Si vous utilisez des listes chaînées, la mémoire n’est plus aussi une préoccupation depuis et n’a pas à rechercher les espaces vides, le redimensionnement n’est donc pas une grosse affaire.

La clé avec les tables de hachage est l'algorithme de hachage, pas le nombre de compartiments. Idéalement, vous voulez toujours au plus un élément dans chaque compartiment. Vous devez donc idéalement redimensionner lorsque le nombre d'éléments dans la table de hachage = le nombre de compartiments. Si vos données ne sont pas distribuées de manière uniforme, il vaut mieux utiliser un meilleur algorithme de hachage qu'une meilleure stratégie de redimensionnement.

Answer 5

Si vous utilisez le hachage linéaire, la table se charge automatiquement du redimensionnement en maintenant un facteur de charge constant.