Ces derniers temps, j'ai appris à connaître les tables de hachage. Il y a quelques exemples de résolutions de collision et l'un d'entre eux est le sondage quadratique. Pourquoi quelqu'un utiliserait-il le sondage quadratique ? Sait-il que la table de hachage sera toujours moins qu'à moitié pleine ? Et si c'est le cas, pourquoi utilise-t-il une table aussi grande pour commencer ?
Réponses
Trop de publicités?
Pourquoi utiliser le sondage quadratique ?
En supposant que nous ayons besoin de certains algorithme de résolution des collisions,
Le sondage quadratique peut être un algorithme plus efficace dans une table de hachage fermée, car il évite mieux le problème de regroupement qui peut se produire avec le sondage linéaire, bien qu'il ne soit pas immunisé.
Le sondage quadratique n'est pas parfait, mais il présente certains avantages par rapport aux autres solutions :
Les avantages du chaînage quadratique (ou d'autres formes de chaînage) sont les suivants
- logique plus simple pour la gestion du stockage (pas d'allocation dynamique)
- des insertions plus rapides (pour simplifier le stockage)
- réduction des besoins de stockage en général
(extrait de la réponse de mjv)
Sait-il que la table de hachage sera toujours moins qu'à moitié pleine ?
Pas nécessairement ; cela dépend de la stratégie de redimensionnement utilisée, le cas échéant.
Considérez que votre apprentissage sur QP est avant tout éducatif. Les implémentations pratiques de tables de hachage n'utilisent pas souvent des l'adressage ouvert, d'après mon expérience.
James Dow Allen
Points
11
Le rehash quadratique est un moyen très simple et rapide d'éviter le problème de regroupement du hash linéaire. Il n'est normalement utilisé que lorsque la taille de la table est primordiale (ce qui peut également être intéressant pour d'autres raisons).
Pour éviter tout problème de "table à moitié pleine", il est plus simple de passer à une sonde linéaire à un moment donné. (Vous pouvez placer le test de seuil pour une telle commutation à l'intérieur l'habituel if (index >= size) {index -= size;} afin d'éviter toute perte de performance.
