Optimisation des tables de hachage

Question

Dans plusieurs implémentations de table de hachage, j'ai vu l'utilisation d'heuristiques telles que «transposer» ou «aller de l'avant» pour les éléments dans un compartiment.

1. Quels sont les avantages de l'utilisation de telles heuristiques? Je ne pouvais pas le comprendre moi-même.
2. Quelles autres optimisations peuvent être effectuées au niveau table de hachage/compartiment, pourquoi et dans quelles circonstances?

Optimiser les fonctions de hachage de côté, s'il vous plaît.

Answer 1

Si des collisions se produisent et que les compartiments contiennent plusieurs éléments, qui doivent être examinés, il serait pratique que les articles couramment utilisés soient en début de liste. Ces heuristiques ont un sens s'il y a des raisons de supposer qu'un élément récemment accédé est susceptible d'être accédé à nouveau bientôt. Quand on considère quelque chose comme des nouvelles, il est fort probable que l'on accède fréquemment aux dernières nouvelles.