Algorithm dossier

  • Category: Hashing
  • Worst-case complexity: O(1)
  • Approach: Iterative
  • Data structure: Hash table
  • First formalised: 1970s

Why this snippet is Bloom Filter Insertion

Why a Bloom filter. Hash x with several independent hash functions and set the bits at each resulting index. Membership-check works the same way: if *any* corresponding bit is 0, x is *definitely absent*; if *all* are 1, x is *probably present* (with false-positive rate controllable by table size and k). Why it matters. O(k) ops where k is small and constant, regardless of how many items you've inserted. Constant time, sub-linear space — the canonical "probabilistic data structure" win.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.