해시 기능 결합 - 충돌 위험이 크게 감소 했습니까?

Question

해시 함수를 결합하여 충돌 확률을 낮추는 것과 관련하여 실질적인 이점이 있는지 아는 사람이 있습니까? 특히 32 비트 해싱, 즉 Adler32와 CRC32의 결합에 관해서는이 사실을 알아야합니다. 기본적으로 adler32 (crc32 (data))는 crc32 (data)보다 작은 충돌 확률을 산출합니까? 마지막 코멘트 here은 결합에 유리한 몇 가지 테스트 결과를 제공하지만 소스는 언급되지 않았습니다. 내 목적에 따라 충돌은 중요하지 않습니다 (즉, 작업에 보안이 포함되지 않음). 가능하면 가능하면 가능성을 최소화하고 싶습니다. 추신 : 나는 해싱의 멋진 세계에서 시작하여 많은 독서를하고있다. 미안하지만 어리석은 질문을하면 적절한 "해시 방언 (hash dialect)"을 아직 습득하지 못했을 것입니다. 아마 이것에 관한 Google 검색도 제대로 이루어지지 않았을 것입니다. 감사합니다. .

Answer 1

이런 식으로 시리즈를 결합하는 것은 의미가 없습니다. 하나의 32 비트 공간을 다른 32 비트 공간으로 해싱하려고합니다.

첫 번째 단계에서 crc32 충돌의 경우 최종 결과는 여전히 충돌입니다. 그런 다음 adler32 단계의 잠재적 인 충돌을 추가합니다. 그래서 더 나아질 수없고, 단지 같거나 더 나쁠 수 있습니다. 충돌을 줄이기 위해

, 당신은 64 비트 출력 공간 만들 독립적으로 두 개의 해시를 사용하여 같은 것을 시도 할 수 있습니다 :

adler32 (데이터) < < 32 | crc32 (데이터)

그렇게 할 때 상당한 이점이 있는지 여부는 확실하지 않습니다. 당신이 언급 원래 댓글이 독립적으로 해시를 저장 한 것을

참고 :

당신이 거짓 양성의 일부 기회가 될 것 가 사용하든 알고리즘

. 그러나 알고리즘을 두 가지 다른 해시 알고리즘을 사용하여 이러한 기회를 상당히 줄일 수 있습니다 ( ). 을 계산하고 각 URL에 대해 CRC32와 Alder32를 모두 저장하는 경우 주어진 URL 쌍에 대해 해시 모두에 대한 동시 충돌 확률은 크게 입니다.

물론 이것은 원래 문제의 일부인 많은 정보로 두 번 저장하는 것을 의미합니다. 그러나, 거의 동일한 검색 성능을 제공하는 반면 (그래서 10킬로바이트 또는) 최소 메모리를 필요 데이터되도록 해시의 두 세트를 저장하는 방법이 인 펄의 해쉬 값 (15 microsecs은/조회 5 microsecs 비교) .