The Dictionary Problem: How Do You Efficiently Look Up Things?

A walkthrough of the classic dictionary problem in computer science, exploring how to efficiently check membership in large collections. Starting from unsorted arrays with O(n) lookup, progressing through sorted arrays with binary search (O(log n)), hash tables (O(1) average), and binary search trees (O(log n) with ordering support). Each structure's trade-offs in speed, memory, and flexibility are compared using a browser-based spell checker as the running example. Hash tables win for pure membership checks, BSTs win when ordering matters, and sorted arrays work well for static datasets. The post teases Bloom filters as a memory-efficient probabilistic alternative.