Hacker News Reader

Comment by yarg | Hacker News Reader

In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might not be such a bad idea (especially if you're IO bound in any way).

With a bad hash function you can end up with a high level of bucket utilisation, significantly reducing the efficiency of the structure.

With user defined data there's even the possibility of maliciously crafted input attempting to force collisions as part of a DOS attack.

You can salt your input, and pretty much eliminate the issue - but as far as I can tell, you'll just end up rolling your own crypto.

View on HN

Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions.

Salting is the way to deal with these issues, and for hash tables it works well even if your hash function isn’t cryptographically secure. Hence, for hash tables, salt+fast hash function should be sufficient.

Thanks.

Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes.

It could have some application as a preprocessing step in clustering (if it could be done efficiently).

Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.

Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.

The term for this is locality sensitive hashing, and it's very useful in some contexts.

Reply on news.ycombinator.com