I know there are hashing algorithms that have so little known collisions, that it is safe to assume that they don't have any collisions at all (approximately).

Using this information, I tried implementing a bloom filter with only one hash function(in my case it was murmur3). My input for this bloom filter is 50,000 strings and my objective is to find the strings that are duplicate out of these or are repeated more than once. I am using an array of 50021 bits.

Note: I know there are other approaches to finding duplicates, but I am only specifying a small subset of my approach as the entire approach is irrelevant to my question.

The steps that I followed to find the duplicates are as follows :

  1. I get a string and hash it with murmur3 to get a 128 bit hash value.
  2. I get an index by doing the modulus of this hash value with 50021 (closest prime but larger than 50,000).
  3. I use the index to check if the bit at that position is 1 or 0.
  4. If the bit is 1, it indicates that the string is duplicate. Else if the bit is 0 it indicates that the string is not duplicate and I set it to 1.

Using this approach, I get close to 50 collisions.

Is there any way to reduce the collisions further down to 2 or 3?

Alternatively, I am thinking of using a 16 bit hash algorithm which can remove the problem of performing modulus or at least reduce the number of collisions caused by performing modulus on the hash value.

  • 4
    $\begingroup$ I'm voting to close this question as off-topic because this is not about cryptographic properties of a hash function. $\endgroup$ – Maarten Bodewes Dec 20 '16 at 18:52

Using this approach, I get close to 50 collisions.

That's suspiciously low; with these parameters, and if we assume that Murmur3 generated random hash values, we'd expect circa 18,400 collisions.

That might be a bug in your code. If not, what I suspect is happening is that Murmur3 is not acting randomly; instead, the strings that you are hashing are related (for example, they're in an incrementing pattern), and Murmur3, given related inputs, produces related outputs.

If you're simulating how the algorithm would behave under actual operating conditions, well, unless the real inputs also show this same related pattern, your simulation is likely to be misleading.

| improve this answer | |
  • $\begingroup$ You are right about the incrementing pattern @poncho. Could you suggest another approach that I might use to reduce the collisions? $\endgroup$ – Aniketh Jain Dec 21 '16 at 4:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.