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 :
- I get a string and hash it with murmur3 to get a 128 bit hash value.
- I get an index by doing the modulus of this hash value with 50021 (closest prime but larger than 50,000).
- I use the index to check if the bit at that position is 1 or 0.
- 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.