rgluzman wrote:What does it mean "collisions" and "collisions resolutions" please ?
Wikipedia can explain it much better and more thoroughly than I can:
http://en.wikipedia.org/wiki/Hash_function
But I'll give it a shot. You're mapping some big compound key, say 100 bytes, into only 128 bits (16 bytes). It is IMPOSSIBLE to map EVERY 100 byte value into 16 bytes. So the hash function is simply trying to distribute your values as evenly as possible, to assign a random-looking but easily-reproduced value to each input value. A good hash function will tend to do a very good job of mapping your keys to unique values, but this is ultimately an impossible task unless it has as many bytes available as your input. So sometimes, two different input values will map to the same output value. For instance, "ABC" might map to 5, but "DEF" might ALSO map to 5. That's a collision. Well, it can't assign 5 to BOTH of them because it must give you a unique value. So it uses a second algorithm to search for an available value that hasn't been used yet. So it might then map "DEF" to 7 because nobody has used 7 yet. That's the collision resolution.
And that's all just fine if everything's in one application. Even though it isn't what the hash function assigned, DEF will still always be mapped to 7 in that one application.
But what happens if both ABC and DEF are in different applications? Well, in your first application, ABC will map to 5. In your second application, DEF could map to 5 as well, because it's likely that nothing else will have taken the 5 spot in your second application. Now you have, I suppose you could say, an "unresolved collision".
With a 128 bit hash function, you have a VAST number of possible key values, 2^128, or over 3.4*10^38.
Let's see, looking up the probability since it's been way too long since I had a probability class, and assuming I'm getting this right:
The probability of a collision for N random keys = 1 - (2^128)! / ((2^128)^N * (2^128 - N)!)
And that's, uh, really not going to be computable, directly, on any computer. So, OK, what about an approximation function?
The probability of a collision for N random keys is ABOUT 1-e^(-N^2/(2*2^128)) is ABOUT 1-2.7182818^(-N^2/2^129).
So let's say you have ten million random keys. The chance of a collision with an ideal hash algorithm is about 1-2.7182818^(-10000000^2/2^129) = 0 to as many decimal places as Excel will calculate. Microsoft's calculator seems to be indicating 0 out to 25 decimal places or so. In other words, the chance of collision is ZERO for all practical purposes.
Now, your data isn't perfectly random, and the hash algorithm isn't some ideal thing that perfectly distributes your input data, so perhaps the chances are higher. However, it does still seem EXTREMELY unlikely that this is actually causing your problem. I STILL wouldn't use a hash algorithm in this way, because it can cause problems in theory, but it'll probably never cause problems in practice.
So we probably need another explanation for what you're seeing.
