해시를 자르는 것이 안전합니까?

Question

약 20 억 개의 문자열에 해시를 저장하고 싶습니다. 그 목적을 위해 가능한 한 적은 저장 공간을 사용하고 싶습니다.

해시를 일련의 16 진수 (예 : md5 해시)로 반환하는 이상적인 해싱 알고리즘을 고려해보십시오. 나는 생각하기에 이것은 길이가 8 심볼 이하가되도록 해시가 필요하다는 것을 의미한다. 그러한 해시는 4+ 억 (16 * 16 * 16 * 16 * 16 * 16 * 16 * 16) 개의 고유 문자열을 해싱 할 수 있기 때문에 가능합니다.

그래서 공간을 절약하기 위해 해시를 일정 길이로 자르는 것이 안전한지 알고 싶습니다. (해시는 물론 충돌하지 않아야합니다.)

예/아니요/어쩌면 - 관련 연구에 대한 설명 또는 링크가있는 답변을 주시면 감사하겠습니다.

p.s. 8 문자 해시가 20 억 개의 문자열을 저장할 수 있는지 여부를 테스트 할 수 있습니다. 하지만 20 억 개의 해시를 20 억 개의 잘라 버린 버전과 비교해야합니다. 나에게 사소한 것처럼 보이지 않기 때문에 내가 그렇게하기 전에 더 잘 물어볼 것입니다.

Answer 1

해시는 숫자이며 16 진수 (문자)의 문자열이 아닙니다. MD5의 경우 효율적인 형태로 저장된 128 비트 또는 16 바이트입니다. 문제가 계속되는 경우에는 단어를 줄이거 나 단어를 첫 번째 비트로 바꿔서 숫자를자를 수 있습니다. 좋은 해시 알고리즘은 모든 비트에 균등하게 분배됩니다.

부록 : 당신이 해시를 처리 할 때마다

는 일반적으로, 당신은 문자열이 정말 일치하는지 확인합니다. 이렇게하면 해시를 콜 레이스 할 수 있습니다. 더 해시를 줄이면 더 많은 충돌이 발생합니다. 그러나이 단계에서 그 일이 일어나기를 계획하는 것이 좋습니다. 그것의 2 배 별개의 해시 값을 나타내는 만 할 수있는 해시 도메인의 X 값을 저장하는 것이 안전하면 충돌을 견딜 수 있는지 여부에 달려 여부

Answer 2

.

해시 함수는 실제로 난수 생성기이므로 계산 된 해시 값 20 억 개가 40 억 개의 가능한 결과에 균등하게 분산됩니다. 즉, 귀하는 Birthday Problem의 적용을받습니다.

가능한 경우 2^32 (40 억) 개의 해시 값으로 2^31 (20 억) 해시를 계산하면 동일한 해시 (충돌)를 가질 확률은 매우 높습니다 거의 100 %. (3 가지가 같을 확률도 100 %에 가깝다.)이 숫자를 기반으로 가능한 충돌 횟수를 계산하는 공식은 찾을 수 없지만 엄청난 숫자라고 생각된다. .

해시 충돌이 재난이 아닌 경우 (해시 대상을 같은 해시 키를 공유하는 개체 목록으로 전환하여 충돌을 처리하는 Java HashMap 구현에서와 같이 성능이 저하 되더라도) 그렇다면 당신은 높은 충돌 수의 확실성으로 살 수 있습니다. 그러나 고유성이 필요하다면 훨씬 더 큰 해시 도메인이 필요하거나 목적에 따라 각 레코드에 보장 된 고유 일련 ID 번호를 할당해야합니다.

마지막으로, Keccak은 원하는 출력 길이를 생성 할 수 있으므로, 긴 해시 출력을 생성하는 CPU 리소스를 나중에 만 사용하여 지출을 줄이는 것은 의미가 없습니다. Keccak 함수에 필요한 비트 수만 알려줄 수 있어야합니다.(Keccak 출력 길이의 변경은 초기 출력 비트에 영향을 미치지 않으므로 나중에 수동으로 비트 트림을 한 경우와 똑같은 결과가 나타납니다.)