1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Mar 6, 2020 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
    Commented Mar 6, 2020 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
    Commented Mar 6, 2020 at 14:56

2 Answers 2

Reset to default
2
$\begingroup$

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}$.

By picking a large n, you can make that probability arbitrarily small. Ask a physicist to calculate the probability that your computer will be hit by a meteor and completely destroyed, together with all hash values. Pick n large enough that the probability of a collission is say 1,000 times smaller than the probability of a total destruction of the computer involved.

You might also consider what is the amount of damage if you have a collission. For example, the damage could be that as a result, there will be one person in the world who can enter your country with the passport of one specific other person. Make n large enough so that the expect damage through a collision is negligible.

(That's the principle behind the use of GUIDs. There is no guarantee that there are no collisions, but with a proper implementation the probability can be neglected. )

Improve this answer
$\endgroup$
1
$\begingroup$

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...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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