CODEWITHSUNDEEP
data-structureshashmaphashtable
Adam Zerner
Adam Zerner

Reputation: 19168

In handling hash collisions, why use a linked list over a BST?

A linked list takes O(n) to search while a BST takes O(log n). So why use a linked list to handle collisions? The only reason I could think of is because inserting into the linked list is O(1) whereas inserting into the BST is O(log n).

Upvotes: 3

Views: 521

Answers (3)

NPE
NPE

Reputation: 500157

I imagine the main reason is ease of implementation. At least one widely-used implementation of a hash table has recently moved from using linked lists to using a hybrid of linked lists and balanced trees: JEP 180: Handle Frequent HashMap Collisions with Balanced Trees in Java 8:

The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).

It is worth noting that using a tree over a list requires that the elements can be ordered. A plain hash table (with or without linked lists) does not have this requirement: all it requires is that the elements are hashable and comparable for equality.

Upvotes: 2

John Kugelman
John Kugelman

Reputation: 361547

If the hash function is good and the hash table load factor isn't too high then there shouldn't be many collisions in any one bucket. A linked list is a very simple data structure that is good enough with a low number of collisions. It is fast and it takes little space. Remember, most buckets will have either 0 or 1 values in them.

Also, a BST would impose the requirement that items be orderable. One nice property of hash tables is that the keys don't need to be comparable.

Upvotes: 5

mcdowella
mcdowella

Reputation: 19601

The justification of a hash table is that there should be very few items hashing to the same hash slot. For these small numbers, a linked list should actually be faster than the BST (better constant factors) and will in any case be simpler and more reliable to code. The worst case for a BST is the same as a linked list in any case, unless you want to go really over the top and use a balanced tree.

Upvotes: 5

Related Questions