연관 noncommutative 해시 함수

Question

다음과 같은 속성을 가진 해시 함수가 있습니까? 내가 올바른, 이러한 기능은

• 계산 해시 다음과 같은 목표를 달성 허용하고있는 경우 int32 hash(int32, int32)

:

• 는
• 32 개 비트 정수에
• 쉽게 구현 가능하지 교환 법칙이 성립입니다 연관성 하위 문자열의 해시에서 연결된 문자열 연결
(210)
• 계산 해시 동시에
• 리스트의 해시 이진 트리 구현 계산 - 순서를 포함하지만, 나무가 균형을 얼마나 제외

지금까지 발견 된 가장 비트의 4 × 4 행렬의 곱셈,하지만 어색 이잖아 구현하고 공간을 16 비트로 줄입니다.

도움에 감사드립니다.

Answer 1

이것은 내가 작성한 것입니다 (Java로 작성). 기본 아이디어는 32 비트 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; 
    } 
}