Big O in a Homemade Hash
summary
Builds a Hash class from scratch, first as a naive tuple_map that shows linear lookup, then replaces it with a sparse array plus a digest function and buckets, measuring reads that stay flat and writes with occasional rehash spikes (one spike reaches ~48s against millions of entries). Growth policy is grow when bucket has 10 keys, resizing by double size and next prime and rehashing everything, yielding amortized O(1) performance but not production‑tuned compared to Ruby's native C implementation.
AI-written summary · about
chapters (41)
- 0:00Intro
- 0:41What is a Hash
- 1:36Hash Clasp
- 2:10Syntax
- 2:31Testing
- 2:49Phone call
- 3:20The problem
- 3:47Big O notation
- 4:45Order of growth
- 7:18The Traveling Salesman problem
- 9:57The Big O problem
- 10:32Measurement
- 11:11Internals
- 11:34RAM
- 12:46New Plan
- 14:08Collisions
- 14:31Buckets
- 14:57Waste
- 15:25Memory for speed
- 15:51Trade off RAM
- 16:05Grow as needed
- 16:21Spread things out
- 16:50Rehash every key
- 17:07Basic strategy
- 17:26Modulo
- 18:29Growth Strategy
- 19:03Number Conversion
- 19:29Same Value
- 21:07Review
- 21:38Performance
- 22:05Graph
- 23:14Spikes
- 23:31Native Hash
- 24:14Linear Performance
- 25:01Success
- 25:35Growth
- 26:44Email
- 27:34Applications
- 28:31Adding Servers
- 29:14President Obama
- 29:35Outbox
related talks
27mReimplementing Ruby's Hash
11mWhy Hashes Will Be Faster in Ruby 2.0
25mMaking Hash Parallel, Thread-Safe and Fast!
32mThe Humble Hash
34mBeyond the language. An introduction to algorithms.
34mLet's subclass Hash - what's the worst that could happen?
20mAlternative Data Structures in Ruby
23mParallelization of Dynamic Languages - Synchronizing Built-in Collections