Table de hachage vs Liste de hachage vs Hash tree?

Question

Quelle propriété rend la table de hachage, la liste de hachage et l'arbre de hachage différentes les unes des autres? Lequel est utilisé quand? Quand est la table supérieure à l'arbre.

Answer 1

• Hashtable: il est une structure de données dans laquelle vous pouvez insérer des paires de (clé, valeur) dans laquelle la clé est utilisée pour calculer une hashcode qui est nécessaire pour décider où stocker la valeur associée à la clé . Ce type de structure est utile car le calcul d'un hashcode est O (1), donc vous pouvez trouver ou placer un objet à temps constant. (Attention, il existe des mises en garde et des implémentations différentes qui modifient légèrement cette performance)
• Hashlist: il s'agit simplement d'une liste de hashcodes calculés sur différents blocs de données. Ex: vous divisez un fichier en plusieurs parties et vous calculez un hash pour chaque partie, puis vous les stockez tous dans une liste. Vous pouvez ensuite utiliser cette liste pour vérifier l'intégrité des données.
• Hashtree: il est semblable à un hashlist mais au lieu d'avoir une liste de hash vous avez un arbre, de sorte que chaque nœud de l'arbre est un hashcode qui est calculée sur ses enfants. Bien sûr, les feuilles seront les données à partir desquelles vous commencez à calculer les hashcodes.

Hashtable est souvent utile (ils sont aussi appelés hashmaps), tandis que hashlists et hashtrees sont un peu plus précis et utiles à des fins précises ..