Swiss Tables are hash tables. O(1) lookup, but expensive to copy.

HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy.

They are not really comparable, since hash tables are not persistent.

In functional languages, persistent data structures are MUCH more natural to work with. HAMTs we're originally created for the Clojure standard library, IIRC.

HAMTs lend themselves to more elegant/performant implementations than self-balancing trees, since they don't need to rebalance as long as your hash function is good.

Also, HAMTs generally have a high branching factor, so the search can be as fast as a hash table for small-to-medium maps. Though I don't know of any HAMTs using SIMD tricks like Swiss Table.

(EDIT: I guess the popcnt thing that HAMTs do would be considered a SIMD trick. Larger registers would allow the branching factor to be raised.)

Like hash tables, HAMTs don't require intermediate key comparison for lookup.

The original HAMT paper is a good read: http://infoscience.epfl.ch/record/64398/files/idealhashtrees...

> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy.

O(LOG(k)) might be a clearer bound rather than n.

For a hash trie, the depth is bounded by the log of the number of elements: O(log(n)).

I think O(log(k)) would mean that the bound is based on the size of the largest key. This may be true of regular tries, but not of hash tries.

Completely unrelated.

The primary advantage of hamt is that they’re persistent, so they’re immutable with cheap update, but with efficient lookup & good cache behaviour thanks to the dense nodes and high branching factor.