---
title: "Space/Time Trade-offs in Hash Coding with Allowable Errors"
description: "Bloom's paper asks how a compact in-memory screen can reject missing keys before an expensive exact lookup. Read it to see why one zero bit proves absence, why all-one evidence means only possibly present, and how shared hash positions trade memory for a controlled false-positive path."
canonical_url: "https://fanout.sh/daily/2026-08-17-bloom-filter"
md_url: "https://fanout.sh/daily/2026-08-17-bloom-filter.md"
last_updated: "2026-08-17"
access: "public"
---

# Space/Time Trade-offs in Hash Coding with Allowable Errors

Bloom's paper asks how a compact in-memory screen can reject missing keys before an expensive exact lookup. Read it to see why one zero bit proves absence, why all-one evidence means only possibly present, and how shared hash positions trade memory for a controlled false-positive path.

## Paper details

- Authors: Burton H. Bloom

- Venue: Communications of the ACM, 1970

- Track: Systems

- Difficulty: Easy

- Reading time: 30 min

- Original paper: https://dl.acm.org/doi/10.1145/362686.362692

## What you will learn

- How each inserted key sets several shared bit positions and a query replays the same address rule.

- Why any zero proves a key absent while collisions can make a never-inserted key appear possibly present.

- How bit occupancy, hash count, exact confirmation, and the cost of false positives determine whether the filter helps.

## Continue exploring

[Explore Bloom filters](https://fanout.sh/system/archive/bloom-filters): Continue into Fanout's Bloom Filters guide and connect the original one-sided membership test to database read paths, filter sizing, false-positive budgets, and exact fallbacks.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md