Introduction

A Bloom filter uses k hash functions, but all of them write into the same bit array of size m. That design is not an arbitrary shortcut. It is the whole reason Bloom filters stay compact while still giving a controllable false-positive rate.

One Shared Bit Array Is the Data Structure

A Bloom filter stores no actual keys. Instead, each inserted item is hashed k times, and the resulting bit positions are set to 1 in one shared bit array.

For an element x, the insert operation looks like this conceptually:

• compute h1(x), h2(x), ... hk(x)
• map each result to an index in the same array of m bits
• set those k positions to 1

A lookup does the same hash computations and checks whether all corresponding bits are already set.

1class BloomFilter:
2    def __init__(self, size, hash_count):
3        self.size = size
4        self.hash_count = hash_count
5        self.bits = [0] * size
6
7    def _hashes(self, item):
8        h1 = hash(item)
9        h2 = hash(str(item) + "salt")
10        for i in range(self.hash_count):
11            yield (h1 + i * h2) % self.size
12
13    def add(self, item):
14        for index in self._hashes(item):
15            self.bits[index] = 1
16
17    def might_contain(self, item):
18        return all(self.bits[index] for index in self._hashes(item))
19
20bf = BloomFilter(size=32, hash_count=3)
21bf.add("apple")
22print(bf.might_contain("apple"))
23print(bf.might_contain("pear"))

That shared array is the structure. If you gave each hash function its own separate array, you would no longer get the same space efficiency profile.

Why Separate Arrays Would Be Wasteful

Imagine using k different arrays, one for each hash function. You would need k * m total bits to represent what a normal Bloom filter represents with just m bits.

That changes the design in two bad ways:

• memory usage grows by a factor of k
• cache behavior gets worse because each operation touches more independent memory regions

A standard Bloom filter deliberately allows different hash functions to collide in the same array. Those overlaps are not a bug. They are part of the probability model.

The false-positive rate depends on how full the shared bit array becomes after inserting n items. A standard approximation is p ≈ (1 - e^(-kn/m))^k. That formula assumes all hashes write into one combined bit space.

Sharing the Array Preserves the Probability Tradeoff

The point of a Bloom filter is not zero error. The point is a compact representation with no false negatives and an acceptable false-positive rate.

Using one array lets you tune the tradeoff with just three parameters:

• 'm for total bit capacity'
• 'k for number of hashes'
• 'n for expected inserted items'

Because all hash functions operate on the same array, each inserted key contributes k chances to mark bits that later queries will inspect. The resulting occupancy of the single array is exactly what drives the probability behavior.

If each hash function had its own array, you could model the structure differently, but you would spend much more space to achieve a similar logical effect. Bloom filters are popular precisely because they do not make that trade.

The Hash Functions Do Not Need Separate Arrays to Stay Independent

Another misunderstanding is thinking that separate storage is required to keep the k hash functions independent. It is not. Independence is about how the indices are generated, not about where the bits are stored.

In practice, many Bloom filter implementations do not even compute k fully independent hash functions. They often use double hashing to derive multiple indices from two base hashes, as the example above does. That is usually fast enough and statistically good enough for real systems.

The data structure works because the indices spread items across the one array, not because each hash has its own private memory.

Common Pitfalls

A common mistake is assuming collisions in the shared array are harmful. In a Bloom filter, collisions are expected. They only become a problem when the array gets too full and the false-positive rate rises beyond what the application can tolerate.

Another mistake is choosing k too large for a small m. More hashes are not always better. After a point, they only set more bits and saturate the filter faster.

Developers also sometimes store bytes or booleans casually without thinking about memory layout. That is fine for a toy example, but high-performance implementations usually pack bits densely because memory efficiency is the entire point.

Finally, do not confuse a Bloom filter with a hash table. A Bloom filter cannot return stored values or prove that an item exists. It can only say "definitely not present" or "possibly present".

Summary

• All k hash functions share one bit array because that is what makes Bloom filters compact.
• Separate arrays would multiply memory use without improving the core probability tradeoff.
• Collisions in the shared array are expected and are part of the design.
• The false-positive rate depends on how k, m, and expected item count interact.
• Hash independence is about index generation, not about giving each hash function separate storage.