Ассоциативная некоммутативная хеш-функция

Question

Есть ли хеш-функция со следующими свойствами?

• является ассоциативным
• не коммутативно
• легко реализуемо на 32-битных целых числах: int32 hash(int32, int32)

Если я прав, такая функция позволяет достичь следующих целей

• вычислить хеш составной строки из хешей подстрок
• вычислять хеш одновременно
• вычислить хэш списка, реализованный в двоичном дереве - включая порядок, но без учета сбалансированности дерева

Лучшее, что я нашел до сих пор, это умножение матрицы битов 4х4, но это неудобно для реализации и уменьшает пространство до 16 бит.

Я благодарен за любую помощь.

Answer 1

Это то, что я придумал (написано на Java). Основная идея состоит в том, чтобы разделить 32bit-int на 2 числа. Старшие суммы битов, включая эффект умножения. Младшие биты отслеживают этот эффект умножения. Оно работает. Он имеет хорошее распределение - также против общих аргументов, таких как (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;
  }
}