0
$\begingroup$

I have permutations:

4 1 2 5 3
4 3 2 5 1

numbers can be order magnitude of 1000 (fits in two bytes) I want compute 32 bit (or better 64 bit) hashes, it should be non cryptographically secure but evenly distributed in 32 or 64 bits.

This second permutations is derived from first by swap 1-st and 4-th element (count form zero). I want incremental hash: if I know hash of first permutation, should be fast and easy obtain hash of second by knowing only 1-st and 4-th element.

Apart from evenly distribution, candidate can be modified XOR. XOR has disadvantage, that is insensitive to order - modified XOR computes xor with numbers and its positions. Smaller disadvantage , that would be 10-12 bits for this numbers instead of 32 or 64 bits, but 10-12 bits is enough to unique distinguish between permutations? when number bits would be order of magnitude of log2(permutation len)?

Unfortunately xor of permutation give 0 (or constant number?), xor of two permutations also.. Is possible add bit rotations but with incrementality?

What about checksum defined below: simple sum is insensitive to order, but if we sum products: tab[index]*(index+1)? This is order sensitive.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Polynomial hash: cp-algorithms.com/string/string-hashing.html#toc-tgt-0 $\endgroup$ – Dmitry Aug 24 '20 at 7:58
  • 1
    $\begingroup$ What is your question? $\endgroup$ – Pål GD Aug 24 '20 at 8:20
  • $\begingroup$ Maybe Fletcher checksum is good solution? $\endgroup$ – Saku Aug 24 '20 at 8:47
  • $\begingroup$ Fletcher sum has two components: lower bits is insensitive to the order of bytes or numbers, while upper is sensitive. How I can incremental modify it? Lower component modification is easy - I subtract old value and add the new. But how change upper component? $\endgroup$ – Saku Aug 24 '20 at 9:15

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.