Andrew Haley writes: > > After a bit of experimenting, I get 1651956 collisions per 10716023 > probes (about 16%) which is not far from what Knuth expects for an > unsuccessful lookup with a truly random hash function and a half-full > table. Sorry, a thinko. This is the actual number of collisions for a *successful* lookup, i.e. the condition where the key is present but the key that is found in the table is the wrong key. I didn't count the number of probes for nonexistent keys. Andrew.
