현재 약 1,000 억 개 항목의 데이터 세트에 해시 테이블을 구현 중입니다. 대부분이 중복되어 (약 75 %) "고유 한"값 세트가 조금 더 작습니다.하나의 128 비트 해시 대 두 개의 다른 64 비트 해시 (비 암호화)?
나는 100 % 충돌을 피할 수는 없다는 것을 알고 있지만, 적어도 그럴 가능성은 희박합니다. 아이디어는 하나의 해시가 충돌하면 다른 하나가 충돌하지 않는다는 가정에서 두 개의 다른 해시 함수에 대해 테스트하는 것이 었습니다. 참조 : bloom-filter.
이제 내 질문에 - 통계적으로 두 배 크기의 단일 해시를 사용하는 것과 똑같지 않습니까? 그럼 Murmur3 64 대신 CityWash 64와 Murmur3 128을 가정 해 봅시다.
뛰어난 해시 함수 인 경우 충돌 확률은 동일해야합니다. 실제로는 별도의 해시 함수가 조금 더 나은 성능을 낼 것으로 판단됩니다.
블룸 필터는 해시 세트를 함께 BITOR하여 메모리를 절약하는 영리한 방법입니다. 이론적으로 두 개의 64 비트 해시와 128 비트 해시의 두 절반으로 동일한 작업을 수행 할 수 있습니다. 2 비트의 RAM이 충분하지 않으므로 4 개의 32 비트 해시로 분리하여 (또는 별도로 사용) 2 비트 = 2를 포함하는 블룸 필터에 오버레이하는 것이 실용적입니다. 바이트 = 1/2GB.
64 비트 해시 함수 [특별한 의미가 있기 때문에 "완벽한 해시 함수"라는 용어를 사용하지 않고] 우발적으로 충돌하는 두 항목의 확률은 2 -64입니다. 적은 수. 당신은 100G 고유 항목이 있다면
, 당신은 어떤 충돌까지 있는의 확률을 얻기 위해, 100G 2 = 10 22 약 2 73 해시 값, 또는 73 해시 비트를 필요 했어 1/2.