[cryptography] XOR이 해시를 결합하는 기본 방법 인 이유는 무엇입니까?

xor해싱 할 때 사용할 위험한 기본 함수입니다. andand 보다 낫지 만 or많은 것을 말하지 않습니다.

xor대칭이므로 요소의 순서가 손실됩니다. 그래서 "bad"의지 해시와 같은 결합 "dab".

xor 쌍으로 동일한 값을 0에 매핑하므로 “공통”값을 0에 매핑하지 않아야합니다.

따라서 (a,a)0에 매핑되고 0에 (b,b)매핑됩니다. 이러한 쌍은 거의 임의성이 암시하는 것보다 거의 항상 흔하기 때문에 0보다 훨씬 많은 충돌이 발생합니다.

이 두 가지 문제 xor로 인해 표면에서 절반 정도 괜찮은 해시 결합기가 만들어졌지만 추가 검사 후에는 그렇지 않습니다.

최신 하드웨어에서는 일반적으로 거의 빠른 속도로 추가 xor합니다 (아마도 더 많은 전력을 사용하여이를 끌 수 있습니다). 덧셈의 ​​진리표는 xor문제의 비트 와 유사 하지만 두 값이 모두 1 일 때 다음 비트로 비트를 보냅니다. 이는 정보가 덜 지워짐을 의미합니다.

따라서 if hash(a) + hash(b)보다 결과가 0 대신에 더 낫습니다 .hash(a) xor hash(b)a==bhash(a)<<1

이것은 대칭으로 유지됩니다. 그래서 "bad"와 "dab"같은 결과를 얻는 것은 문제가 남아있다. 적당한 비용으로이 대칭을 깨뜨릴 수 있습니다 :

hash(a)<<1 + hash(a) + hash(b)

일명 hash(a)*3 + hash(b). ( hash(a)시프트 솔루션을 사용하는 경우 한 번 계산 하고 저장하는 것이 좋습니다). 부호없는 정수에 대한 맵 은 일부 에 대해 수학적인 모듈러스이고 , 홀수 상수는 비교적 소수이기 때문에 대신에 홀수 상수 대신 3” k-비트”부호없는 정수를 자신에 매핑 합니다 .2^kk2^k

더 멋진 버전의 경우 다음을 boost::hash_combine효과적으로 검사 할 수 있습니다 .

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

여기에 우리 seed는 상수 (기본적으로 임의 0의 s와 1s입니다-특히 32 비트 고정 소수점 분수와 같은 황금 비율의 역수)를 가진 일부 버전과 xor를 추가합니다. 이 휴식은 대칭 및 수신 해시 값이 있다면 소개합니다은 일부는 “노이즈”, 즉 0으로 모든 구성 요소 해시를 상상 (가난한 – 위의 손잡이는 잘의 얼룩을 생성 1하고 0. 각 결합 후이야 내 순진 3*hash(a)+hash(b)단순히 출력 0의를 그 경우).

(C / C ++에 익숙하지 않은 사용자의 경우 a size_t는 메모리에있는 오브젝트의 크기를 설명하기에 충분히 큰 부호없는 정수 값입니다. 64 비트 시스템에서는 일반적으로 64 비트 부호없는 정수입니다. 32 비트 시스템에서 , 32 비트 부호없는 정수)

답변

00101001 XOR 00000000 = 00101001
00101001 및 00000000 = 00000000
00101001 또는 11111111 = 11111111

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0