Bloom Filter: Complete Implementation Guide

Introduction and Core Concepts

A bloom filter is a space-efficient probabilistic data structure that answers a deceptively simple question: "Is this element possibly in the set, or definitely not in the set?" Conceived by Burton Howard Bloom in 1970, the bloom filter has become a cornerstone of modern large-scale systems where memory efficiency and query speed outweigh the need for absolute certainty. Unlike a traditional hash set that stores every element explicitly, a bloom filter represents set membership using a compact bit array and a handful of hash functions, trading a small, controllable rate of false positives for dramatic savings in space.

The core promise of a bloom filter is asymmetric: it will never produce a false negative. If the filter says an element is not present, you can trust that answer completely. If it says an element is present, that answer is probabilistic — the element is either truly present, or the filter has been tricked by overlapping hash collisions into a false positive. This one-sided error model makes bloom filters ideal as a fast, memory-light pre-filter in front of a more expensive, authoritative data store. By quickly ruling out the vast majority of negative queries, a bloom filter can prevent costly disk lookups, network round trips, or database scans.

Understanding when to use a bloom filter requires understanding this trade-off. You would not use a bloom filter to store passwords or financial transactions where a false positive is unacceptable. You would use it when the cost of a false positive is low compared to the cost of always checking the underlying store. For example, checking if a username is already taken, determining if a web page has been crawled, or deciding whether to query a remote cache are all perfect fits. The bloom filter excels when the data set is massive, memory is constrained, and most queries are expected to be negative.

Why Bloom Filters Matter Today

In the era of big data, distributed databases, and content delivery networks, the sheer scale of data makes traditional exact data structures impractical. Storing billions of URLs, user IDs, or genomic sequences in a hash table would require gigabytes or terabytes of RAM. A bloom filter can represent the same set in a fraction of the space — often 10x smaller — with a false positive rate below 1%. This efficiency is why bloom filters are embedded deep inside systems like Apache Cassandra, Google Chrome, Bitcoin, and Cloudflare.

The key insight is that a bloom filter does not store the data itself. It stores a fingerprint of the data derived from hashing. This makes it not only compact but also privacy-friendly in certain contexts, as the original elements cannot be reconstructed from the bit array alone. For any engineer building high-throughput systems, mastering the bloom filter is essential for designing scalable, resource-aware architectures.

How It Works

A bloom filter consists of two fundamental components: a bit array of m bits, initially all set to 0, and k distinct hash functions, each of which maps an element to one of the m array positions uniformly at random. The choice of m and k is not arbitrary; it is mathematically derived from the expected number of elements n and the desired false positive probability p.

To add an element to the bloom filter, the element is fed to each of the k hash functions to obtain k array positions. The bits at all of these positions are then set to 1. Note that a bit may be set to 1 multiple times by different elements or different hash functions — this overlapping is intentional and is the source of both space efficiency and false positives. No matter how many times a bit is set, it remains 1.

To query for an element, the same k hash functions are applied to the element to get k positions. If any of the bits at these positions is 0, the element is definitely not in the set. The logic is simple: if the element had been added, all of those bits would have been set to 1. If all k bits are 1, the filter reports that the element is possibly in the set. It might be a true member, or it might be that all k bits were set to 1 by a combination of other inserted elements, causing a false positive.

The Mathematics Behind False Positives

The false positive rate is not magic; it is predictable. After inserting n elements into a filter of size m with k hash functions, the probability that a specific bit is still 0 is approximately (1 - 1/m)^(k*n), which converges to e^(-k*n/m). Therefore, the probability that a bit is 1 is 1 - e^(-k*n/m). For a false positive to occur, all k bits probed during a query must be 1, so the false positive probability p is approximately (1 - e^(-k*n/m))^k.

This formula reveals the optimal relationship between parameters. For a given m and n, the value of k that minimizes the false positive rate is k = (m/n) * ln(2). This optimal k corresponds to a filter where about half the bits are set to 0 and half to 1, maximizing entropy. In practice, you typically choose your desired n and p first, then calculate the required size m = -(n * ln(p)) / (ln(2)^2) and the optimal k from that.

For example, to store 1,000,000 elements with a 1% false positive rate (p=0.01), you need m ≈ 9,585,059 bits (about 1.14 MB) and k ≈ 7 hash functions. A Python set storing 1 million strings would easily require 50-100 MB. This 50x space reduction is the bloom filter's superpower.

Implementation

Implementing a bloom filter from scratch in Python is an excellent exercise for understanding its internals. While production systems often use highly optimized libraries like pybloom-live or RedisBloom, a custom implementation clarifies hash function management, bit array operations, and parameter tuning. We will use Python's built-in hashlib for stable hashing and the bitarray concept simulated with a Python integer or bytearray for simplicity.

A robust implementation avoids the common pitfall of needing k independent hash functions. Instead, we can simulate k hashes using the double hashing technique: h_i(x) = h1(x) + i * h2(x) mod m. This requires only two base hash functions (like MurmurHash or SHA256) to generate k effective hashes, which is both efficient and well-distributed. We will also include methods to calculate optimal parameters automatically.

import math
import hashlib

class BloomFilter:
    """
    Complete Bloom Filter implementation with optimal parameter calculation
    and double-hashing technique.
    """
    def __init__(self, expected_items, false_positive_rate=0.01):
        # Calculate optimal size (m) and number of hash functions (k)
        self.n = expected_items
        self.p = false_positive_rate
        self.m = self._optimal_size(expected_items, false_positive_rate)
        self.k = self._optimal_hash_count(self.m, expected_items)
        
        # Initialize bit array with all zeros
        self.bit_array = bytearray((self.m + 7) // 8)
        self.items_inserted = 0

    def _optimal_size(self, n, p):
        # m = -(n * ln(p)) / (ln(2)^2)
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(math.ceil(m))

    def _optimal_hash_count(self, m, n):
        # k = (m / n) * ln(2)
        k = (m / n) * math.log(2)
        return int(math.ceil(k))

    def _hashes(self, item):
        # Generate k hashes using double hashing
        # Use hashlib for deterministic hashing
        item_bytes = str(item).encode('utf-8')
        hash1 = int(hashlib.md5(item_bytes).hexdigest(), 16)
        hash2 = int(hashlib.sha256(item_bytes).hexdigest(), 16)
        
        for i in range(self.k):
            # h_i = (h1 + i * h2) % m
            yield (hash1 + i * hash2) % self.m

    def _set_bit(self, index):
        byte_index = index // 8
        bit_index = index % 8
        self.bit_array[byte_index] |= (1 << bit_index)

    def _get_bit(self, index):
        byte_index = index // 8
        bit_index = index % 8
        return (self.bit_array[byte_index] >> bit_index) & 1

    def add(self, item):
        """Add an item to the bloom filter."""
        for index in self._hashes(item):
            self._set_bit(index)
        self.items_inserted += 1

    def __contains__(self, item):
        """Check membership: True means possibly present, False means definitely not."""
        return all(self._get_bit(index) == 1 for index in self._hashes(item))

    def estimated_false_positive_rate(self):
        # p = (1 - e^(-k*n/m))^k
        return (1 - math.exp(-self.k * self.items_inserted / self.m)) ** self.k

import mmh3  # MurmurHash3 - fast non-cryptographic hash for production
import bitarray

class OptimizedBloomFilter:
    """
    Production-oriented Bloom Filter using MurmurHash and bitarray library.
    Demonstrates handling of large scale and serialization.
    """
    def __init__(self, capacity, error_rate=0.01):
        if not (0 < error_rate < 1):
            raise ValueError("error_rate must be between 0 and 1")
        if capacity <= 0:
            raise ValueError("capacity must be > 0")
            
        self.capacity = capacity
        self.error_rate = error_rate
        self.size = self._calculate_size(capacity, error_rate)
        self.hash_count = self._calculate_hash_count(self.size, capacity)
        self.bit_array = bitarray.bitarray(self.size)
        self.bit_array.setall(0)
        self.count = 0

    def _calculate_size(self, n, p):
        return int(-n * math.log(p) / (math.log(2) ** 2))

    def _calculate_hash_count(self, m, n):
        return max(1, int(round((m / n) * math.log(2))))

    def add(self, item):
        if self.count >= self.capacity:
            print("Warning: Bloom filter at capacity, false positive rate will increase")
        for i in range(self.hash_count):
            # mmh3.hash returns signed int, make it positive
            digest = mmh3.hash(str(item), i) % self.size
            self.bit_array[digest] = 1
        self.count += 1

    def lookup(self, item):
        """Return True if item possibly exists, False if definitely not."""
        for i in range(self.hash_count):
            digest = mmh3.hash(str(item), i) % self.size
            if self.bit_array[digest] == 0:
                return False
        return True

    def get_stats(self):
        bits_per_item = self.size / self.capacity
        fill_ratio = self.bit_array.count(1) / self.size
        return {
            "size_bits": self.size,
            "hash_functions": self.hash_count,
            "bits_per_item": round(bits_per_item, 2),
            "fill_ratio": round(fill_ratio, 3)
        }

# Example: Using the Bloom Filter and measuring false positives
def demonstrate_bloom_filter():
    # Create filter for 10000 items with 1% error rate
    bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)
    print(f"Created Bloom Filter: m={bf.m} bits, k={bf.k} hashes")

    # Insert 5000 known items
    known_items = [f"user_{i}@example.com" for i in range(5000)]
    for item in known_items:
        bf.add(item)

    # Test true positives (should all be found)
    true_positives = sum(1 for item in known_items if item in bf)
    print(f"True positives: {true_positives} / {len(known_items)}")

    # Test false positives with unseen items
    unseen_items = [f"unknown_{i}@example.com" for i in range(5000)]
    false_positives = sum(1 for item in unseen_items if item in bf)
    measured_rate = false_positives / len(unseen_items)
    print(f"False positives: {false_positives} / {len(unseen_items)}")
    print(f"Measured rate: {measured_rate:.4f}, Estimated: {bf.estimated_false_positive_rate():.4f}")

    # Demonstrate definitely-not case
    print(f"'definitely_not_present' in filter? {('definitely_not_present' in bf)}")

# demonstrate_bloom_filter()

# Counting Bloom Filter - variant that supports deletion
class CountingBloomFilter:
    """
    Counting Bloom Filter replaces bits with counters to allow deletions.
    Trade-off: uses 3-4x more space per counter (typically 4 bits per counter).
    """
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        # Use small integers as counters instead of bits
        self.counters = [0] * size

    def _hashes(self, item):
        h1 = hash(str(item) + "salt1") % self.size
        h2 = hash(str(item) + "salt2") % self.size
        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size

    def add(self, item):
        for idx in self._hashes(item):
            self.counters[idx] += 1
            # Prevent overflow if using 4-bit counters (max 15)
            if self.counters[idx] > 15:
                self.counters[idx] = 15

    def remove(self, item):
        # Only remove if item is probably present
        if item not in self:
            return False
        for idx in self._hashes(item):
            if self.counters[idx] > 0:
                self.counters[idx] -= 1
        return True

    def __contains__(self, item):
        return all(self.counters[idx] > 0 for idx in self._hashes(item))

    def approximate_count(self, item):
        # Return minimum counter value as approximate multiplicity
        return min(self.counters[idx] for idx in self._hashes(item))

Step-by-Step Example

Let us walk through a concrete, small-scale example to make the abstract mechanism tangible. Imagine we create a bloom filter with a bit array of size m = 10 (positions 0 through 9) and k = 3 hash functions. The array starts as [0,0,0,0,0,0,0,0,0,0]. We want to insert two elements: "apple" and "banana".

Assume our three hash functions produce the following outputs. For "apple": h1("apple") = 1, h2("apple") = 4, h3("apple") = 7. For "banana": h1("banana") = 3, h2("banana") = 4, h3("banana") = 9. Notice that both elements collide at position 4, which is expected and handled gracefully.

Step 1: Insert "apple". We set bits at positions 1, 4, and 7 to 1. The array becomes [0,1,0,0,1,0,0,1,0,0]. Step 2: Insert "banana". We set bits at positions 3, 4, and 9 to 1. Position 4 is already 1, so it stays 1. The final array is [0,1,0,1,1,0,0,1,0,1]. We have inserted two elements using only 5 bits set to 1.

Query Walkthrough

Now we query for three items: "apple" (a member), "cherry" (not a member, not a false positive), and "mango" (not a member, but causes a false positive in this tiny example).

Query "apple": We compute its hashes (1,4,7) and check those positions. All three are 1, so the filter correctly returns "possibly present" — a true positive.

Query "cherry": Suppose h("cherry") = (2,4,8). We check positions 2, 4, 8. Position 2 is 0 and position 8 is 0. Since at least one bit is 0, the filter correctly returns "definitely not present" — a true negative.

Query "mango": Suppose h("mango") = (1,3,9). We check positions 1, 3, 9. All three bits are 1, even though "mango" was never inserted. The bits were set by "apple" and "banana" together. The filter incorrectly returns "possibly present" — this is a false positive. In a real filter with m=10000, this would be rare, but with m=10 it is common, illustrating why sizing matters.

This example highlights two critical properties. First, deletion is not straightforward. If we try to delete "apple" by clearing bits 1,4,7 back to 0, we would also clear bit 4 which is shared with "banana", causing a subsequent query for "banana" to incorrectly return false negative. Standard bloom filters do not support deletion for this reason; counting variants are needed instead.

Complexity Analysis

The performance profile of a bloom filter is one of its most attractive features: all operations run in constant time with respect to the number of elements stored, and the time is determined solely by the number of hash functions k, which is a small constant (typically 3 to 10). This makes bloom filters exceptionally predictable and scalable.

Insertion requires computing k hashes and setting k bits. Querying requires computing the same k hashes and checking k bits. Both are O(k) time, which is effectively O(1) since k does not grow with n. Unlike hash tables that can degrade due to collisions and resizing, a bloom filter's performance remains flat even when heavily loaded, though its false positive rate degrades.

Space complexity is O(m), where m is the number of bits in the array. As derived earlier, m = -n ln(p) / (ln 2)^2. This means space grows linearly with the number of elements n, but with a very small constant factor determined by the desired error rate. For p=1%, that constant is about 9.6 bits per element. For p=0.1%, it is about 14.4 bits per element. Compare this to storing a 64-bit hash or a string, which might take 64 to 500+ bits per element.

Understanding the Trade-offs

There is no worst-case degradation in time complexity for a bloom filter — every query is O(k) regardless of fill level. However, there is a degradation in accuracy. As more elements are inserted beyond the designed capacity n, the bit array becomes saturated with 1s, and the false positive rate climbs rapidly toward 1. A filter designed for 1 million items that is forced to hold 2 million items may see its false positive rate jump from 1% to over 30%, making it useless as a filter.

Deletion is not supported in a standard bloom filter, so its time complexity is not applicable. Counting bloom filters support deletion in O(k) time by decrementing counters, but at the cost of 3-4x more space. This highlights the fundamental design principle: bloom filters achieve their efficiency by being append-only and probabilistic.

Variations and Optimizations

The classic bloom filter is just the beginning. Researchers have developed numerous variants that address its limitations — lack of deletion, inability to scale, poor cache locality, and vulnerability to adversarial inputs — while preserving its core advantages. Understanding these variants helps you choose the right tool for production constraints.

The Counting Bloom Filter is the most direct extension for supporting deletions. Instead of a bit array, it uses an array of small counters (typically 4 bits each). Adding an element increments the k counters; removing decrements them. An element is considered present if all its counters are > 0. The downside is increased space and the risk of counter overflow, though 4-bit counters overflow only after 15 insertions to the same position, which is rare with proper sizing.

Scalable Bloom Filters solve the problem of not knowing n in advance. A standard filter must be sized upfront; if you exceed capacity, false positives explode. A scalable filter starts with a small filter and adds new, larger filters as needed, each with a progressively tighter error rate. Querying checks all sub-filters. This provides dynamic growth at the cost of slightly higher query time (O(log n) filters) and more complex implementation, but it is ideal for unbounded streams like log processing.

Modern High-Performance Variants

Blocked Bloom Filters and Cuckoo Filters address CPU cache performance. A standard bloom filter's k hashes scatter across the entire bit array, causing up to k cache misses per query. A blocked filter divides the array into cache-line-sized blocks (e.g., 512 bits) and ensures all k hashes for an element fall within a single block chosen by one hash. This reduces cache misses to one, dramatically speeding up queries on modern hardware.

Cuckoo Filters, introduced in 2014, have emerged as a compelling alternative. They store fingerprints of elements in a cuckoo hash table, supporting deletion, counting, and bounded false positive rates with better space efficiency than bloom filters for low error rates (< 3%). They also support dynamic resizing. However, they are more complex to implement and can fail to insert when the table becomes too full, requiring a rebuild.

Other notable optimizations include Compressed Bloom Filters, which optimize for transmission size over memory by using a sparser filter and then compressing it for network transfer, and Stable Bloom Filters for streaming data where old elements gradually decay to make room for new ones. For most web-scale applications, a partitioned or blocked bloom filter with MurmurHash or xxHash provides the best balance of speed, simplicity, and efficiency.

Real-World Applications

Bloom filters are not academic curiosities; they are infrastructure. Their ability to cheaply avoid expensive operations makes them ubiquitous in systems where I/O is the bottleneck. The pattern is always the same: use a small, fast bloom filter in RAM to guard a large, slow store on disk or over the network.

In databases and storage engines, bloom filters are used to avoid unnecessary disk seeks. Apache Cassandra, HBase, and RocksDB maintain a bloom filter per SSTable (Sorted String Table) on disk. Before performing a disk read to find a key, the system checks the filter. If the filter says "definitely not present," the disk I/O is skipped entirely. Since most queries are for non-existent keys or keys in only one of many SSTables, this saves enormous I/O. LevelDB and Google's Bigtable pioneered this technique.

In web browsers and security, Google Chrome once used a bloom filter to check URLs against a list of malicious sites. Instead of sending every URL you visit to Google for checking (a privacy issue), Chrome downloads a compressed bloom filter of malicious URLs and checks locally. Only if the filter returns "possibly malicious" does Chrome make a full network request to verify. This preserves privacy and reduces latency.

Content delivery networks and caches use bloom filters for cache digests. Squid and other web proxies exchange bloom filters summarizing their cached content rather than full lists of URLs. A proxy can quickly check a peer's filter to decide whether to forward a request, reducing inter-cache communication by orders of magnitude.

Comparison with Alternatives

Choosing a bloom filter is not automatic; it depends on your requirements for accuracy, deletion, memory, and query semantics. Several alternative data structures solve similar membership or frequency problems with different trade-offs. Understanding these alternatives prevents misapplying bloom filters where an exact structure or a different probabilistic structure would be better.

A standard Hash Set (or Python set, Java HashSet) provides exact membership with no false positives, supports deletion, and can iterate over elements. Its cost is high memory usage — storing pointers, objects, and hash table overhead — and it cannot be easily serialized as a compact digest for network exchange. Use a hash set when accuracy is non-negotiable and the data fits comfortably in memory.

Cuckoo Filters are the closest modern competitor. They offer similar space efficiency, support deletion natively, have lower false positive rates at low capacities, and provide better locality. Their weakness is that insertion can fail when load factor is high, and they are more complex to implement correctly. For new systems needing deletion, cuckoo filters are often preferred over counting bloom filters.

HyperLogLog and Count-Min Sketch solve different problems that are sometimes confused with bloom filters. HyperLogLog estimates the cardinality (number of distinct elements) of a set, not membership. Count-Min Sketch estimates the frequency of elements in a stream. Neither answers "is X in the set?" Use them for analytics, not for membership filtering.

In short, use a bloom filter when you need a compact, fast, read-heavy membership test and can tolerate a small false positive rate. If you need deletion or iteration, consider a cuckoo filter or hash set. If you need to count frequencies, use a Count-Min Sketch. The decision matrix should always weigh the cost of a false positive against the memory saved.

Common Mistakes and Best Practices

Despite their conceptual simplicity, bloom filters are easy to misuse in ways that silently degrade performance or correctness. Avoiding these pitfalls requires careful attention to sizing, hashing, and operational semantics.

Mistake 1: Undersizing the filter. The most common error is creating a filter for an underestimated n. A filter sized for 100,000 items that actually receives 500,000 items will have a false positive rate far above the designed 1%, potentially exceeding 50%. Always size for the maximum expected cardinality plus a safety margin (e.g., 20-30%), or use a scalable bloom filter if the maximum is unknown. Monitor the fill ratio; if more than 50% of bits are set, it is time to rebuild a larger filter.

Mistake 2: Using poor hash functions. Using Python's built-in hash() is dangerous because it is randomized per process (hash randomization for security) and has poor distribution for bloom filter purposes. Similarly, using cryptographic hashes like SHA256 for every one of k probes is unnecessarily slow. The best practice is to use a fast, non-cryptographic hash like MurmurHash3, xxHash, or FNV, and derive k hashes via double hashing. Ensure hashes are independent and uniformly distributed.

Mistake 3: Attempting to delete from a standard filter. Clearing bits to delete an element introduces false negatives, violating the bloom filter's core guarantee. If your workload requires deletions, do not hack a standard filter — use a counting bloom filter or cuckoo filter from the start. Alternatively, use a time-partitioned approach where you periodically rebuild the filter from the authoritative store.

Best Practices for Production

Always calculate optimal m and k from your requirements rather than guessing. Use the formulas m = -n ln(p) / (ln2)^2 and k = (m/n) ln2. Many libraries do this for you if you provide capacity and error rate. Test your false positive rate empirically with a holdout set of unseen items before deploying.

Consider serialization and persistence. A bloom filter's bit array is trivially serializable to disk or over the network. Precompute filters offline for static sets (like a list of banned passwords) and load them at startup. For distributed systems, ensure all nodes use identical hash functions and parameters so filters are comparable.

Do not use a bloom filter as a primary data store. It is a lossy index, not a database. Always have a fallback authoritative store to verify positive results. The pattern is: if item in bloom_filter: check_database(item) else return not_found. This two-tier architecture is where bloom filters deliver their value. Finally, document the false positive rate in your system design so downstream engineers understand the probabilistic nature of the check.

Interview Questions

Bloom filters are a favorite topic in system design and algorithms interviews because they test understanding of hashing, probability, and space-time trade-offs. Here are common questions and how to approach them.

1. How would you design a system to check if a username is already taken among 1 billion users with minimal memory?

Answer: A hash set for 1 billion usernames would require tens of gigabytes of RAM. Instead, use a bloom filter. For 1 billion users with a 1% false positive rate, we need about 1.14 GB (9.6 bits per element), which fits in RAM. When a new user requests a username, check the bloom filter. If it says "definitely not present," the name is available. If it says "possibly present," do a single database query to confirm. Since most requested usernames are not taken, the filter avoids 99% of database hits. Mention the need to rebuild the filter periodically as users are added, or use a scalable filter.

2. Why does a bloom filter never have false negatives but can have false positives? Can you make a bloom filter with no false positives?

Answer: No false negatives because bits are only ever set from 0 to 1, never cleared. If an element was inserted, all its k bits are guaranteed to be 1, so a query will always find them. False positives occur because bits are shared among elements; an unseen element's k positions may have been set by other elements by coincidence. You can achieve zero false positives only by making the filter exact, which requires m to be large enough to avoid any collisions — essentially turning it into a hash set or bitset sized for the universe of possible elements, losing all space benefits. The false positive rate can be made arbitrarily small by increasing m, but never zero without infinite space.

3. How do you choose the number of hash functions k? What happens if you use too many or too few?

Answer: The optimal k is (m/n) ln2, balancing the fill ratio. If k is too small, you do not use enough bits per element, and false positives rise because fewer bits need to collide. If k is too large, you set too many bits per insertion, filling the array quickly and also increasing false positives, plus you pay more CPU time per operation. The optimum occurs when the filter is half full. For example, with m/n=10 bits per element, optimal k is about 7. Using k=2 or k=20 would both be worse than k=7.

4. How would you support deletion in a bloom filter? What are the trade-offs?

Answer: Standard bloom filters cannot support deletion without risking false negatives. The classic solution is a Counting Bloom Filter, which replaces each bit with a small counter (e.g., 4 bits). Insertion increments counters, deletion decrements them. Trade-offs: 4x space overhead, risk of counter overflow (mitigated by capping at 15), and still no protection against deleting an element that was never inserted (which would decrement counters incorrectly). Modern alternatives like Cuckoo Filters support deletion more efficiently with similar space and are often preferred in interviews as the advanced answer.

5. Estimate the memory needed for a bloom filter to store 10 million URLs with a 0.1% false positive rate.

Answer: Use the formula m = -n ln(p) / (ln2)^2. Here n=10,000,000, p=0.001, ln(p) ≈ -6.9078. So m = -10,000,000 * (-6.9078) / 0.48045 ≈ 143,775,000 bits. Convert to bytes: /8 ≈ 17,971,875 bytes ≈ 17.1 MB. Bits per element ≈ 14.4. Optimal k = (m/n) ln2 ≈ 10. So you need about 17 MB and 10 hash functions. This demonstrates the ability to do quick back-of-the-envelope calculations, a key interview skill. Compare to storing URLs directly, which would be gigabytes.