블룸 필터로 해쉬 함수 사용하기

Question

블룸 필터는 해시 함수 (또는 다수)를 사용하여 입력 문자열 X가 주어진 경우 0과 m 사이의 값을 생성합니다.이 질문에 해시 함수를 사용하여 MD5 해시는 일반적으로 32 자 길이의 hex 문자열로 표현됩니다. MD5 해시 알고리즘을 사용하여 0과 m 사이의 값을 생성하는 방법은 무엇입니까? 여기서 m은 지정할 수 있습니까? 저는 Java를 사용하고 있습니다. 따라서 MessageDigest가 제공하는 MessageDigest 기능을 사용하여 예제를 작성하는 것이 좋을 것입니다.

감사

Answer 1

먼저 해시 출력을 부호없는 정수로 변환 한 다음 모듈 길이를 m으로 줄여야합니다. 이것은 다음과 같습니다

MessageDigest md = MessageDigest.getInstance("MD5"); 
// hash data... 
byte[] hashValue = md.digest(); 
BigInteger n = new BigInteger(1, hashValue); 
n = n.mod(m); 
// at that point, n has a value between 0 and m-1 (inclusive) 

내가 m이 BigInteger 예라고 가정했다. 필요한 경우 BigInteger.valueOf()을 사용하십시오. 마찬가지로 n.intValue() 또는 n.longValue()을 사용하여 n의 값을 Java의 기본 유형 중 하나로 가져옵니다.

모듈러 감소

다소 편향된이지만 m 실질적 미만 2^128 경우 바이어스는 매우 작다.

Answer 2

가장 간단한 방법은 아마 하나의 진수를 (바이트 순서로) 해시 출력을 변환하는 모듈로 m을하는 것입니다.