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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Vladislav Mar 6 at 14:18
  • $\begingroup$ 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. $\endgroup$ – let4be Mar 6 at 14:39
  • $\begingroup$ 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) $\endgroup$ – let4be Mar 6 at 14:56

If you go and change your hash function, you'll have to apply all the ones in the history for following elements (to see if one repeats). The cost of doing that is larger than just handling collisions some way.

Why do you impose this rather strange requirement? If you know the elements beforehand, you can cook up a hash function with no colissions and not too large of a range of the function, but it is quite costly...

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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