Murmur 3F collision
l0rinc opened this issue · 5 comments
I might not be using the api correctly, but we're getting collisons for the following case:
var m1 = new Murmur3F();
m1.update(0);
m1.update(-17664);
var m2 = new Murmur3F();
m2.update(0);
m2.update(-16640);
assert !Objects.equals(new UUID(m1.getValueHigh(), m1.getValue()), new UUID(m2.getValueHigh(), m2.getValue()));
Do we need a finalize or something?
Finishing is done automatically:
Collisions may occur, maybe your numbers are just lucky?
The same doesn't happen with Guava:
Hashing.murmur3_128().newHasher()
.putBytes(a)
.putShort(b)
.hash();
(which returns completely different values by the way).
maybe your numbers are just lucky
This happened as a result of non-malicious usage, that shouldn't happen with Murmur in reality for 128 bits, only after 2^64 random values is it expected to collide.
Hmm, at the time there were tests to verify values against the C implementation and against Guava: https://github.com/greenrobot/essentials/blob/master/java-essentials/src/test/java/org/greenrobot/essentials/hash/Murmur3FTest.java
Maybe can you give the full code how to tested this against Guava?
That's the full context.
We're not using the current implementation after this incident.
This seems to be a user error. If you look closer at what is being called...
/**
* Updates the current checksum with the specified byte.
*
* @param b the byte to update the checksum with
*/
public void update(int b);
It's clear that while taking an int, it is treated as a byte. Thus both numbers are 0 as a byte and thus the result is correct. It's common in Java to pass as int to avoid sign issues.