Skip to content

The Hashing Principle

Transforming arbitrary keys into bounded integers enables constant-time average-case access by converting search into direct addressing, trading memory for speed.

Tension Addressed

Memory Usage vs. Time Performance

Recognizable As

Hash tables/maps/dictionaries; content-addressable storage; cryptographic hashes; consistent hashing in distributed systems; locality-sensitive hashing

Canonical Sources

Knuth, TAOCP Vol. 3 (1973); Cormen et al., Introduction to Algorithms (1990)

Transfers To

Distributed Systems (consistent hashing, DHTs), Security (password storage, integrity), Database Indexing (hash indexes), Caching (cache keys)

Sub-concepts: - Collision resolution: Open addressing vs. chaining as fundamental strategies - Load factor: The space-time trade-off parameter - Hash function quality: Uniform distribution as the essential property