algorithm - 哈希数组映射 Trie 性能

Question

我正在尝试用 Java 实现哈希数组映射 Trie。之前，我认为这种数据结构应该比 Hash Map 的内存效率更高，但是当我使用 Visual Vm 进行第一次内存测量时，我发现我的实现需要比 Hash Map 更多的内存(而且“put”操作更慢)。我无法理解:HAMT 确实需要更多内存，或者我在实现时犯了错误。与 in this question 类似的性能结果.

“Hash Array Mapped Trie”比“Hash Table”(“Hash Map”)有性能优势吗？

Answer 1

预计单个 HAMT 需要比单个哈希表更多的内存。只有当您使用 HAMT 的持久属性时，内存优势才会出现。当您复制 HAMT 并更改其中的单个值时，您可以共享两个副本之间的大部分节点，对于哈希表，您通常需要复制整个表结构。