# 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? – Vladislav Mar 6 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. – let4be Mar 6 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) – let4be Mar 6 at 14:56