HashMap a deux propriétés importantes : size et load factor. J'ai parcouru la documentation Java et il dit que 0.75f est le facteur de charge initial. Mais je ne peux pas trouver son utilisation réelle.
Quelqu'un peut-il décrire quels sont les différents scénarios où nous devons définir le facteur de charge et quels sont quelques valeurs idéales d'échantillon pour différents cas ?
La documentation l'explique assez bien :
Une instance de HashMap a deux paramètres qui affectent ses performances : la capacité initiale et le facteur de charge. La capacité est le nombre de compartiments dans la table de hachage, et la capacité initiale est simplement la capacité au moment où la table de hachage est créée. Le facteur de charge est une mesure de la quantité de remplissage autorisée avant que la capacité de la table de hachage ne soit automatiquement augmentée. Lorsque le nombre d'entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage est rehachée (c'est-à-dire que les structures de données internes sont reconstruites) de sorte que la table de hachage ait environ deux fois le nombre de compartiments.
En règle générale, le facteur de charge par défaut (.75) offre un bon compromis entre les coûts de temps et d'espace. Des valeurs plus élevées réduisent le surdébit d'espace mais augmentent le coût de recherche (reflété dans la plupart des opérations de la classe HashMap, y compris get et put). Le nombre attendu d'entrées dans la carte et son facteur de charge doivent être pris en compte lors du réglage de sa capacité initiale, afin de minimiser le nombre d'opérations de rehachage. Si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de rehachage ne se produira jamais.
Comme pour toutes les optimisations de performances, il est bon de ne pas chercher à optimiser prématurément (c'est-à-dire sans données précises sur les goulots d'étranglement).
Les autres réponses suggèrent de spécifier capacity = N/0.75 pour éviter le hachage multiple, mais ma première pensée était simplement de définir load factor = 1. Y aurait-il des inconvénients à cette approche? Pourquoi le facteur de charge aurait-il un impact sur les coûts des opérations get() et put()code>?
Un hashmap avec un facteur de charge=1 et un nombre d'entrées=capacité aura statistiquement un nombre important de collisions (=quand plusieurs clés produisent le même hachage). Lorsqu'une collision se produit, le temps de recherche augmente, car dans un seul seau il y aura >1 entrées correspondantes, pour lesquelles la clé doit être vérifiée individuellement pour l'égalité. Quelques maths détaillées: preshing.com/20110504/hash-collision-probabilities
Je ne vous suis pas @atimb; La propriété loadset est uniquement utilisée pour déterminer quand augmenter la taille de stockage, n'est-ce pas? -- Comment le fait d'avoir un loadset de un augmenterait la probabilité de collisions de hachage? -- L'algorithme de hachage n'a pas connaissance du nombre d'éléments dans la table de hachage ou de la fréquence à laquelle il acquiert de nouveaux "blocs" de stockage, etc. Pour tout ensemble d'objets de même taille, peu importe comment ils sont stockés, vous devriez avoir la même probabilité de valeurs de hachage répétées...
La capacité initiale par défaut du HashMap est de 16 et le facteur de charge est de 0,75f (c'est-à-dire 75% de la taille actuelle de la carte). Le facteur de charge représente le niveau auquel la capacité du HashMap doit être doublée.
Par exemple, le produit de la capacité et du facteur de charge est de 16 * 0.75 = 12. Cela signifie qu'après avoir stocké la 12ème paire clé-valeur dans le HashMap, sa capacité devient 32.
Bien que votre réponse soit claire, pouvez-vous me dire si juste après avoir stocké 12 paires clé-valeur, la capacité devient de 32 ou est-ce que lorsque la 13ème entrée est ajoutée, à ce moment-là la capacité change et ensuite l'entrée est insérée.
@userab ce sera à la 13ème entrée, vous ne chercherez peut-être plus cette réponse mais pour les autres.
En fait, d'après mes calculs, le facteur de charge "idéal" est plus proche de log 2 (~ 0.7). Bien que tout facteur de charge inférieur à cela donnera de meilleures performances. Je pense que .75 a probablement été sorti d'un chapeau.
Preuve :
Le chaînage peut être évité et la prédiction de branche exploitée en prédisant si un seau est vide ou non. Un seau est probablement vide si la probabilité qu'il soit vide dépasse .5.
Soit s la taille et n le nombre de clés ajoutées. En utilisant le théorème binomial, la probabilité qu'un seau soit vide est :
P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)Ainsi, un seau est probablement vide s'il y a moins de
log(2)/log(s/(s - 1)) clésComme s tend vers l'infini et si le nombre de clés ajoutées est tel que P(0) = .5, alors n/s approche rapidement log(2) :
lim (log(2)/log(s/(s - 1)))/s lorsque s -> l'infini = log(2) ~ 0.693...
Les nerds en mathématiques FTW! Il est probable que le .75 ait été arrondi à la fraction la plus simple la plus proche de log(2), ce qui semble moins être un nombre magique. J'aimerais voir une mise à jour de la valeur par défaut de la JDK, avec ledit commentaire au-dessus de sa mise en œuvre :D
Je veux vraiment aimer cette réponse, mais je suis un développeur JavaEE, ce qui signifie que les mathématiques n'ont jamais été mon point fort, donc je comprends très peu de ce que vous avez écrit lol
La prémisse qu'un seau ayant une probabilité de 0,5 de remplissage/vidage conduirait à des performances optimales est tout simplement injustifiée
La quantité de capacité qui doit être épuisée pour que la HashMap augmente sa capacité.
Le facteur de charge est par défaut de 0,75 de la capacité initiale (16), donc 25 % des seaux seront libres avant qu'il y ait une augmentation de la capacité, et cela entraîne la création de nombreux nouveaux seaux avec de nouveaux hashcodes pointant vers eux juste après l'augmentation du nombre de seaux.
Si vous définissez le facteur de charge à 1,0, quelque chose de très intéressant pourrait se produire.
Supposons que vous ajoutiez un objet x à votre hashmap dont le hashCode est 888 et que le seau représentant le hashcode dans votre hashmap est libre, alors l'objet x est ajouté au seau, mais à la fin du seau (parce que les seaux ne sont rien d'autre qu'une implémentation de LinkedList stockant la clé, la valeur et le suivant) cela a un impact sur les performances ! Puisque votre objet y n'est plus présent en tête du seau, si vous effectuez une recherche, le temps nécessaire ne sera pas O(1) cette fois-ci, cela dépendra du nombre d'éléments présents dans le même seau. C'est ce qu'on appelle une collision de hachage, et cela se produit même lorsque votre facteur de charge est inférieur à 1.
Vous pourriez ajouter un peu de détails sur la façon dont le hashCode est réduit à un nombre dans la plage de 1 à {count bucket}, et donc ce n'est pas en soi le nombre de seaux, mais que le résultat final de l'algorithme de hachage couvre une plage plus large. HashCode n'est pas l'algorithme de hachage complet, il est juste assez petit pour être facilement retraité. Il n'y a donc pas de concept de "seaux gratuits", mais "nombre minimum de seaux gratuits", puisque vous pourriez stocker tous vos éléments dans le même seau. Plutôt, il s'agit de l'espace clé de votre hashCode, qui est égal à capacité *(1 / facteur de charge). 40 éléments, facteur de charge de 0,25 = 160 seaux.
De la documentation :
Le facteur de charge est une mesure de la quantité de remplissage autorisée pour la table de hachage avant que sa capacité ne soit automatiquement augmentée
Cela dépend vraiment de vos besoins particuliers, il n'y a pas de "règle générale" pour spécifier un facteur de charge initial.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
0 votes
Java a de nombreuses distributions et versions différentes. Il s'agit d'une question très ancienne mais ceux qui visitent cet article peuvent utiliser des versions plus récentes de Java. Un point très important est qu'avant Java 8,
HashMapn'est pas vraiment bien écrit. C'est pourquoi les développeurs de JDK ont réécritHashMapen Java 8.0 votes
Si vous regardez le code source de
HashMapdans Oracle JDK 7, vous pouvez voir que dans la méthodeaddEntry(appelée parput(k, v)), la méthoderesizene sera appelée que lorsque(size >= threshold) && (null != table[bucketIndex])ce qui signifie que la taille doit atteindre le facteur de charge (c'est-à-dire75%) de la capacité, ET, Le seau actuel a une collision. Par conséquent, le facteur de charge n'est qu'une partie de l'histoire dans Oracle JDK 7. Dans Oracle JDK 8, la condition précédente n'existe plus.