建议首先阅读Introduction to HAMT。
A HAMT is an array mapped trie where the keys are first hashed to ensure an even distribution of keys and a constant key length.
In a typical implementation of HAMT’s array mapped trie, each node contains a table with some fixed number N of slots with each slot containing either a nil pointer or a pointer to another node. N is commonly 32. As allocating space for N pointers for each node would be expensive, each node instead contains a bitmap which is N bits long where each bit indicates the presence of a non-nil pointer.
The hash array mapped trie achieves almost hash table-like speed while using memory much more economically. Also, a hash table may have to be periodically resized, an expensive operation, whereas HAMTs grow dynamically. Generally, HAMT performance is improved by a larger root table with some multiple of N slots.
HAMT与adaptive radix tree有什么差别呢？
- HAMT需要对key hash，而ART的key就是长整型，无需hash
相对于hash table，HAMT可以节省内存；相对于Radix Tree，ART可以节省内存。