CODEWITHSUNDEEP
data-structureshashtime-complexity
Immanuel
Immanuel

Reputation: 172

Separate Chain Hashing ordered vs unordered

Can you improve separate chain hashing by keeping the linked lists ordered?

How does it affect the operations on the array, time complexity-wise(mainly inserting, deleting and searching)?

At first I thought this might be trivial, but the more I think about it I can't figure out why would you NOT keep it sorted? Surely the few operations of inserting and deleting a node is far less time consuming than having to traverse the whole list with each attempt at finding a certain value?

I'm not looking for any code solution, just the understanding behind the concept. For some reason I could not find any sources discussing this question.

Upvotes: 2

Views: 1302

Answers (1)

Kaidul
Kaidul

Reputation: 15915

At first I thought this might be trivial, but the more I think about it I can't figure out why would you NOT keep it sorted?

I can think of these reasons behind why a hashtable chain's elements are not sorted:

  • The keys in hashtable are not always primitive data-type like integer, float, double or string. It can be anything - any complex object/class instance which are not easily comparable to be sorted. So in that case, everytime you will have to be implement comparing policy for the object to be key (implement <, = operator in C++, implement Comparable<T> in Java etc).

  • Another reason is the chain in hashtable is basically doubly linked list under the hood. So for example, if you want to search an element in a chain, you couldn't take advantage of the binary search to search in logarithmic time because applying binary search on linked list type structure (finding middle) is not straight forward.

  • If the load factor of hashtable is choosen wisely, bucket/chains of the hashtable won't be too dense or too sparse. In this case, every chains will have reasonable number of entries and it will be acceptably fast to run linear search on chain and to ensure amortized constant time complexity.

Edit

If the key is assumed to be integer, then still it won't be beneficial to make the chain sorted. For the two main operations on hashtable - insertion and search, you can't still take advantage of binary search or logarithmic timing because the chains are not array or vector, its doubly linked list. And binary search on linked list is not logarithmic (Finding middle in linked list is not O(1) like array).

Upvotes: 1

Related Questions