如何理解 Tree 或 Trie 中的浅尺寸和保留尺寸？

Question

我有一个字符树数据结构，如下所示：

sealed class TrieNode(val children: MutableMap<Char, TrieNode>) {
    class NormalNode(kids: MutableMap<Char, TrieNode>) : TrieNode(kids)
    class EndNode(kids: MutableMap<Char, TrieNode>, val info: SubInfo) : TrieNode(kids)
}

如您所见，我的 trie 由 NormalNode 和 EndNode 组成，其中 NormalNodes 是内部节点，EndNodes 是一次叶子。

当我在运行时间创建 trie 后进行内存分析时，我可以看到 class TrieNode 的浅层内存使用是 1 MB 而保留使用是 120 MB。代码是 android 中的运行并且实现似乎没有任何错误。

我的问题是 class 的保留内存在这种 nested/composite 实现中是否有意义。浅尺寸是对象本身的尺寸。但保留大小是所有私有引用（仅通过此路径访问的引用）及其子引用的总大小。现在考虑由相同种类的物体组成的 tree/trie。每个节点的 shallow size 将是节点的大小，但是 retain size 将是节点的大小 + 它所有子节点的大小之和，因为它的所有子节点只能通过这个父节点访问？

Answer 1

（我不认为对此有一个明确的答案，但这里有一些想法。）

正如您所说，“浅”大小应该只包括 TrieNode 对象本身，而不是它们所指的任何内容。并且“保留”大小通常会包括从那些 classes 可以到达的任何东西：这将包括他们的 children 地图和所有其他的 trie 可以从他们;还有他们引用的info对象（以及任何他们指的是……）。

我最关心的是为每个节点使用一个 Map 对象，因为大多数 Map 实现会占用相当多的内存 — 你将为你的每个节点创建一个对象特里

最常见的映射类型是散列映射，它包含一个散列数组 table（可能从 16 个或更多条目开始，并且会根据需要增长到明显大于数字）条目数）；根据它的实现方式，每个非空哈希条目可能指向一个节点链表，每个节点都可能引用键和相应的值。这是相当少的对象，占用的内存比您预期的要多。（ConcurrentHashMap 以使用更多内存为代价获得良好的并发性能。）

所以我怀疑这将解释浅层和深层内存使用之间的很多差异。（当然，你的 trie 中的 info 对象也将包含在其中，所以如果它们非常大或最终引用很多东西，那么地图可能不是主要因素。）

因此，如果内存使用是一个真正的问题，您可能需要重新考虑重写 class 以使用不同形式的存储。（这可能需要付出很多努力，并使它变得更复杂 and/or 更不通用，所以只有当它是一个重要问题时才值得这样做。）

例如，如果您希望每个节点都有很少数量的子节点，那么您可以将 Map 替换为并行的键和值数组——大多数操作将是 O(n)，但如果 n 是总是很小，那么内存节省可能会超过它。 And/or 如果您知道您的密钥始终是 Char，那么您可以对该类型进行硬编码并避免所有盒装原语。

（作为中途之家，您创建了一个新的 MutableMap 实现，具有一些内存优势；然后您可以保持漂亮干净的 trie 实现。）

如何理解 Tree 或 Trie 中的浅尺寸和保留尺寸？

How to understand shallow size and retain size in a Tree or Trie?

java

kotlin

memory

profiling