Even if I weren't the best hash author ever (TM), I still wouldn't find much use in this article. You can't argue without evidence, and this provides none. If you want to argue that the amortization creates latency bugs, you need to measure resize latency on some hash or another. If you want to complain about bad hash functions being used, you need to find one and show me a collision rate analysis.

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.

Hmm.

  > You can't argue without evidence ...

I guess as a mathematician I find evidence based arguments unconvincing, and exposition of principles more interesting. I'm now aware of the issues (although in truth I already was before reading this article) and so if implementing my own hash tables would know what to be wary of, and be ready to do some research, analysis and measurements.

But each to their own. I think we'll simply have to agree to disagree.

As a mathematician, I find evidence-based arguments very convincing... where do you think that QED comes from, the planet of magic unicorns?

Purely mathematical proofs are nothing but supplying a pile of evidence, in the form of theorems and facts that both the proof-reader and proof-writer agree on, to support the argument that the proof is attempting to make.

What you have done in your article is this:

"X implies Y, QED."

And when people pointed this out, you balked, rather than writing a follow up that looked like this:

"X may imply Y under many circumstances. Take X. A, B, C, and Q are very common implementations of X, and all of them do Y, based on the following analysis..."

My article?

But leaving that aside, I simply don't understand your points at all. In what way is a mathematical proof "a pile of evidence"? Consider, as a simple, single example the Banach-Tarski theorem. To help me understand you, perhaps you could explain how the proof of that is "a pile of evidence."

As I said elsewhere, I'm baffled by the responses here, so I'm not going to reply any more until, and if, I understand the points of view being expressed.

EDIT: speeling cerrocted

Wait,

Arguing from principle is great but ...not only does he not give numerical evidence, he also doesn't give evidence in terms of describing which commonly used libraries or applications use what hashing method.

I don't see much exposition of principles going on when the author asserts that hash functions are much slower than comparison functions, for example. If you're going to make an empirical argument, you need empirical evidence.

I'm baffled by some of the comments here, I really am. I'm going to leave this for a bit and come back later to see if I can make sense of it. Clearly people disagree with me, but it seems to me that there are several principles and concerns that are validly raised.

This is an opinion piece - he doesn't like hash tables. For him personally, he prefers not to use them and instead to use other structures such as balanced trees. He says that there are gotchas with hash-tables that aren't always realised by those who don't read the small print and take care. That seems unassailable to me. There are gotchas.

He gives an example of a bad hash-function, and points out that you need good ones. Designing a good hash function is part-art, part-science, and can be very hard. Certainly it deserves a full scholarly article and justice couldn't be done in a blog like this.

You've highlighted:

   > the author asserts that hash functions are
   > much slower than comparison functions, for
   > example.

He said:

  > hash functions have to be blindingly fast - because
  > comparisons are already really fast.

That seems pretty clear to me. The reasons are then expanded, but the point remains. Crypto-hash functions are not fast, and yet I've seen them suggested as good hash functions. In many cases, though, they're not fast enough.

But this isn't really the place for a full point-by-point discussion of the issues. I think the piece makes useful and interesting points. It's not a journal article, it's a blog piece that allows the author to vent his prejudices with some supporting arguments.

If want it done properly, read Knuth. I think many of the criticisms here are mis-placed.

In your modded-down post, I think you were intending to mean numeric evidence like bench-marks but you actually wrote that you weren't convinced by evidence, period.

The author makes some logical arguments, which could be considered evidence. But as the GP points out, a lot of his assertions at least seemed to lack both numeric and logical evidence - so your assertion comes-off a bit muddle headed.

I found some of the article's points interesting too but I don't think this is problem people are having with this earlier post.

I think the real objection is that it's a meandering rant, not a well-structured essay explaining the pitfalls of using hash tables.