Impact du facteur de charge sur le temps de recherche?

Question

As Java doc explains

En règle générale, le facteur de charge par défaut (.75) offre un bon compromis entre le temps et les coûts d'espace. Des valeurs plus élevées diminuent la surcharge de l'espace mais augmentent le coût de la recherche (reflété dans la plupart des opérations de la classe HashMap, y compris get et put).

Je ne reçois pas comment augmenter le facteur de charge dire à 1, augmenter le temps de recherche

Par exemple: - La capacité initiale est de 16 et le facteur de charge est 1 alors redimensionne à 32 va se passer après la taille atteint à 16 * 1 = 16. maintenant, si je mets toute nouvelle nouvelle entrée combien de temps recherche seront plus en comparaison si le facteur de charge aurait été .75 (dans ce hashmap cas aurait redimensionnées au format 2)

Comme cette la réponse ditWhat is the significance of load factor in HashMap? que moins le nombre de seaux gratuits, plus le chances de collision.

Je ne suis pas sûr du nombre de seaux libres liés au risque de collision.

Selon ma compréhension, le godet est décidé en fonction du hashcode de l'objet clé. Si le résultat est le même que pour un objet déjà clé dans le bucket, alors il y aura seulement des chances de collision sinon il ira dans un autre seau (hors du seau disponible). Alors, comment se fait-il que la collision soit liée à des seaux gratuits? Voulez-vous dire que même si hashcode est différent et hashmap est plein, alors il va essayer de l'adapter dans le seau existant?

Ce n'est pas un doublon de What is the significance of load factor in HashMap?. Je demande le point spécifique qui n'est pas répondu dans ce lien

Answer 1

Alors comment se fait-il que la collision soit liée à des seaux gratuits? Voulez-vous dire que même si hashcode est différent et hashmap est plein, alors il va essayer de l'adapter dans le seau existant?

Le code de hachage d'une clé peut être une valeur quelconque int de 0 à 2 -1. Cela signifie que la valeur de la méthode hashCode() est généralement supérieure au nombre de compartiments. Par conséquent, deux clés de différents codes de hachage peuvent être mappées sur le même compartiment. Par exemple, si le nombre de compartiments est de 16, les codes de hachage 1, 17, 33, 49, etc ... seront tous mappés au compartiment n ° 1.

S'il y a plus de compartiments, un plus petit nombre de codes de hachage uniques peut être mappé dans le même compartiment, il y a donc moins de chances que le même compartiment contienne plusieurs entrées. Par exemple, si le nombre de compartiments est augmenté à 32, les codes de hachage 1 & 33 seront toujours mappés au compartiment n ° 1, mais les codes de hachage 17, 49, etc ... seront mappés à un compartiment différent (# 17) - donc moins de chance de collision.

Lorsque le facteur de charge < 1, le nombre moyen d'entrées dans chaque godet est < 1, ce qui vous donne une bonne chance de temps de recherche constante (à moins que votre clé a une terrible mise en œuvre hashCode qui retourne quelques valeurs uniques).

Answer 2

Une table de hachage est soutenue par un tableau.
La taille de la matrice de sauvegarde et la taille de la table de hachage de la structure de données ne correspondent pas au même nombre.
Un élément peut finir par exactement le même emplacement comme un autre élément en raison de la collision et le nombre de collisions est fonction de la taille de la matrice de support aussi (en plus de la fonction de hachage) car il est
index_in_array = Math.abs(element.hashCode() % array.length);
Même un parfait La fonction de hachage n'aide pas si vous avez besoin d'une très petite table de support pour un très grand nombre d'éléments.
Plus le groupe de support est grand, plus l'espace pour placer un élément est grand et moins les risques de collision sont importants.
Le facteur de charge (le rapport des éléments insérés à la taille du tableau) détermine quand le tableau de sauvegarde devrait grossir.
Pour un taux de chargement de 1, cela signifie que vous avez épuisé toutes les fentes du groupe de support, ce qui signifie que vous avez plus de collisions car il est impossible d'avoir un cas où vous auriez 1 élément par fente.
Si vous aviez ce cas, vous devriez utiliser un tableau simple en premier lieu