Hash Array Mapped Trie performance

Question

I'm trying to implement Hash Array Mapped Trie in Java. Before, I thought that this data structure should be more memory efficient than Hash Map, but when i made first memory measurements using Visual Vm, i found that my implementation require more memory then Hash Map (also "put" operation is slower). I can't understand : HAMT really requires more memory or i made mistake in implementation. Similar performance results as in this question.

Has "Hash Array Mapped Trie" performance advantages over "Hash Table" ("Hash Map")?

Answer 1

A single HAMT can be expected to require more memory than a single hash table. The memory advantage comes only when you make use of the persistent properties of a HAMT. When you make a copy of a HAMT and change a single value in it, you can share most of the nodes between the two copies, for a hash table you will usually need to duplicate the entire table structure.