Bloom Filter (บลูมฟิลเตอร์) ในโครงสร้างข้อมูล

Bloom Filter คืออะไร?

Bloom Filter = Data Structure สำหรับตรวจสอบ Element Presence ใน Set แบบ รวดเร็วและประหยัดหน่วยความจำ

เป็น Probabilistic Data Structure: บอกว่า Element "น่าจะอยู่" หรือ "แน่ไม่อยู่" ใน Set

โครงสร้างพื้นฐาน: Bit Vector

แต่ละ Cell = 1 Bit, ตัวเลข = Index/Position

การทำงาน

Insert (Add Element)

1. Compute Hash Values ของ Element (หลาย Hash Functions)
2. Set Bits ที่ Positions ตรงกับ Hash Values = 1

Query (Check Element)

1. Compute Hash Values เดียวกัน
2. Check Bits ที่ Positions นั้น → All 1s? → "Possibly in Set"
   Any 0? → "Definitely NOT in Set"

Important Note

Hash Value ไม่ได้ Store ตรงใน Filter แต่ละ Hash Function แค่บอกว่า Bit ไหน Set/Check

Example: 1 Hash Function → Check 1 Bit Only → High False Positive Rate

Properties

• No False Negatives: ถ้าอยู่จริง → ต้อง Return "Possibly in Set"
• False Positives Possible: ไม่อยู่แต่ Return "Possibly in Set" (Hash Collisions)
• Space Efficient: m Bits สำหรับ n Elements (m ≪ n × Element Size)
• Time: O(k) สำหรับ Insert/Query (k = Hash Functions)

Use Cases

• Database: Avoid Disk Lookups สำหรับ Non-existent Keys
• Web Caching: Check URL ใน Cache ก่อน Fetch
• Spell Checkers: Fast Dictionary Lookup
• Network: Packet Routing, DDoS Detection
• Distributed Systems: Membership Queries