Facteur de charge et remaniement

Le facteur de charge mesure le niveau de remplissage d'une table de hachage. Si le facteur de charge est dépassé, augmentez la taille de la table de hachage et rechargez les entrées dans une nouvelle table de hachage plus grande. C’est ce qu’on appelle ressasser. Le facteur de charge l (lambda) mesure le niveau de remplissage d'une table de hachage. C'est le rapport du nombre de
éléments à la taille de la table de hachage, c'est-à-dire l = n / N, où n désigne le nombre d'éléments et N le nombre d'emplacements dans la table de hachage.

Notez que l vaut zéro si la table de hachage est vide. Pour le schéma d'adressage ouvert, l est compris entre 0 et 1 ; l vaut 1 si la table de hachage est pleine. Pour le schéma de chaînage séparé, l peut être n'importe quelle valeur.

À mesure que l augmente, la probabilité d'une collision augmente. Des études montrent que vous devez maintenir le facteur de charge inférieur à 0,5 pour le schéma d'adressage ouvert et inférieur à 0,9 pour le schéma de chaînage séparé.

Maintenir le facteur de charge en dessous d'un certain seuil est important pour les performances du hachage. Dans l'implémentation de la classe java.util.HashMap dans l'API Java, le seuil 0,75 est utilisé. Chaque fois que le facteur de charge dépasse le seuil, vous devez augmenter la taille de la table de hachage et rehacher toutes les entrées de la carte dans une nouvelle table de hachage plus grande. Notez que vous devez modifier les fonctions de hachage, car la taille de la table de hachage a été modifiée. Pour réduire le risque de remaniement, car cela coûte cher, vous devez au moins doubler la taille de la table de hachage. Même avec des rehachages périodiques, le hachage est une implémentation efficace pour map.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!