3 ms·
I'm pretty sure that's exactly like a HAMT except that HAMTs only use one bitmap. I'm not sure why the CHAMP is referred to as "compressed", then, since HAMTs a
by wyager 9y ago
I'm pretty sure that's exactly like a HAMT except that HAMTs only use one bitmap. I'm not sure why the CHAMP is referred to as "compressed", then, since HAMTs are compressed using the same bitmap technique with a slightly different node structure.
- loopingoptimism 9y agoIn principle both HAMT and CHAMP compress sparse associative arrays by construction. However, the bitmap encoding of CHAMP results in a better compression for map data structures, enabled by permuting the elements that are stored in the node's array. This is in particular the case when compared to Clojure's PersistentHashMap. Clojure reserves two array slots per entry to either store a) two pointers inline (i.e., key and value tuple), or b) a single reference to a sub-trie in the second slot. At runtime Clojure checks if the first slot is equal to 'null' for distinguishing cases a)/b) and doing the correct type casts at runtime. The thesis visualizes this in chapter 3, page 42.