关联非对易散列函数 [英] Associative noncommutative hash function

问题描述

• 是关联的


• 不可交换


• 可以在32位整数上轻松实现： int32 hash（int32，int32）

如果我是正确的，这样的函数可以实现以下目标：
$ b $ ul

计算连接字符串的哈希值哈希并行计算哈希

计算在二叉树上实现的哈希列表 - 包括顺序，但不包括树是如何平衡的

迄今为止我发现的最好的方法是乘以4x4矩阵的比特，但这很难实现，并将空间减少到16比特。

我很感激任何帮助。

解决方案

这就是我想出的在Java中）。
基本思路是将32bit-int分成2个数字。包含乘法效应的旧比特和。年轻的位跟踪乘法效应。
它的工作原理。它具有良好的分布 - 也可以与（0，1），（1,0）等常见参数相比。

  public class AssociativelyMergedIntegers { 
 / **最大无符号16位素数* / 
 private static final int PRIME = 65521; 
 $ b $ / **联合式，不可交换散列函数* / 
 public static int merged（int first，int second）{
 int firstFactor = remainingOf（first& 0x0000FFFF）; 
 int secondFactor = remainingOf（second& 0x0000FFFF）; 
 int firstSum = remainingOf（first>>> 16& 0x0000FFFF）; 
 int secondSum = remainingOf（second>>> 16& 0x0000FFFF）; 
 int resultSum = remainingOf（firstSum +（long）firstFactor * secondSum）; 
 int resultFactor = remainingOf（（long）firstFactor * secondFactor）; 
返回resultSum<< 16 ^ resultFactor; 
 
 
 private static int remainingOf（long number）{
 int rest =（int）（number％PRIME）; 
 return rest == 0 
？ PRIME  -  2 
：休息; 
} 
} 
  

Is there a hash function with following properties?

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

If I am correct, such function allows achieving 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 thats awkward to implement and reduces space to 16bits.

I am grateful for any help.

解决方案

This is what I came up with (written in Java). Basic idea is to split 32bit-int into 2 numbers. Older bits sums including multiplication effect. Younger bits tracks that multiplication effect. It works. It has good distribution - also against common arguments like (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;
  }
}

这篇关于关联非对易散列函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！