Meilleure table de hachage pour l'insertion et la recherche uniquement

Question

Je souhaite créer une table de hachage permettant uniquement l'insertion et la recherche. Une fois que quelque chose est dans la table, c'est pour de bon, sauf si vous créez une nouvelle table de hachage et remplissez le contenu. Existe-t-il des algorithmes/structures de données plus appropriés pour cela (par exemple, B-tree/RB-tree/LLRB-tree)? Mieux serait comme - temps d'insertion et de recherche plus rapides, ou peut être fragmenté plus facilement, ou plus petit. Merci

Answer 1

Si vous savez (approximativement) combien de fois chaque élément sera recherché (et si ces fréquences ne sont pas uniformes), alors vous pouvez utiliser l'algorithme de Knuth (free pdf) pour trouver un arbre optimal qui rendra l'accès plus fréquent éléments plus proches du sommet (et sont donc plus rapidement accessibles). Chaque nœud dans cet arbre serait un code de hachage (utilisé pour naviguer dans l'arbre) et un pointeur vers l'élément réel. Je ne connais aucune implémentation de cet algorithme, cependant ...