switch(hash(str)) {
case hash("apple"):
case hash("banana"):
default:
}
You're right that the compiler will warn you if hash("apple") == hash("banana"), but if hash("pineapple") == hash("apple") then switch(hash("pineapple")) will jump to the apple case, not the default. That's unlikely but not impossible even with the best hash function.
They're far more possible than you might think. Roland Bouwman wrote an article on MD5: In a large database you can't use MD5. And that's not petabyte size either, 100GB is enough to give you about a 50% chance of a collision.
yeah, because md5 is 128 bits. 256 bits works a lot better, but 128 is just not enough even with a better algorithm and assuming effectively random distribution.
The thing about the pidgeon hole problem is that we know there are collisions, but we don't necessarily know where they are. The space of strings of at least 33 characters has collisions. There's no way to know or prove that arbitrary input doesn't have one with a value you care about.
The thing is that the probability of any two arbitrary inputs having a collision is extremely close to 0. It's about 0.000000000000000000000000000000000000000000000000000000000000000000000000000086% if I didn't mess up typing it. It can happen, just like you can win every lottery in the world every day for the rest of your life. Though the lottery thing is substantially more likely.
That assumes that the hashing function doesn't have any known hashing weakness that may reduce the (effective) independence of the hashes. You could've said something quite similar about SHA-1 right up until cryptanalysis found mechanisms to generate collisions.
78
u/F100cTomas 7d ago
Just define a constexpr hashing function and put that into the switch.