java - 使用嵌套 HashMap 实现 TRIE？

Question

使用嵌套 HashMap 创建 TRIE 有什么好处？

例如，我们有一个嵌套的 HashMap ，其中每个映射只有一个字符的键。因此，对于单词“Dog”，我们会有类似 myHashMap['d']['o']['g']['*'] = True 的东西。末尾的“*”表示条目结束。

在书中，我从未见过这种方法，而是“经典”的 Node 类。为什么？

Answer 1

我用

Map<Character, TrieMap<K, V>> children = new TreeMap<>();

用于我的 TrieMap 实现。它工作得很好。

使用普通 Node 结构的好处是您可以将指向父 map 的链接包装到结构中，这样您就可以更轻松地迭代 map 。我没有采用那条路线并在迭代时构建 Stack，因为我想确保我没有用不必要的内容使结构膨胀。然后我在迭代时构建堆栈。

Trie 的主要好处是它在键相似时具有节省空间的特性——在我看来，向结构添加不必要的权重是愚蠢的。因此我决定只使用 TreeMap。另一种选择是 Array 或 List，但对我来说，当数据模式化良好时，它们都不像 TreeMap 那样节省空间对于 Trie。

实际上 - 代码看起来更像:

/**
 * Map each character to a sub-trie.
 *
 * Could replace this with a 256 entry array of Tries but this will handle multi-byte character sets and I can discard
 * empty maps.
 *
 * Maintained at null until needed (for better memory footprint).
 *
 */
private Map<Character, TrieMap<K, V>> children = null;

....

/**
 * Create a new set of children.
 *
 * I've always wanted to name a method something like this.
 */
private void makeChildren() {
  if (children == null) {
    // Use a TreeMap to ensure sorted iteration.
    children = new TreeMap<>();
  }
}

所以我通过确保无子节点不包含浪费的空 Map 来进一步减少内存占用(尽管我可以很容易地使用 Collections.emptyMap()).