Merci de la réponse. Et oui, je me suis mélangé les pinceaux entre hachage et adressage ouverts. Je suis un peu surpris pour la notion d'adressage qui serait plus susceptible à une « mauvaise » fonction de hachage. Le clustering dont tu parles va aussi arriver avec un hachage ouvert (sous forme de liste chaînée), et du coup 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.
Je réfléchis « à voix haute » :
dans le cas du hachage ouvert (table + listes chaînées), on peut garantir une insertion en O(1) à tous les coups
il suffit d'insérer l'élément en début/fin de liste, indépendamment de toute forme d'ordre;
par contre, si on veut éviter les doublons, alors il faut parcourir la liste chaînée (complexité O(n)) pour vérifier que l'objet n'existe pas déjà.
conséquence : en cas d'accès en lecture, il faudra compter sur une complexité en O(n) pour récupérer l'objet.
Dans le cas d'un adressage ouvert, si un objet différent existe déjà à l'adresse (ou indice) de la case déterminée, on va itérer sur les cases suivantes jusqu'à en trouver une libre.
On a donc bien une complexité O(n) en cas de collision;
pour les mêmes raisons que précédemment, on a potentiellement aussi une complexité O(n) pour la recherche d'un objet en cas de collision.
Donc il me semble que dans les deux cas, la complexité en cas de collision est la même. Certes, l'effet de clustering dont tu parles peut aussi arriver (mais après tout, si j'ai une liste chaînée de mes objets en collision, n'est-ce pas quelque part aussi une forme de 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).
[ Par contre je me dis que si jamais j'ai une table à adressage ouvert, je pourrais potentiellement tenter de trier mes entrées de collision sans doute à l'aide d'un moyen pour savoir combien d'objets ont le même hash, et ainsi ne trier que les entrées importantes1, avec une complexité de « seulement » O(log,円n). ]
j'ai conscience que telle que je la décris, cette méthode n'est pas faisable en pratique à cause d'autres résultats de hachages qui peuvent se trouver « au milieu » des collisions. ↩
[^] # Re: Python
Posté par lasher . En réponse à la dépêche OpenJDK JEP 180: HashMap, collisions & attaques par la complexité. Évalué à 2.
Merci de la réponse. Et oui, je me suis mélangé les pinceaux entre hachage et adressage ouverts. Je suis un peu surpris pour la notion d'adressage qui serait plus susceptible à une « mauvaise » fonction de hachage. Le clustering dont tu parles va aussi arriver avec un hachage ouvert (sous forme de liste chaînée), et du coup 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.
Je réfléchis « à voix haute » :
Donc il me semble que dans les deux cas, la complexité en cas de collision est la même. Certes, l'effet de clustering dont tu parles peut aussi arriver (mais après tout, si j'ai une liste chaînée de mes objets en collision, n'est-ce pas quelque part aussi une forme de 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).
[ Par contre je me dis que si jamais j'ai une table à adressage ouvert, je pourrais potentiellement tenter de trier mes entrées de collision sans doute à l'aide d'un moyen pour savoir combien d'objets ont le même hash, et ainsi ne trier que les entrées importantes1 , avec une complexité de « seulement » O(log,円n). ]
j'ai conscience que telle que je la décris, cette méthode n'est pas faisable en pratique à cause d'autres résultats de hachages qui peuvent se trouver « au milieu » des collisions. ↩