使用嵌套 HashMap 创建 TRIE 有什么好处?
例如,我们有一个嵌套的 HashMap ,其中每个映射只有一个字符的键。因此,对于单词“Dog”,我们会有类似 myHashMap['d']['o']['g']['*'] = True
的东西。
末尾的“*”表示条目结束。
在书中,我从未见过这种方法,而是“经典”的 Node 类。为什么?
最佳答案
我用
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()
).
关于java - 使用嵌套 HashMap 实现 TRIE?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19897242/