Associative Non-Commutative Hash Function

Question

Is there a hash function with the following properties?

• is associative
• not commutative
• easily implemented in 32-bit integers: int32 hash(int32, int32)

If I'm right, this function allows me to achieve the following goals

• computes the hash of a concatenated string from substring hashes
• calculate hash at the same time
• compute the hash of a list implemented on a binary tree - including the order, but excluding how the tree is balanced

The best I have found so far is multiplication of a 4x4 bit matrix, but it is inconvenient to implement and reduce the space to 16 bits.

I am grateful for any help.

Answer 1

This is what I came up with (written in Java). The basic idea is to split 32bit-int into 2 numbers. Old bit amounts, including the effect of multiplication. The lower bits track the effect of the multiplication. It is working. It has a good distribution - also against general arguments such as (0, 1), (1, 0).

 public class AssociativelyMergedIntegers { /** biggest unsigned 16-bit prime */ private static final int PRIME = 65521; /** associative, not commutative hash function */ public static int merged(int first, int second) { int firstFactor = remainderOf(first & 0x0000FFFF); int secondFactor = remainderOf(second & 0x0000FFFF); int firstSum = remainderOf(first >>> 16 & 0x0000FFFF); int secondSum = remainderOf(second >>> 16 & 0x0000FFFF); int resultSum = remainderOf(firstSum + (long) firstFactor * secondSum); int resultFactor = remainderOf((long) firstFactor * secondFactor); return resultSum << 16 ^ resultFactor; } private static int remainderOf(long number) { int rest = (int) (number % PRIME); return rest == 0 ? PRIME - 2 : rest; } }