Hash array mapped tries usually have a bunch of “slots” per level. So where a binary tree has branching factor of 2, a HAMT will usually have many more. Array.Hamt
uses 32, for example. So, with a good hashing function, the depth becomes log32(n)
, which means that even for an array of 1024 elements, you only need 2 levels in the tree.
In practice, that’s “close enough” to call it constant time.