Quelle est l'importance du facteur de charge dans HashMap?

HashMapa deux propriétés importantes: sizeet load factor. J'ai parcouru la documentation Java et il 0.75fest dit que c'est le facteur de charge initial. Mais je ne trouve pas son utilisation réelle.

Quelqu'un peut-il décrire quels sont les différents scénarios dans lesquels nous devons définir le facteur de charge et quelles sont quelques exemples de valeurs idéales 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 capacité maximale de la table de hachage à obtenir avant que sa capacité 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 ressassée (c'est-à-dire que les structures de données internes sont reconstruites) de sorte que la table de hachage a environ le double du nombre de compartiments.

En règle générale, le facteur de charge par défaut (0,75) offre un bon compromis entre le temps et les coûts d'espace. Des valeurs plus élevées réduisent la surcharge 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 prévu d'entrées dans la carte et son facteur de charge doivent être pris en compte lors de la définition de sa capacité initiale, afin de minimiser le nombre d'opérations de reprise. Si la capacité initiale est supérieure au nombre maximal d'entrées divisé par le facteur de charge, aucune opération de reprise ne se produira jamais.

Comme pour toutes les optimisations de performances, il est préférable d'éviter d'optimiser les choses prématurément (c'est-à-dire sans données précises sur l'emplacement des goulots d'étranglement).

La capacité initiale par défaut des HashMapprises est de 16 et le facteur de charge est de 0,75f (soit 75% de la taille actuelle de la carte). Le facteur de charge représente à quel niveau la HashMapcapacité doit être doublée.

Par exemple, le produit de la capacité et du facteur de charge comme 16 * 0.75 = 12. Cela signifie qu'après avoir enregistré la 12e paire clé-valeur dans le HashMap, sa capacité devient 32.

En fait, d'après mes calculs, le facteur de charge "parfait" est plus proche de log 2 (~ 0,7). Bien que tout facteur de charge inférieur à celui-ci produira de meilleures performances. Je pense que .75 a probablement été retiré d'un chapeau.

Preuve:

Le chaînage peut être évité et la prédiction de branche exploitée en prédisant si un compartiment est vide ou non. Un seau est probablement vide si la probabilité qu'il soit vide dépasse 0,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)) keys

Lorsque s atteint l'infini et si le nombre de clés ajoutées est tel que P (0) = 0,5, alors n / s approche rapidement log (2):

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...

Qu'est-ce que le facteur de charge?

La quantité de capacité qui doit être épuisée pour que le HashMap augmente sa capacité?

Pourquoi le facteur de charge?

Le facteur de charge est par défaut de 0,75 de la capacité initiale (16), donc 25% des compartiments seront libres avant une augmentation de la capacité, ce qui fait que de nombreux nouveaux compartiments avec de nouveaux codes de hachage pointant vers eux existent juste après l'augmentation de la nombre de seaux.

Maintenant, pourquoi devriez-vous conserver de nombreux compartiments gratuits et quel est l'impact de conserver des compartiments gratuits sur les performances?

Si vous définissez le facteur de chargement sur 1,0, alors quelque chose de très intéressant pourrait se produire.

Supposons que vous ajoutez un objet x à votre hashmap dont le hashCode est 888 et dans votre hashmap le bucket représentant le hashcode est gratuit, donc l' objet x est ajouté au bucket, mais dites encore une fois si vous ajoutez un autre objet y dont le hashCode est également 888, votre objet y sera ajouté à coup sûr MAIS à la fin du compartiment ( car les compartiments ne sont rien d'autre que la mise en œuvre de LinkedList stockant la clé, la valeur et ensuite ) maintenant, cela a un impact sur les performances! Étant donné que votre objet y n'est plus présent dans la tête du seau si vous effectuez une recherche, le temps pris ne sera pas O (1)cette fois, cela dépend du nombre d'articles 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.

Corrélation entre les performances, la collision de hachage et le facteur de charge?

Facteur de charge plus faible = plus de godets libres = moins de risques de collision = hautes performances = encombrement élevé.

Corrigez-moi si je me trompe quelque part.

De la documentation :

Le facteur de charge est une mesure de la capacité maximale de la table de hachage à obtenir 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 empirique" pour spécifier un facteur de charge initial.

Pour HashMap DEFAULT_INITIAL_CAPACITY = 16 et DEFAULT_LOAD_FACTOR = 0.75f, cela signifie que le nombre MAX de TOUTES les entrées dans le HashMap = 16 * 0.75 = 12 . Lorsque le treizième élément sera ajouté, la capacité (taille du tableau) de HashMap sera doublée! Perfect illustration a répondu à cette question: l' image est prise d'ici:

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

Si les seaux sont trop pleins, alors nous devons regarder à travers

une très longue liste chaînée.

Et c'est en quelque sorte vaincre le point.

Voici donc un exemple où j'ai quatre seaux.

Jusqu'à présent, j'ai un éléphant et un blaireau dans mon HashSet.

C'est une assez bonne situation, non?

Chaque élément a zéro ou un élément.

Maintenant, nous mettons deux autres éléments dans notre HashSet.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

Ce n'est pas trop mal non plus.

Chaque seau n'a qu'un seul élément. Donc, si je veux savoir, est-ce que ça contient du panda?

Je peux regarder très rapidement le seau numéro 1 et ce n'est pas

là et

Je savais que ce n'était pas dans notre collection.

Si je veux savoir s'il contient du chat, je regarde le seau

numéro 3,

Je trouve le chat, je sais très vite si c'est dans notre

collection.

Et si j'ajoute du koala, eh bien ce n'est pas si mal.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

Peut-être maintenant au lieu de dans le seau numéro 1 en ne regardant que

un élément,

Je dois en regarder deux.

Mais au moins je n'ai pas à regarder l'éléphant, le blaireau et

chat.

Si je cherche encore du panda, il ne peut être que dans un seau

numéro 1 et

Je n'ai pas à regarder autre chose qu'une loutre et

koala.

Mais maintenant, je mets l'alligator dans le seau numéro 1 et vous pouvez

voir peut-être où cela va.

Que si le seau numéro 1 continue de grossir de plus en plus et

plus gros, alors je dois essentiellement regarder à travers tous

ces éléments pour trouver

quelque chose qui devrait être dans le compartiment numéro 1.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

Si je commence à ajouter des chaînes à d'autres compartiments,

à droite, le problème devient de plus en plus grand dans chaque

seau simple.

Comment pouvons-nous empêcher nos seaux de devenir trop pleins?

La solution ici est que

          "the HashSet can automatically

        resize the number of buckets."

Il y a le HashSet se rend compte que les seaux deviennent

trop plein.

Il perd cet avantage de cette recherche unique

éléments.

Et cela ne fera que créer plus de seaux (généralement deux fois comme avant) et

puis placez les éléments dans le bon seau.

Voici donc notre implémentation de base de HashSet avec des

enchaînement. Maintenant, je vais créer un "HashSet auto-redimensionnant".

Ce HashSet va se rendre compte que les seaux sont

devenir trop plein et

il a besoin de plus de seaux.

loadFactor est un autre champ de notre classe HashSet.

loadFactor représente le nombre moyen d'éléments par

seau,

au-dessus duquel nous voulons redimensionner.

loadFactor est un équilibre entre l'espace et le temps.

Si les godets sont trop pleins, nous redimensionnerons.

Cela prend du temps, bien sûr, mais

cela peut nous faire gagner du temps sur la route si les seaux sont un

un peu plus vide.

Voyons un exemple.

Voici un HashSet, nous avons ajouté quatre éléments jusqu'à présent.

Éléphant, chien, chat et poisson.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

À ce stade, j'ai décidé que le loadFactor, le

seuil,

le nombre moyen d'éléments par seau que je vais bien

avec, est de 0,75.

Le nombre de godets est buckets.length, qui est de 6, et

à ce stade, notre HashSet a quatre éléments, de sorte que le

la taille actuelle est de 4.

Nous allons redimensionner notre HashSet, c'est-à-dire que nous ajouterons plus de compartiments,

lorsque le nombre moyen d'éléments par seau dépasse

le loadFactor.

C'est lorsque la taille actuelle est divisée par des seaux. La longueur est

supérieur à loadFactor.

À ce stade, le nombre moyen d'éléments par compartiment

est 4 divisé par 6.

4 éléments, 6 seaux, soit 0,67.

C'est moins que le seuil que j'ai fixé à 0,75, nous sommes donc

d'accord.

Nous n'avons pas besoin de redimensionner.

Mais maintenant, disons que nous ajoutons la marmotte.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

La marmotte se retrouverait dans le seau numéro 3.

À ce stade, la taille actuelle est 5.

Et maintenant, le nombre moyen d'éléments par seau

est la taille actuelle divisée par buckets.length.

Cela fait 5 éléments divisés par 6 seaux soit 0,83.

Et cela dépasse le loadFactor qui était de 0,75.

Afin de résoudre ce problème, afin de rendre le

des seaux peut-être un peu

plus vide de sorte que des opérations comme déterminer si un

le seau contient

un élément sera un peu moins complexe, je veux redimensionner

mon HashSet.

Le redimensionnement du HashSet prend deux étapes.

Je vais d'abord doubler le nombre de seaux, j'avais 6 seaux,

maintenant, je vais avoir 12 seaux.

Notez ici que le loadFactor que j'ai défini à 0,75 reste le même.

Mais le nombre de seaux modifiés est de 12,

le nombre d'éléments est resté le même, est 5.

5 divisé par 12 est d'environ 0,42, ce qui est bien en deçà de notre

facteur de charge,

nous allons donc bien maintenant.

Mais nous n'avons pas fini parce que certains de ces éléments sont en

le mauvais seau maintenant.

Par exemple, l'éléphant.

L'éléphant était dans le seau numéro 2 car le nombre de

personnages en éléphant

avait 8 ans.

Nous avons 6 seaux, 8 moins 6 est 2.

C'est pourquoi il s'est retrouvé au numéro 2.

Mais maintenant que nous avons 12 seaux, 8 mod 12 est 8, donc

l'éléphant n'appartient plus au seau numéro 2.

L'éléphant appartient au seau numéro 8.

Et la marmotte?

Woodchuck est celui qui a commencé tout ce problème.

La marmotte s'est retrouvée dans le seau numéro 3.

Parce que 9 mod 6 est 3.

Mais maintenant, nous faisons 9 mod 12.

9 le mod 12 est 9, la marmotte passe au numéro 9.

Et vous voyez l'avantage de tout cela.

Désormais, le compartiment numéro 3 ne comporte que deux éléments, alors qu'auparavant il en avait 3.

Voici donc notre code,

où nous avions notre HashSet avec un chaînage séparé

n'a fait aucun redimensionnement.

Maintenant, voici une nouvelle implémentation où nous utilisons le redimensionnement.

La plupart de ce code est le même,

nous allons encore déterminer s'il contient le

valeur déjà.

Si ce n'est pas le cas, nous déterminerons dans quel seau il

devrait entrer et

puis ajoutez-le à ce compartiment, ajoutez-le à cette LinkedList.

Mais maintenant, nous incrémentons le champ currentSize.

currentSize était le champ qui gardait une trace du nombre

d'éléments dans notre HashSet.

Nous allons l'incrémenter, puis nous allons regarder

à la charge moyenne,

le nombre moyen d'éléments par seau.

Nous ferons cette division ici.

Nous devons faire un peu de casting ici pour nous assurer

que nous obtenons un double.

Et puis, nous comparerons cette charge moyenne au champ

que j'ai défini comme

0,75 lorsque j'ai créé ce HashSet, par exemple, qui était

le loadFactor.

Si la charge moyenne est supérieure à loadFactor,

cela signifie qu'il y a trop d'éléments par seau sur

moyenne, et je dois réinsérer.

Voici donc notre implémentation de la méthode de réinsertion

tous les éléments.

Tout d'abord, je vais créer une variable locale appelée oldBuckets.

Qui fait référence aux seaux tels qu'ils sont actuellement

avant de commencer à tout redimensionner.

Remarque Je ne crée pas encore de nouveau tableau de listes liées.

Je ne fais que renommer les compartiments en anciens compartiments.

Rappelez-vous maintenant que les seaux étaient un domaine dans notre classe, je vais

pour créer maintenant un nouveau tableau

de listes liées, mais cela aura deux fois plus d'éléments

comme il l'a fait la première fois.

Maintenant, je dois faire la réinsertion,

Je vais parcourir tous les anciens seaux.

Chaque élément de oldBuckets est une LinkedList de chaînes

c'est un seau.

Je vais passer par ce seau et obtenir chaque élément

seau.

Et maintenant je vais le réinsérer dans les newBuckets.

J'obtiendrai son hashCode.

Je vais déterminer de quel indice il s'agit.

Et maintenant, je reçois le nouveau compartiment, la nouvelle LinkedList de

cordes et

Je vais l'ajouter à ce nouveau seau.

Donc, pour récapituler, les HashSets comme nous l'avons vu sont des tableaux de Linked

Listes ou seaux.

Un HashSet auto-redimensionnant peut réaliser en utilisant un certain rapport ou

Je choisirais une taille de table de n * 1,5 ou n + (n >> 1), cela donnerait un facteur de charge de 0,66666 ~ sans division, ce qui est lent sur la plupart des systèmes, en particulier sur les systèmes portables où il n'y a pas de division en le matériel.