0
$\begingroup$

I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient.

I'm not at all concerned about security. The output should be evenly distributed and appear random in relation to the input, but it doesn't matter if it's possible - even trivially possible - to determine the input that produced a given output.

Most hash functions are designed to be used for cryptographic purposes; they can be used for a task such as this but are not particularly fit for the purpose: they are complex to implement, they are (often intentionally) slow, and they guarantee many properties that are of no concern, such as non-reversibility. A smaller, faster algorithm surely exists that does not waste space and time guaranteeing these properties.

Non-cryptographic hash functions such as the Mersenne Twister or WELL are closer to what I'm looking for, but they're state-permuting PRNGs rather than true hash functions - you can't get the MT hash value of 1 and then the MT hash value of 624001 without running 1000 twist operations to advance its state. Yes, you can use a state-permuting PRNG to emulate a hash function by just running it N times (or N mod period times) for an input of N, but it requires either a huge amount of time or a huge amount of precomputation or both. And even if you ignore that issue, such functions are... well, they're faster than cryptographic hashes, but they still make gaurantees that the problem doesn't require.

Optimally, what I'm looking for is something like return (seed ** (1.1 + 1/seed)) % 1 - it convolutes the input to produce an output 0..1 and it does it with 4 arithmetic operations and no state. This particular example isn't a good solution because it appears to skew significantly towards certain results. Is there something similarly fast and small (or at least, faster and smaller than the other options I'm aware of) that actually works?

$\endgroup$
  • 2
    $\begingroup$ "The output should [...] appear random in relation to the input, but it doesn't matter if it's possible - even trivially possible - to determine the input that produced a given output." Isn't this a contradiction? Or how is something which "appears random" to be understood in this context? $\endgroup$ – dkaeae Feb 5 at 12:43
  • $\begingroup$ How about CRC ? $\endgroup$ – Yuval Filmus Feb 5 at 13:41
  • $\begingroup$ Well, a hash function is deterministic by definition, it'll never actually be random. By "appears random" I mean "appears independent of the source" - two similar inputs should produce two dissimilar outputs. It should exhibit the avalanche effect. $\endgroup$ – user34457 Feb 6 at 3:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.