블룸 필터는 항목마다 여러 해시 위치의 비트를 1로 켭니다. 조회할 때 해당 비트 중 하나라도 0이면 그 항목은 확실히 들어 있지 않습니다.
모든 비트가 1이어도 다른 항목이 같은 위치를 켰을 수 있으므로 존재는 확정할 수 없습니다. 항목이 많아지면 거짓 양성이 늘 수 있지만 거짓 음성은 정상적인 삽입·조회에서는 생기지 않습니다.
언제 쓰나
큰 저장소를 조회하기 전에 없는 키를 저렴하게 걸러낼 때 씁니다.
블룸 필터
Bloom filter
여러 비트 검사로 확실한 부재와 가능한 존재를 빠르게 구분합니다.
···
<div class="v"><header><b>BLOOM FILTER</b><span id="state"></span></header><main><div class="bits" id="bits"></div><div class="query" id="query"></div></main><footer>zero bit proves absence</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .bits{height:57%;display:flex;align-items:center;justify-content:center;gap:3px}.bit{width:25px;height:30px;border:1px solid var(--line);border-radius:4px;display:grid;place-items:center;font:700 .8em ui-monospace,monospace}.query{text-align:center;color:var(--accent);font:600 .85em ui-monospace,monospace}let n=0;const base=[1,0,1,1,0,1,0,1];function draw(){const checks=n%2?[1,4,6]:[0,3,7];document.getElementById("bits").innerHTML=base.map((v,i)=>"<div class=\"bit "+(checks.includes(i)?"active":"")+"\">"+v+"</div>").join("");document.getElementById("query").textContent=n%2?"B: bit 1 = 0 → absent":"A: all bits = 1 → maybe";document.getElementById("state").textContent=n%2?"definitely absent":"possibly present";n++}draw();setInterval(draw,1300)