1

I know that hastable datastructure will store key value pair. And that key is sorted based on the hash value.

Whereas the sorted list is the same but sorted on the actual key value rather than the hash.

What is the purpose of hash table- or in other words what is the benefit of sorting key by hash value?

variable
  • 8,262
  • 9
  • 95
  • 215
  • 6
    It is not about the sorting (that is accidental and an artifact of implementation), it is about the lookup. But in general, you should be using a `Dictionary` instead of `Hashtable`. – Mark Rotteveel Nov 26 '21 at 20:01
  • 1
    Related: [what is the difference between list<> and dictionary<> in c#](https://stackoverflow.com/questions/7914830/what-is-the-difference-between-list-and-dictionary-in-c-sharp) and [Why is dictionary so much faster than list?](https://stackoverflow.com/questions/16977694/why-is-dictionary-so-much-faster-than-list) – Mark Rotteveel Nov 26 '21 at 20:05
  • *And that key is sorted* - this is not really correct – Caius Jard Nov 26 '21 at 20:19

1 Answers1

2

Hashtables are accessible in O(1) while a sorted List is accessible in O(log n).

I'll also provide an answer in the comparison of a Dictionary vs HashTable. while a Dictionary is conceptually a hash table, they have some significant differences.

You would want to use Dictionary<TKey, TValue> class instead of the Hashtable class beacuse the Dictionary<TKey, TValue> is a generic type where as a Hashtable is not. So, you actually get type safety using the Dictionary<TKey, TValue>, because you can't insert any random object into it, and you don't have to cast the values you take out.

One extra note, the Dictionary<TKey, TValue> implementation in .NET Framework is actually based on a Hashtable. you can validate this by taking a look at the HashTable implementation - https://referencesource.microsoft.com/#mscorlib/system/collections/hashtable.cs

Ran Turner
  • 14,906
  • 5
  • 47
  • 53