Choisir une taille de table appropriée pour un hachage

Question

Si j'ai un jeu de clés de 1 000, quelle est la taille appropriée pour ma table de hachage et comment cela est-il déterminé?

Answer 1

Cela dépend du facteur de charge (le "pourcentage de remplissage" où la table augmentera sa taille et redistribuera ses éléments). Si vous savez que vous avez exactement 1000 entrées et que ce nombre ne changera jamais, vous pouvez simplement définir le facteur de charge sur 1,0 et la taille initiale sur 1 000 pour une efficacité maximale. Si vous n’êtes pas sûr de la taille exacte, vous pouvez laisser le facteur de charge à 0,75 par défaut et définir votre taille initiale à 1334 (taille attendue / LF) pour une réelle performance à un coût raisonnable. de mémoire supplémentaire.

Vous pouvez utiliser le constructeur suivant pour définir le facteur de charge:

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

Vous devez également prendre en compte la fonction de hachage.

Une règle empirique suggère de doubler la taille de la table, afin de permettre une expansion et d’espérer que le nombre de collisions reste faible.

Une autre règle empirique consiste à supposer que vous effectuez une sorte de hachage lié au modulo, puis arrondissez la taille de votre table au nombre premier le plus grand et utilisez ce nombre premier comme valeur modulo.

Quel genre de choses hachez-vous? Plus de détails devraient générer de meilleurs conseils.

Answer 3

Il existe des informations sur ces facteurs dans la documentation de Hashtable

Answer 4

Laissez-le grandir. Avec cette taille, le traitement automatique est correct. Autre que cela, 2 x taille + 1 est une formule simple. Les nombres premiers sont également intéressants, mais dès que votre ensemble de données atteint une certaine taille, l’implémentation du hachage peut décider de modifier l’agrandissement du tableau.

Vos clés déterminent l'efficacité et sont suffisamment distinctes, espérons-le.

Conclusion: posez la question de taille lorsque vous rencontrez des problèmes tels que la taille ou des performances lentes, autres que ceux-ci: Ne vous inquiétez pas!

Answer 5

Deux fois c'est bien.

Vous n'avez pas un gros clavier. Ne vous embêtez pas au sujet de discussions difficiles sur votre implémentation de HashTable et optez pour 2000.

Answer 6

Je voudrais réitérer ce que https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany"> > dit ci-dessus. 1000 ne me semble pas être un très gros hash. J'utilise beaucoup de tables de hachage de cette taille en java sans trop me préoccuper des problèmes de performances. Et je ne parle presque jamais de la taille ou du facteur de charge.

Si vous avez exécuté un profileur sur votre code et déterminé que la hashtable est votre problème, commencez à peaufiner. Sinon, je ne supposerais pas que vous ayez un problème tant que vous n’êtes pas sûr.

Après tout, dans la plupart des codes, le problème de performances n’est pas celui que vous pensez. J'essaie de ne pas anticiper.