Open addressing schemes also put more stringent requirements on the hash function: besides distributing the keys more uniformly over the buckets, the function must also minimize the clustering of hash values that are consecutive in the probe order. Using separate chaining, the only concern is that too many objects map to the same hash value; whether they are adjacent or nearby is completely irrelevant.
Je vais revenir là dessus avec un exemple.
Le clustering dont tu parles va aussi arriver avec un hachage ouvert (sous forme de liste chaînée)
Non.
Dans le hachage ouvert, seules les collisions ont un impact sur les performances (il n’y a pas de phénomène de clustering car chaque bucket est « indépendant »).
Un exemple valant un long discours : soit une fonction de hachage H et une fonction de sondage linéaire (la plus sensible au phénomène de clustering) on pourrait avoir l’exécution suivante :
H("foo") = 0
hachage ouvert : (0) est libre, pas de collision => insertion en (0)
adressage ouvert : (0) est libre, pas de collision => insertion en (0)
H("bar") = 1
hachage ouvert : (1) est libre, pas de collision => insertion en (1)
adressage ouvert : (1) est libre, pas de collision => insertion (1)
H("baz") = 1
hachage ouvert : collision => chaînage en (1)
adressage ouvert : collision => insertion en (2) (sondage linéaire)
H("qux") = 2
hachage ouvert : (2) est libre, pas de collision => insertion en (2)
adressage ouvert : collision (due au clustering induit par la sondage linéaire) => insertion en (3)
On voit que à cause du sondage on crée des collisions artificielles, c’est le phénomène de clustering (qui est donc inexistant en hachage ouvert).
On voit aussi que plus le facteur de charge va augmenter, plus les performances vont se dégrader (c’est aussi le cas avec le hachage ouvert, mais le phénomène est moins rapide).
Enfin, on note que dans le cas où tous les buckets sont utilisés, l’algo’ d’insertion de l’adressage ouvert va échouer.
au moins dans le cas de l'adressage ouvert, il me semblait qu'on bénéficiait au minimum d'une allocation mémoire contiguë garantie.
Oui, l’adressage ouvert peut offrir une meilleur localité spatiale c’est vrai. Mais il faut bien choisir la fonction de sondage pour avoir un équilibre entre localité et clustering.
Mais quand la capacité de ma table à adressage ouvert approche le taux de remplissage fatidique, je dois alors doubler la taille, et re-hacher tous les éléments (qui était l'argument que j'avançais au post précédent). Du coup mes éléments sont potentiellement dispersés à nouveau dans ma table. Et je ne comprends pas bien en quoi c'est pire qu'avec le hachage ouvert (donc avec listes chaînées).
Le hachage ouvert est plus tolérant au l’élévation du facteur de charge.
[^] # Re: Python
Posté par grim7reaper . En réponse à la dépêche OpenJDK JEP 180: HashMap, collisions & attaques par la complexité. Évalué à 3.
Pour citer Wikipédia :
Je vais revenir là dessus avec un exemple.
Non.
Dans le hachage ouvert, seules les collisions ont un impact sur les performances (il n’y a pas de phénomène de clustering car chaque bucket est « indépendant »).
Un exemple valant un long discours : soit une fonction de hachage H et une fonction de sondage linéaire (la plus sensible au phénomène de clustering) on pourrait avoir l’exécution suivante :
On voit que à cause du sondage on crée des collisions artificielles, c’est le phénomène de clustering (qui est donc inexistant en hachage ouvert).
On voit aussi que plus le facteur de charge va augmenter, plus les performances vont se dégrader (c’est aussi le cas avec le hachage ouvert, mais le phénomène est moins rapide).
Enfin, on note que dans le cas où tous les buckets sont utilisés, l’algo’ d’insertion de l’adressage ouvert va échouer.
Oui, l’adressage ouvert peut offrir une meilleur localité spatiale c’est vrai. Mais il faut bien choisir la fonction de sondage pour avoir un équilibre entre localité et clustering.
Le hachage ouvert est plus tolérant au l’élévation du facteur de charge.