建议首先阅读Introduction to HAMT。

Operation

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.

Advantages of HAMTs

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有什么差别呢？

  1. HAMT需要对key hash，而ART的key就是长整型，无需hash
  2. HAMT不支持范围查询，而ART支持范围查询

相对于hash table，HAMT可以节省内存；相对于Radix Tree，ART可以节省内存。
这两者都用用来节省内存的。

参考资料：

  1. Introduction to HAMT
  2. wikipedia