Hash array mapped trie - sellout/data-structure-zoo GitHub Wiki

A hash array mapped trie (HAMT) is a data structure that can be used to implement a pure finite map or multimap with most operations taking O(1), making it competitive with a hash table. One caveat is that it uses the Hamming weight, and while it can be implemented in software in O(1), that can add a huge constant factor relative to having a machine instruction that calculates it.

• [bind](/sellout/data-structure-zoo/wiki/bind) – O(1)
• [lookup](/sellout/data-structure-zoo/wiki/lookup) – O(1)
• [rebind](/sellout/data-structure-zoo/wiki/rebind) – O(1)
• [unbind](/sellout/data-structure-zoo/wiki/unbind) – O(1)