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

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

---

두 개의 해시가 H(A)있고 H(B)이를 결합하려고 한다고 가정하십시오 . 나는 두 개의 해시를 결합하는 좋은 방법이 XOR그들에게 있다는 것을 읽었습니다 XOR( H(A), H(B) ).

내가 찾은 가장 좋은 설명은 다음 해시 함수 지침 에 간략하게 설명되어 있습니다 .

대수 분포가 거의없는 두 숫자를 XOR하면 대수 분포가 다른 수는 여전히 발생하지만 두 값에 따라 달라집니다.
...
* 결합 할 두 숫자의 각 비트에서 두 비트가 같으면 0이 출력되고 그렇지 않으면 1이 출력됩니다. 즉, 조합의 50 %에서 1이 출력됩니다. 따라서 두 개의 입력 비트가 각각 50 또는 50의 확률로 0 또는 1이면 출력 비트도 마찬가지입니다.

XOR이 OR 또는 AND 등이 아닌 해시 함수를 결합하기위한 기본 연산이어야하는 이유에 대한 직관 및 / 또는 수학을 설명 할 수 있습니까?

---

균일하게 랜덤 한 (1 비트) 입력을 가정하면 AND 함수 출력 확률 분포는 75 % 0및 25 % 1입니다. 반대로, OR은 25 % 0및 75 % 1입니다.

XOR 함수는 50 % 0및 50 % 1이므로 균일 한 확률 분포를 결합하는 데 좋습니다.

이것은 진리표를 작성하여 볼 수 있습니다.

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

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

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

운동 :이 1 비트 입력 얼마나 많은 논리적 기능 a및 b이 균일 한 출력 분포를 가지고? 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 비트 부호없는 정수)

---

In spite of its handy bit-mixing properties, XOR is not a good way to combine hashes due to its commutativity. Consider what would happen if you stored the permutations of {1, 2, …, 10} in a hash table of 10-tuples.

A much better choice is m * H(A) + H(B), where m is a large odd number.

Credit: The above combiner was a tip from Bob Jenkins.

---

Xor may be the "default" way to combine hashes but Greg Hewgill's answer also shows why it has its pitfalls: The xor of two identical hash values is zero. In real life, there are identical hashes are more common than one might have expected. You might then find that in these (not so infrequent) corner cases, the resulting combined hashes are always the same (zero). Hash collisions would be much, much more frequent than you expect.

In a contrived example, you might be combining hashed passwords of users from different websites you manage. Unfortunately, a large number of users reuse their passwords, and a surprising proportion of the resulting hashes are zero!

---

There's something I want to explicitly point out for others who find this page. AND and OR restrict output like BlueRaja - Danny Pflughoe is trying to point out, but can be better defined:

First I want to define two simple functions I'll use to explain this: Min() and Max().

Min(A, B) will return the value that is smaller between A and B, for example: Min(1, 5) returns 1.

Max(A, B) will return the value that is larger between A and B, for example: Max(1, 5) returns 5.

If you are given: C = A AND B

Then you can find that C <= Min(A, B) We know this because there is nothing you can AND with the 0 bits of A or B to make them 1s. So every zero bit stays a zero bit and every one bit has a chance to become a zero bit (and thus a smaller value).

With: C = A OR B

The opposite is true: C >= Max(A, B) With this, we see the corollary to the AND function. Any bit that is already a one cannot be ORed into being a zero, so it stays a one, but every zero bit has a chance to become a one, and thus a larger number.

This implies that the state of the input applies restrictions on the output. If you AND anything with 90, you know the output will be equal to or less than 90 regardless what the other value is.

For XOR, there is no implied restriction based on the inputs. There are special cases where you can find that if you XOR a byte with 255 than you get the inverse but any possible byte can be output from that. Every bit has a chance to change state depending on the same bit in the other operand.

---

If you XOR a random input with a biased input, the output is random. The same is not true for AND or OR. Example:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

As @Greg Hewgill mentions, even if both inputs are random, using AND or OR will result in biased output.

The reason we use XOR over something more complex is that, well, there's no need: XOR works perfectly, and it's blazingly stupid-fast.

---

Cover the left 2 columns and try to work out what the inputs are using just the output.

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

When you saw a 1-bit you should have worked out that both inputs were 1.

Now do the same for XOR

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

XOR gives away nothing about it inputs.

---

The source code for various versions of hashCode() in java.util.Arrays is a great reference for solid, general use hashing algorithms. They are easily understood and translated into other programming languages.

Roughly speaking, most multi-attribute hashCode() implementations follow this pattern:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

You can search other StackOverflow Q&As for more information about the magic behind 31, and why Java code uses it so frequently. It is imperfect, but has very good general performance characteristics.

---

XOR does not ignore some of the inputs sometimes like OR and AND.

If you take AND(X, Y) for example, and feed input X with false, then the input Y does not matter...and one probably would want the input to matter when combining hashes.

If you take XOR(X, Y) then BOTH inputs ALWAYS matter. There would be no value of X where Y does not matter. If either X or Y is changed then the output will reflect that.

참고URL : https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes