Hacker News Reader

Comment by 19eightyfour | Hacker News Reader

Edit: Update. I pushed a new version that addresses the collisions presented by dchest. I invite you to take a look. Thanks!

Thanks for the feedback. I really appreciate it. Well done finding all those collisions. This is serious! Here's an issue: https://github.com/dosaygo-coder-0/tifuhash/issues/3

Tho it's already valuable enough you pointing this out -- if you have any ideas on how to improve for these cases, please let me know!

Note to self: This community is so good. If something technical gets a bit of traction, you can count on people to find some holes in it. Very valuable. Just wanna say words can't express my gratitude at people's efforts at this. It's very helpful.

View on HN

Update: I have completed testing of a slightly modified version in c++ with SMHasher, details below.

I posted the results in the repo: https://github.com/dosaygo-coder-0/tifuhash/blob/master/tifu...

And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher

Dumb questions, why is this a problem?

   t.hash(0.00000000000000002) == t.hash(0.00000000000000003)

How often would this cause issues in real-world?

If you use it for a hash table, every collision has to be "resolved" in a way that takes time: https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio... .

So if a hash function has lots of collisions it will use the memory of the hash table less efficiently and cause inserts and lookups to be slower. I think collisions are undesirable for other reasons too, none of which are coming to me right now.

But doesn't every hash function have some collisions? Why would this particular example be very bad?

I'm of the same mindset. I mean -- surely there are some collisions always. And I actually liked the property of the original version that a zero value hashed to all zeroes. While the rest of the pre-image was shuffled. But I suppose that being able to compute collisions is not a great thing. You may think that if it is not intended to be used in a cryptographic sense it does not matter. However, if you can easily compute collisions you could, theoretically of course, launch a denial-of-service attacks on a service (cache denial) by sending lots of values to the same hash slot. I mean, with probing and so on there are ways around this and in the end maybe the conventional wisdom ought to be revised, maybe there isn't so much to worry about from a few collisions, even easy to compute ones. But, as it stands, right now, the market demands collision resistance. So I damn well gave it to them.

[keep in mind I'm far from an expert on this]

The thing that bothers me personally about these examples is that there are a lot that end in 0x000000 or 0xffffff, i.e. all bits set or all bits unset in many of the trailing bits.

If you use this for a hash table, a common way that you get your index into the table is:

    index = hash_result % table_size

If you use power-of-two table sizes, then you are going to get these collisions, even though the upper bits differ.

You can use a non-power-of-two table size to compensate for this (prime sizes are typically the most robust choice I think) at the cost of a more expensive modulo operation. See more here in the first section: https://en.wikipedia.org/wiki/Hash_table#Hashing

Reply on news.ycombinator.com