First off, for small tables, you always take the hash value modulo some small number like 10000. Who cares how good the hash function is, if you end up with 1/1

First off, for small tables, you always take the hash value modulo some small number like 10000. Who cares how good the hash function is, if you end up with 1/10000 chance of collision in the end anyway? Speed is obviously more important in this setting. Second, assume very large hash tables...assume that with noncollision using the data structure takes time T1(H) and with collission it takes T2(H) for hash function H, and that the probability of collision is P(H). So your total cost is then P(H) T2(H) + (1 - P(H)) T1(H) Which is approximately P(H) T2(H) + T1(H) Easy to play with numbers so that a worse but cheaper hash has a lower total cost. In fact this will usually be the case I would expect... T2 is multiplied with P and disappears for all but the very worst hashes/extremely expensive T2