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

Question

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).

Answer 1

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.