What I like about HAMTs is that they can be super simple to implement if you make them one bit per level. They are like a combination of a binary search tree and hash table but without any of their annoyances.
* In binary search trees, you need to balance the tree every time you insert something because the tree will be linear if you insert the nodes in order. In a HAMT the positions are determined by the hash, so the positions will be random-like and not depend on the order you insert the nodes in.
* In binary search trees, you need to perform some complicated steps to remove a node. In a HAMT, you can either just mark the node as deleted, or if you want to fill the gap, find a leaf node that has the removed node on its path and just put it there.
* In hash tables, when it starts to get full you need to rehash it or put the added item in the "wrong" slot or something. A HAMT never gets full because it's a tree so you just add another child node.
* In binary search trees, you need to balance the tree every time you insert something because the tree will be linear if you insert the nodes in order. In a HAMT the positions are determined by the hash, so the positions will be random-like and not depend on the order you insert the nodes in.
* In binary search trees, you need to perform some complicated steps to remove a node. In a HAMT, you can either just mark the node as deleted, or if you want to fill the gap, find a leaf node that has the removed node on its path and just put it there.
* In hash tables, when it starts to get full you need to rehash it or put the added item in the "wrong" slot or something. A HAMT never gets full because it's a tree so you just add another child node.
Here I have written an explanation of a simple HAMT: https://www.robalni.org/posts/20220507-a-hash-table-you-dont...