Bloom Filters for Fast Negative Lookups

Write a C program that implements a Bloom filter for SSTable negative lookups.

Requirements:

• Define FILTER_SIZE as 64 bits (uint64_t for simplicity)
• Implement hash1(key) = key * 31 % 64, hash2(key) = key * 17 % 64, hash3(key) = key * 7 % 64
• Implement bloom_add(filter, key): set bits at hash1, hash2, hash3
• Implement bloom_check(filter, key): return 1 if all three bits are set, 0 otherwise
• Create a filter and add these keys: 10, 20, 30, 40, 50
• Test lookups for:
  • Present keys: 10, 30, 50 (should all return 1)
  • Absent keys: 15, 25, 35, 45, 99 (should mostly return 0, but may have false positives)
• Print the filter bit pattern as a 64-character binary string
• Count and print the number of false positives in the test
• Calculate the theoretical false positive rate for n=5, m=64, k=3 using the formula p = (1 - e^(-kn/m))^k
• Explain why Bloom filters have no false negatives