# Looking for memory-efficient way to detect hash collisions

Given a hash function H, it's possible that H(a) = H(b) = c

Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set

After operation is done, we'd get a set of hashes [H1 ... Hm] where m < k, meaning we had collisions

What would be the most memory-efficient way(without storing all of hashes and hashed items) to determine if we've ever hashed item X before and if we did, did it collide with anything?

Is it even possible to relax memory constrains on such kind of task?

• Well, clearly you do not have to store anything but the original data set and be able to find all repetitions and hash collisions simply by iterating all the dataset for every element, what gives $O(n^2)$ time complexity. Will it work for you? If no, please specify time complexity restrictions. UPD: I think I have got it now: you have an input stream of items and you want to get rid of storing the whole dataset, am I correct? Mar 6, 2020 at 14:18
• More wide task is the following - I have a stream of strings, I want to be able to use a hash function over each string to map it to a hash while providing a guarantee there was no collision, if there was a collision I'd need to modify the output hash in some consistent way(like adding "-n" suffix). This stream of strings is very-very-very big, I will never be able to store it in ram. Mar 6, 2020 at 14:39
• Task could be solved by moving the full mapping to a distributed persistent storage, it's an option if I can find a way to make 99% of operations happen in memory and 1% go to database for lookup(like in case of bloomfilters which can be used to reduce n of db access) Mar 6, 2020 at 14:56

Assume you have a good hash function producing an n bit hash code, that is $$2^n$$ possible values. Assume you are hashing k values, so there are about $$k^2/2$$ pairs of hash codes that might collide. The probability of a collision is about $$k^2 / 2^{n+1}$$.