1
$\begingroup$

I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects.

E.g., "domain" is the set of valid english phrases with length 1000, and "general set" is the set of all possible strings with length 1000.

Roughly speaking, hashes just project our objects from giant and almost-empty "abacus" desk to much more smaller one.

Question: Is there a smart criterion (expressed in therms of Kolmogorov complexity theory, Shannon entropy), which we could use to be sure that comparison operation will be more effective using hashes?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.