Hash Maps: more room at the bottom
summary
Claims that a CHAMP variant doubles iteration speed (2x iteration), speeds equality checks by 10–100x, and reduces implementation size to about two thirds. Implements a ClojureScript port called lean-map and verifies results in real benchmarks. Key changes: key/value entries packed before subnode refs, bitmap metadata split, and upward compression on deletions so shared structure allows node-level equality. Works overall, though assoc/transient assoc shows a ~15% slowdown in one test that the author narrows with small layout tweaks.
AI-written summary · about
chapters (12)
- 0:00Start
- 0:16Building an alien space ship
- 3:22Clojure Hash Maps tree of nodes 32 way branching factor
- 3:34Node internals
- 4:08How a key finds a node
- 6:02Adds incidental complexity
- 6:58Sub node references are scattered throughout a nodes array
- 9:57Decomplect metadata
- 12:15CHAMP iteration algorithm
- 15:11Current Delete Algorithm
- 19:26Structural Sharing
- 24:46Clojure Hash Maps is one of Clojure's best exports
