Est-il judicieux de redimensionner une baisse de table de hachage? Et quand?

Question

Ma mise en œuvre de table de hachage a une fonction pour redimensionner la table lorsque le cours de charge environ 70%. Ma table de hachage est mis en œuvre avec l'enchaînement séparé pour les collisions.

Est-il logique que je redimensionner la table de hachage vers le bas à tout moment ou devrais-je laisser tout comme il est? Dans le cas contraire, si j'augmente la taille (par presque le double, en fait je suis ceci: http://planetmath.org /encyclopedia/GoodHashTablePrimes.html ) lorsque la charge est de 70%, dois-je changer la taille vers le bas lorsque la charge obtient 30% ou moins?

Answer 1

Êtes-vous en train d'écrire la table de hachage pour un usage général, ou est-il un objectif spécifique pour elle? Je suggère de ne pas redimensionner plus petit pour une mise en œuvre générale. Cela permet de garder votre simple table et l'empêcher de raclée de mémoire dans des conditions où la table est remplie et vidée souvent. Si vous finissez par en cours d'exécution dans un état où les besoins de table de hachage à réduire la taille, l'étendre à ce moment.

Answer 2

tables de hachage ne doivent pas avoir des longueurs de nombres premiers si vous avez une fonction de hachage de bonne qualité (voir ici ). Vous pouvez en faire les pouvoirs de deux, ce qui accélère énormément les calculs de l'indice.

Pourquoi est-il pertinent à la question? Parce que quand vous réduisez une puissance de deux enfants Hashtable, vous pouvez laisser toutes les entrées dans la partie inférieure où ils sont et ajouter simplement la liste liée à i fente (de la moitié supérieure) sur la liste chaînée dans i - n/2 slot.

Answer 3

Si la mémoire est pas cher, le laisser seul. Si la mémoire est coûteuse, redimensionner avec hystérèse comme vous l'avez suggéré. Lorsque vous avez terminé, le profil le résultat pour vous assurer qu'il fonctionne bien et n'ont pas fait quelque chose de stupide.

Answer 4

Première idée: La seule raison pour la croissance d'une Hashtable est parce que la performance Hashtable diminue s'il y a trop de collisions. De plus en plus la table lorsque sa charge est supérieure à 70% est une bonne règle du pouce pour empêcher que cela se produise, mais son juste une règle du pouce. Beaucoup mieux est de garder une trace du nombre de collisions et que croître la Hashtable si elles dépassent une certaine limite ou une fois un certain rapport de collision est frappé. Après tout, pourquoi voudriez-vous développer une table de hachage qui est chargé de 90%, n'a pas encore une seule collision? Il aurait aucun avantage.

Deuxième idée: La seule raison de réduire une table de hachage est d'économiser de la mémoire, mais en réduire la taille pourrait augmenter le nombre de collisions et de diminuer ainsi les performances de recherche. Ceci est une vitesse classique vs le commerce de mémoire hors et pourquoi devriez-vous résoudre vous-même? Laissez à quiconque utilise votre code. Il suffit de ne jamais réduire votre propre mais offrir une méthode de psy. Si une faible utilisation de la mémoire est une exigence, quiconque utilise votre code peut appeler rétrécir régulièrement. Si la performance maximale si une exigence, celui qui utilise votre code ne devrait jamais appeler rétrécir. Tout le monde peut utiliser une sorte d'heuristique pour décider si et quand appeler psy.

Troisième idée: Lorsque augmente ou diminue, toujours croître / rétrécir de manière à ce que, après l'opération un certain facteur de charge est garantie. Par exemple. quand de plus en plus, toujours grandir de sorte que par la suite le facteur de charge est de 50% et lors de la réduction, réduire toujours manière telle que par la suite le facteur de charge est de 70%. Bien sûr, cela ne dit rien sur le nombre de collisions, de sorte que l'ajout d'un élément immédiatement après la croissance / rétrécissement peut entraîner la Hashtable de croître à nouveau, mais qui est inévitable que simulant l'effet d'une croissance / psy est généralement trop cher. réduire aussi sera souvent appelé une fois qu'aucune autre modification ne rabotés, donc il faut plutôt sauver la mémoire que d'éviter d'avoir à nouveau à croître dans l'avenir.

idée dernière: Pour chaque décision que vous faites, vous ferez le Hashtable mieux pour certains cas d'utilisation et pire pour d'autres. Si vous savez comment votre Hashtable va être utilisé, ce ne sera pas un problème. Pourtant, si vous ne le faites pas, et généralement vous ne pas, pourquoi prendre ces décisions vous-même? Il suffit de les déléguer. Permettre à l'utilisateur de votre code pour personnaliser tous les petits détails, par exemple combien de croître ou diminuer, que ce soit en permettant à tous ces facteurs à fixer lorsque votre Hashtable est en cours de création ou en permettant à votre Hashtable d'avoir des fonctions de délégué (fonctions de rappel que vous pouvez toujours demander en cas de doute ce qu'il faut faire). De cette façon, chaque utilisateur de votre code peut personnaliser votre code, même lors de l'exécution pour tout scénario d'utilisation qu'ils en ont besoin.