해시 - 충돌 : 여러 해싱으로 성장 가능성

Question

개체를 여러 번 해시 할 때 해시 충돌이 발생할 가능성이 있습니까?

의미는 hash(hash(object))에 대한 충돌 가능성이 hash(object)보다 높음을 의미합니다.

Answer 1

정확한 의미에 따라 다릅니다.

다시 해싱으로 인해 해시가 변경된 경우 예, 그렇지 않으면 아니요.

개체가 변경되지 않고 다시 해시하면 동일한 해시를 유지합니다. 예를 들어 문자열 teststring의 md5 해시는 항상 D67C5CBF5B01C9F91932E3B8DEF5E5F8입니다.

그러나 개체가 변경되어 그 때문에 다시 해시하면 새 해시를 받게됩니다.

이제 변경된 개체를 다시 칠하면 충돌 가능성이 높아질 수 있습니다.

예를 들어 정수 값 하나와이 값을 취하는 매우 간단한 해싱 알고리즘을 포함하는 매우 간단한 개체가 있고이 개체에 modulo 20이 있습니다. 이 예제에서는 의도적으로 잘못된 해싱 알고리즘입니다.

이제 임의의 숫자를 포함하는 두 개의 개체가 있다고 가정 해 보겠습니다. 이 두 값에 대한 해시 충돌 가능성은 해시 알고리즘에 20 개의 버킷이 있으므로 1/20입니다.

다시 충돌하면 다시 1/20 충돌 가능성이 나타나거나 충돌 가능성이 19/20입니다.

따라서 n 개 심자가 충돌하지 않을 확률은 (19/20)^(n+1)입니다. 그래서 첫 번째 rehash 이후 (원래의 값을 가지며 변경된 값 중 하나를 다시 한 번 재연 해), 충돌이없는 90.25% 기회가 있습니다. 두 번째 재연 후, 충돌이없는 85.76% 가능성이 있습니다. 100 번 재촉하면 0.59%의 충돌 만 발생합니다.

각 rehash 전에 값이 새 값으로 변경된다는 점에 따라 달라집니다.

• 해싱 알고리즘은 당신에게 당신은 다른 값
을의 무한대로 해싱 알고리즘을 공급할 수
• 버킷의 제한된 양 (= 다른 가능한 해시를) 제공 :

  것을 증명하는 또 다른 방법은 이것이다

• 각 값을 버킷에 매핑해야합니다.
• 제한된 양의 버킷에 매핑 된 값의 무한 값이있는 경우 충돌이있을 수 있습니다.