0

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")?

Community
  • 1
  • 1
Ivan Kurchenko
  • 4,043
  • 1
  • 11
  • 28
  • Did you use a classic trie or a [radix tree](http://en.wikipedia.org/wiki/Radix_tree)? What are the lengths of your strings for the test? hwo many strings did you use? How many bits did you hash to? – amit Feb 13 '14 at 11:34
  • No, i didn't use any of them. I used [hamt](http://en.wikipedia.org/wiki/Hash_array_mapped_trie) . For tests I made two cases : with random integers and sequential integers as keys. Number of keys was 1-5 millions in different tests. Hash prefix length was 4 bit (but in classic variant should be 5). – Ivan Kurchenko Feb 13 '14 at 12:01
  • Who told you hamt's are faster than hash tables in any way? Their big advantage is being persistent, not being particularly fast. The fast implementations also use low-level trickery like hardware popcount etc. I think you can get close to hash table speed that way – Niklas B. Feb 13 '14 at 17:01
  • Niklas B., thanks for a comment! I made mistake in the question. I really mean memory usage instead of performance. As i understood from "Ideal Hash Trees" and "Fast And Space Efficient Trie Searches" articles , hamt should be more memory efficient. Or I'm wrong? – Ivan Kurchenko Feb 13 '14 at 17:44

1 Answers1

2

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.

JanKanis
  • 6,346
  • 5
  • 38
  • 42