News for hackers. Stuff that matters.
Re:Problems with Hash Tables by fauigerzigerk on Friday January 08, 2010 @05:15PM (#1040564)
You're basically saying that computational complexity theory cannot make any valid claims about the actual complexity of algorithms. That's a pretty far reaching assumption you're making there.

In my view, the author did two things, and maybe this debate results from his rather rambling style that made it a little difficult to separate the two.

One thing he did was to explain theoretical properties of possible (bad) hash table implementations and hash functions. And the other thing he did was to claim that these bad implementations are actually out there.

I did not find a flaw in his theoretical analysis. Maybe there is one that you can find, but if you do you should be able to prove him wrong without any empirical evidence. His second claim that these issues frequently occur in the wild is where we do indeed need empirical evidence.

I don't believe that bad hash table implementations are widely used. They are very central components of programming languages and libraries and I suspect that any glaring mistakes would have been found.

But one thing I can say for sure is that bad hash functions exist in the wild. I know because I have written some of them. It's not trival to write a hash function that distributes hash values evenly across all buckets. I really do think that hardly anyone bothers to actually analyse the distribution of their ad-hoc hash functions.

In OO languages people write lots of little hash functions all the time. They're not well designed or well tested pieces of code.

There are no comments on this comment yet.