9
Si j'ai un jeu de clés de 1000, quelle est la taille appropriée pour ma table de hachage, et comment cela est-il déterminé?Choix d'une taille de table appropriée pour un hachage
A
Répondre
9
Cela dépend du facteur de charge (le point "pourcentage plein" où la table va augmenter sa taille et redistribuer 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 à 1.0 et la taille initiale à 1000 pour une efficacité maximale. Si vous n'étiez pas sûr de la taille exacte, vous pouvez laisser le facteur de charge à sa valeur par défaut de 0,75 et régler votre taille initiale à 1334 (taille attendue/LF) pour vraiment bonne performance, au prix de plus de mémoire.
Vous pouvez utiliser le constructeur suivant pour définir le facteur de charge:
Hashtable(int initialCapacity, float loadFactor)
1
3
Vous devez prendre en compte la fonction de hachage ainsi. Une règle empirique suggère de faire en sorte que la taille de la table soit à peu près double, de sorte qu'il y ait de la place pour l'expansion et, espérons-le, de limiter le nombre de collisions. 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 avez-vous? Plus de détails devraient générer de meilleurs conseils.
0
deux fois est bon.
Vous n'avez pas un grand jeu de clés. Ne vous embêtez pas à propos de discussions difficiles au sujet de votre implémentation de HashTable, et optez pour 2000.
+0
2000 ne fait pas une bonne taille, car il n'est pas premier. 2001 serait bien, ce n'est pas premier, mais au moins pas même. Va distribuer les clés dans la table beaucoup mieux. Une bonne hashtable prendra soin d'une bonne fonction de hachage mais la plupart du temps, la taille est utilisée. – ReneS
+0
Ceci est une question intéressante. Votre déclaration est correcte si vous utilisez une clé de hachage de type: H (s) = s [0] + b * s [1] + b^2s [2] + ... [N] Je pense que la norme de l'industrie d'aujourd'hui est utiliser 2^k comme taille et de meilleures fonctions de hachage comme celle de Jenkins. La dernière fois que j'ai vérifié le std travaillait avec le premier cependant. – fulmicoton
+0
Les nombres premiers et impairs sont plus froids;) – ReneS
1
Laissez-le grandir. Avec cette taille, la manipulation automatique est bien. Autre que cela, 2 x taille + 1 est une formule simple. Les nombres premiers sont également bons, mais dès que votre ensemble de données atteint une certaine taille, l'implémentation du hachage peut décider de ressasser et d'agrandir la table. Vos clés sont le moteur de l'efficacité et sont, espérons-le, assez distinctes.
Bottom line: Posez la question de taille lorsque vous avez des problèmes tels que la taille ou la lenteur des performances, à part ça: Ne vous inquiétez pas!
+0
S'inquiète si la performance * dans cette zone * devient un problème. Si vous essayez de le gérer à l'avance, vous avez plus de chances d'insérer un bogue ou simplement d'avoir du code inutilement complexe qui peut causer un problème de maintenance. –
+0
Je suis d'accord. Ayez le problème en premier et cherchez une solution après. – ReneS
0
Je voudrais réitérer ce que https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany a dit ci-dessus. 1000 ne me semble pas un très gros hasch. J'ai utilisé beaucoup de hashtables à propos de cette taille en Java sans trop voir les problèmes de performance. Et je ne suis presque jamais déçue par la taille ou le facteur de charge.
Si vous avez exécuté un profileur sur votre code et déterminé que la hashtable est votre problème, alors commencez à peaufiner. Sinon, je ne supposerais pas que vous avez un problème jusqu'à ce que vous soyez sûr.
Après tout, dans la plupart des codes, le problème de performances n'est pas là où vous le pensez. J'essaie de ne pas anticiper.
Questions connexes
- 1. Choix d'un multiplicateur pour une fonction de hachage (chaîne)
- 2. Silverlight table de taille dynamique
- 3. WinForms .NET 2.0: Comment peindre l'icône de taille appropriée?
- 4. L'utilisation d'une table de hachage pour stocker uniquement les clés?
- 5. Raison du tri d'une table de hachage
- 6. Impossible d'obtenir la taille appropriée d'une ArrayList dans JSP
- 7. Java Swing Table taille
- 8. MySQL Design de table pour un questionnaire
- 9. Choix de la colonne de l'autre table/objet
- 10. Taille de table maximale pour une base de données MySQL
- 11. Taille de table de recherche réduction
- 12. Quelle est la taille maximale de maxReceivedMessageSize pour un NetNamedPipeBinding?
- 13. Choix de la taille du tampon pour les transferts FTP et HTTP
- 14. Un dictionnaire Python est-il un exemple de table de hachage?
- 15. meilleure façon d'offrir une table de hachage statique C#
- 16. Quelle est l'utilisation appropriée pour le contrôle MultiView d'ASP.NET?
- 17. WPF, liaison bidirectionnelle à une table de hachage
- 18. Remplir JTable à partir d'une table de hachage en Java
- 19. CSS ajuster la taille de la table
- 20. Choix de l'emplacement d'enregistrement Sharepoint pour un formulaire InfoPath
- 21. Comment ajoutez-vous cette table de hachage dans Clojure?
- 22. Conception appropriée
- 23. Plusieurs choix Calendrier pour jsf
- 24. Comment allez-vous tester une unité contenant un type de données de table de hachage?
- 25. Serait-ce une situation appropriée pour un curseur?
- 26. Listes liées ou tables de hachage?
- 27. jQuery licence choix
- 28. Comment choisir entre une table de hachage et un trie (arborescence de préfixes)?
- 29. self.send Appel itérativement sur un argument de hachage pour initialize()
- 30. La structure de données la plus appropriée pour une liste ordonnée dans un SGBDR?
En supposant que la fonction de hachage se comporte bien sur l'ensemble des clés attendues. Une fonction de hachage brassée à la maison peut ne pas bien se comporter dans une table de taille minimale. Pour une fonction brassée à la maison, il faudrait faire des expériences. –
Si la fonction de hachage n'est pas correcte, les éléments en collision seront stockés dans le même compartiment (dans une LinkedList). La taille minimale de la table n'aura aucun effet sur les performances. –