Immutable/persistent data structures are almost always some sort of tree, even if on the outside they look different. Knowing that all your operations that were constant (for the mutable case) are now logarithmic (for the immutable case) is a must.

Modern HAMTs are faster than your run of the mill hash table, the "constant" vs. "logarithmic" is misleading here.

The HAMT will be log32 or log16 N and will have runs of values that play very nicely with the caching behavior of the processor if you find yourself traversing more than one value.

With log N > 2, you have to pay extra space costs. This can be worse than a simple binary tree.

Locality is also a problem for high-performance applications, but the HPC people would never go near this stuff anyways.

You might be interested in this: http://www.ergy.com/FSet.html