효율적인 연관 비트셋 해시 찾기

Question

일련의 비트셋이 있다고 가정하십시오. b1, b2, b3, ..., bN.

연관성이있는 해시를 생성하는 데 사용할 수있는 효율적인 비트 연산자 해시 계산이 있습니까?

즉

는 권장 해시 함수에게 무엇 hash(bX, bY) 있도록 :

hash(hash(b1, b2), b3) == hash(b1, hash(b2, b3)) 

독점 또는 XOR가 수용 가능한 낮은 충돌 속도를 제공 비트 단위겠습니까?

편집 : 관련 질문이 있습니다 (here).

Answer 1

XOR은 연관 적이지만 또한 교환 가능합니다. 그것은 당신이 필요 이상의 것입니다. 그러나 저는 실용적인 순전히 연관성있는 변형을 생각하지 않습니다. 행렬 곱셈이 마음에 들지만 이진 해시와 함께 사용하는 방법을 잘 모르겠습니다.

덧셈은 또한 연관되어 있으므로 해시를 결합 할 수 있습니다. 하나는 합쳐진 것과 다른 하나는 XOR과 결합 된 두 가지 해시를 유지합니다. 충돌은 효과적인 충돌이되기 위해서는 두 가지 모두에 영향을 주어야합니다. 훨씬 더 가능성이 높습니다.

단점은 hash(a, b) == hash(b, a) (이것은 commutativity)입니다. 해당 속성을 제거하는 방법을 모릅니다.