Cuckoo 필터 : 왜 정확히 7 카운트입니까? (엔티티 삽입의 "제한된 수"와 같습니다.)

Question

저는 지난 며칠 동안 뻐꾸기 필터를 사용하여 머리를 감싸 주려고했습니다. 블룸 필터보다 여러면에서 장점이 있다는 것을 알고 있으며 일반적으로 사용하는 것이 좋습니다 (일반적으로 사용할 수있는 경우).

내가 찾고있는 응용 프로그램에 대한 계산이 필요합니다. 어디서나 정보를 찾을 수없는 이유는 뻐꾸기 필터에 "제한된 계산"이 정확히 존재하는 이유입니다. (나는 한계가 7이라고 들었지만)

이것은 이론적 인 한계입니까?

Answer 1

뻐꾸기 필터는 하나의 키를 여러 개 복사 할 수 있습니다. 모든 항목은 동일한 해시 값을 가지므로 두 개의 가능한 버킷 중 하나의 슬롯에 모두 삽입됩니다. 버킷의 크기가 4 인 경우 총 슬롯은 8 개입니다.

일반적으로 가능한 슬롯이 꽉 찼을 때 키를 추가하려고하면 문제가되지 않습니다. 슬롯에있는 키 중 하나는 쫓겨납니다. 그러나 모든 키가 같을 때 이동 가능한 오버플로 또는 백업 위치가 없습니다.