Hashtable est rapide

Question

s [0] * 31^(n-1) + s [1] * 31^(n-2) + ... + s [n-1]. Est la fonction de hachage de la chaîne Java, je suppose que le reste des langues est similaire ou proche de cette implémentation.

Si nous avons hash-Table et une liste de 50 éléments. chaque élément est 7 caractères ABCDEF1, ABCDEF2, ABCDEF3 ..... ABCDEFn

Si chaque compartiment de hachage contient 5 chaînes (je pense que cette fonction en fera une chaîne par seau, mais supposons qu'il est 5).

Si nous appelons col.Contains ("ABCDEFn"); // fera 6 comparaisons et découvrira la différence le 7ème.

La table de hachage prendra environ 70 opérations (multiplication et ajouts) pour obtenir le code haché et comparer avec 5 chaînes dans le compartiment. et BANG trouvé.

Pour la liste il faudra environ 300 comparaisons pour le trouver. Dans le cas où il n'y a que 10 éléments, la liste prendra environ 70 opérations, mais la table Hashtable prendra environ 50 opérations. et notez que les opérations de hachage prennent plus de temps (ce sont des multiplications).

Je conclus que HybirdDictionary dans .Net est probablement le meilleur choix pour la plupart des cas qui nécessitent Hashtable avec une taille inconnue, car il me permettra d'utiliser une liste jusqu'à ce que la liste devienne plus de 10 éléments. encore besoin de quelque chose comme HashSet plutôt qu'un dictionnaire de clés et de valeurs, je me demande pourquoi il n'y a pas HybirdSet !!

Alors, que pensez-vous?

Merci

Answer 1

Je pense que vous soulevez un bon point. Les listes peuvent être plus rapides que les tables de hachage pour les petits nombres, et ceci est parfaitement documenté dans la littérature.

Cependant, vous pouvez facilement créer votre propre structure de données, qui selon sa taille count() utilisera une liste ou un hachage.

Answer 2

Est-ce vraiment important? Vous vous souciez généralement de l'impact sur les performances avec de grandes collections de données. 20-30 opérations supplémentaires si la collecte est petite ne fera aucune différence.