0

Does the fact that the keys are usually strings, make it more useful for collections of string data? I know that a hash table uses less space, because it has a chunk of memory allocated to it, rather than for each character of each string.

In terms of search, O(m) is the worst case, where m is the length of a key. Binary tree search is O(log n), so I guess I should compare which is more efficient depending on a situation?

P.S. Before you vote to close, this not an opinion question. I need real facts regarding data structures to make the optimal choice.

Thank you

Oleksiy
  • 37,477
  • 22
  • 74
  • 122

1 Answers1

3

You have to decide what you are looking for in terms of use cases. As far as facts are considered, here are the points we should keep in mind.

  1. HashTable stores data for key, and it can be used only if you want to search a particular string. So, if you want to search all strings starting with K, then you will have to iterate whole Hashtable, and order information is also lost while inserting data in table.

  2. As far as BST is considered, it is easy to store strings in it and it will store strings are per it's natural ordering, but at each node it will have to match all the characters , and that is not good from search time point of view.

  3. Now coming to Trie, unlike Hashtable and BST, Trie is not good from storage point of view, and it will take too much space, but from search point of view, it is much faster.

Once again, it all depends what you want to buy and at what price , based on this you can go for Hashtable,BST,Trie or SuffixTree.

AKS
  • 1,393
  • 3
  • 19
  • 29