25

What property makes Hash table, Hash list and Hash tree different from each other? Which one is used when? When is table superior than tree.

Passionate programmer
  • 5,748
  • 10
  • 39
  • 43

1 Answers1

28
  • Hashtable: it's a data structure in which you can insert pairs of (key, value) in which the key is used to compute an hashcode that is needed to decide where to store the value associated with its key. This kind of structure is useful because calculating a hashcode is O(1), so you can find or place an item in constant time. (Mind that there are caveats and different implementations that change this performance slightly)
  • Hashlist: it is just a list of hashcodes calculated on various chunks of data. Eg: you split a file in many parts and you calculate a hashcode for each part, then you store all of them in a list. Then you can use that list to verify integrity of the data.
  • Hashtree: it is similar to a hashlist but instead of having a list of hashes you have got a tree, so every node in the tree is a hashcode that is calculated on its children. Of course leaves will be the data from which you start calculating the hashcodes.

Hashtable is often useful (they are also called hashmaps) while hashlists and hashtrees are somewhat more specific and useful for exact purposes..

Lieven Keersmaekers
  • 57,207
  • 13
  • 112
  • 146
Jack
  • 131,802
  • 30
  • 241
  • 343
  • 1
    I am trying to implement Apriori Algorithm for my Data Mining Project & HashTree is a good data structure for calculating the support count of generated candidates. Can someone specify how to implement hash tree (as I am not able to find good info on hashtree on web). Any help would be appreciated, thank you! – saurcery Sep 27 '12 at 22:24
  • 3
    This assumes "hash tree" is a synonym for "Merkle tree". There's also a [general purpose data structure by that name](https://en.wikipedia.org/wiki/Hash_tree_%28persistent_data_structure%29). – Fred Foo May 15 '13 at 11:06
  • "Hashtable: it's a data structure in which you can insert pairs of (key, value)" - this is incorrect, a hash table just requires access to an array of buckets based on the index returned by hashing the key. There doesn't have to be a value distinct from the key - when there isn't it is often termed a hash set (as distinct from a hash map where there is a distinct value). – Tony Delroy Jan 28 '23 at 22:36