17

Is there a hash function with the following properties?

  • is associative
  • is not commutative
  • easily implementable on 32 bit integers: int32 hash(int32, int32)

If I am correct, such a function allows achieving the following goals:

  • calculate hash of concatenated string from hashes of substrings
  • calculate hash concurrently
  • calculate hash of list implemented on binary tree - including order, but excluding how tree is balanced

The best I found so far is multiplication of 4x4 matrix of bits, but that's awkward to implement and reduces space to 16 bits.

I am grateful for any help.

Improve this question
3
  • I'm sure I've seen a hash function like this in a set reconciliation protocol somewhere, but I'm having a lot of difficulty finding it. Commented Nov 7, 2024 at 22:20
  • No, I found it arxiv.org/pdf/2212.13567 and it's clear they recommend commutative functions xor, or wrapping add. I'd be curious to know why you want it to not be commutative. Commented Nov 9, 2024 at 6:47
  • @mako this question would be better asked at cs.stackexchange.com Commented Nov 14, 2024 at 10:30

2 Answers 2

Reset to default
1
+50

Polynomial rolling hash could help:

  • H(A1,...,An) = (H(A1,...,An-1) * Base + An) Mod P

It's easy to concat two results or substract prefix/suffix from result, as long as the length is known.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Matrix multiplication is associative and non-commutative.

You could try representing your hashes as matrices but this will result in a loss of information if they have 0 determinant (which is likely!).

So instead you should generate a triangle matrix with a diagonal of 1's to ensure that you have a determinant of 1 (this guarantees that composition does not loose information).

Furthermore the composition of triangle matrices produces a new triangle matrix, making reading the composition the same as generation.

Note: to use this method the length of your hash must be a triangle number!

Improve this answer

1 Comment

What do you mean by composition of matrices? Matrix multiplication (if so, wouldn't you run out or precision really fast?)?

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.