Hash Table: Devrais-je augmenter le nombre d'éléments sur les collisions?

Question

En ce moment, mes tables de hachage compter le nombre de chaque élément inséré dans la table de hachage. J'utilise ce nombre, la taille totale de la table de hachage, pour calculer le facteur de charge et lorsqu'il atteint comme 70%, je remâcher.

Je pensais que je devrais peut-être seulement compter les éléments insérés avec remplissages un emplacement vide au lieu de tous. Parce que la méthode de collision que je utilise est séparé Enchaînement. La charge de facteur ne cesse d'augmenter, mais s'il peut y avoir quelques collisions laissant beaucoup de créneaux vides sur la table de hachage.

Vous pensez probablement que si j'ai que beaucoup de collisions, peut-être que je ne suis pas en utilisant la meilleure méthode de hachage. Mais ce n'est pas le point, j'utilise un des algorithmes de hachage savoir là, je l'ai testé trois d'entre eux sur mes données d'échantillon et sélectionné celui qui a produit moins de collisions.

Ma question reste. Dois-je continuer à compter chaque élément inséré, ou seulement ceux qui remplissent un emplacement vide dans la table de hachage?

Answer 1

Rehashing vise à réduire la probabilité de collisions, de manière systématique sans tenir compte des collisions de décider quand resucée semble autodestructrice.

Le meilleur est peut-être si vous avez gardé à chaque entrée de la valeur de hachage originale complète (une collision est bien sûr au lieu déterminé par le hachage modulo votre taille actuelle) et ne comptait que les collisions qui sont dues à l'opération modulo - reconnaissant implicitement que si une collision est due à des valeurs de hachage complet identiques pour les articles différents, il y a ressasser ne peut rien faire pour aider (à moins que par « ressasser » vous impliquez également passer à une fonction de hachage différente, mais il ne ressemble pas à ce que ce que vous voulez dire ici; -.)

Garder les valeurs complètes de hachage signifie aussi ressasser moins cher puisque vous n'avez pas besoin d'exécuter la fonction de hachage à nouveau (quelle est la pertinence qui dépend de la façon coûteuse de votre fonction de hachage est de calculer, bien sûr).