hash table vs. linear list

Question

Will there be a instance where a search for a keyword in a linear list will be quicker than a hash table?

I'd basically like to know if there is a fringe case where the search for a keyword in a linear list will be faster than a hash table search.

Thanks!

Answer 1

Searching in a hash table is not always constant-time in reality. If the hash function is a poor match for the data, you can have a lot of collisions, and in the extreme case that every data item has the same hash value, the result looks much like linear search. Depending on the details, this effective linear search might work slower than a linear search over the data in an array. (E.g. open addressing with a quadratic probing sequence, which makes poor use of the processor caches, might well be slower than a linear search over an array.)

Here's an example of a real-world case where all keys ended up in the same bucket: Java bug 4669519.