C의 블룸 필터에 대한 범용 해시 함수 구현

Question

블룸 필터를 사용하여 시뮬레이션 교차 집합 근사화를 시뮬레이션합니다. 필터에 값을 해시하는 간단한 해시 함수를 많이 시도했습니다. 하지만 충돌을 피하는 데는 좋지 않습니다. 그래서 누군가는 보편적 인 해시 함수를 제안했습니다. 하지만 어떻게 작동하는지 모르겠다. 내 프로그램은 해시 함수에 키만 전달하고 해시 함수는 해시를 반환하도록 설계되었습니다. 누구든지 코드를 도와 줄 수 있습니까? 감사합니다.

Answer 1

블룸 필터와 함께 사용할 때 해시 함수 충돌에 대해 걱정하지 마십시오. 이 경우에는 충돌을 처리 할 필요가 없습니다. 그냥 k를 얻으려면 요소를 삽입 할 때 m 비트 배열에 k 비트를 설정하는 함수가 있어야합니다. 쿼리 할 때 다시 모든 k 해시 함수를 사용하여 모든 k 비트를 검사합니다. 그 중 하나가 설정되지 않은 경우 검색은 거짓입니다. 모든 것이 정해지면, 결론을 내릴 수 없습니다 (거짓 결과). 위키에서 명확하게 설명되어 있습니다 :

http://en.wikipedia.org/wiki/Bloom_filter