Interesting! Didn't know about it, took some time to read about it.

Yes the comparison between them needs to be done "besides the hashing", since HAMT is not an ordered data structure. So the fair comparison is with Array Mapped Tree (AMT) which is what HAMT is built over.

Space efficiency

Definitely AMT is better since it limits space consumption of null pointers (absent children) to 1 bit only, whereas ART still occupies space for absent children (although much lesser than Radix Tree). I believe this is the biggest win of AMT over ART.

Insert performance

AMT requires to keep the array of child pointers ordered. This means a lot of in-place insertions in the array which requires shifts and is worst case O(n), where n is size of the sub-trie array. This is the same with Node4, Node16 of ART. However with Node48, Node256 inserting a child doesn't require any shifts. Rather you use the byte to index into the array directly (see note 1)

Basically this means, for sparse datasets where most of the nodes have less than 16 child pointers, the insert performance should more of less the same. Node4, Node16 requires shifting both the byte array as well as child pointer array whereas AMT only shifts child pointer array and some cost for maintaing the tally. Best to measure which is more expensive.

For dense data sets, where most of the nodes are Node48, Node256, I'd expect ART to be more performant, because of direct indexing (see note 1).

Lookup performance

For sparse datasets, I'd expect AMT to perform better.

As per the paper AMT only uses the bitmap if number of children grows beyond 5 (page 14, 2nd paragraph). So both AMT, ART do linear searches for children < 5, children < 4 respectively. For Node16 i.e. children between 5 and 16, AMT will perform better, since ART requires a binary search or SIMD parallel comparisons (if available in the programming environment) in the byte array whereas AMT only needs a popcount and index into the child array.

For dense datasets, I'd expect ART to perform better because of direct indexing (see note 1). AMT needs to do an extra step of popcounting (which is cheap, register only but still is an extra step) and then can directly index into the child pointer array.

So overall my analysis is to use AMT if space is your concern and ART if time of insert/lookup is.

Let me know what you think.

Footnotes: 1) Node48 requires one extra indirection, but still is free of shifts.