4 ms·
> Not in hash tables. There the smaller, the faster. The selection criteria is: not bad (not failing any test), small and fast. Esp. it needs to be inlinable.
by asdkhadsj 8y ago
> Not in hash tables. There the smaller, the faster. The selection criteria is: not bad (not failing any test), small and fast. Esp. it needs to be inlinable.
Can you explain why? Like what use cases are there where you don't actually care how likely something is to collide, you just want it to be fast?
I've always thought being able to predict the chance of collision to be the most important factor on a hasher. When is it not?
- zzzcpan 8y agoYou have to deal with worst case regardless of how likely collisions happen, you can't leave it to a chance. At least if you want a decent hash table implementation.
- dagss 8y agoFirst 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