Hacker News Reader

Comment by gruez | Hacker News Reader

Another question: doesn't the O(1) property of hashtables require that there's no collisions? Because of the birthday paradox, you'll need an insanely large hashtable to avoid collisions, and if you don't (or get unlucky), the performance approaches O(n) as the hashtable gets fuller.

If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".

View on HN

Collisions are expected (fill factors are typically typically 2/3 to 3/4). You make every bucket in the table a linked list. And check each value in the list against that for which you are searching.

This, I believe, is the exactly the behavior the parent commenting was describing (and bemoaning.) If you you have to check against every term in a linked list (an operation proportional to the length of the list), then your hash table ceases to be constant-time once you get collisions. In that case, if you have a hash table of fixed size, but arbitrarily increase the number of entries in the table, then the look-up time tends as O(n).

> if you have a hash table of fixed size

No HashTable implementation worth it's salt is going to have a fixed size table. They are going to dynamically grow the size of the table (double it) once certain level of utilization is reached in the table (say 50%). In practice this means that chains at the same bucket will be of some small constant length assuming a good hash function.

Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.

Or use probing.

Java switches to Red-Black after a bucket's linked list's length has grown upto some constant number(8?).

Reply on news.ycombinator.com