我正在阅读有关trie数据结构的内容,发现两种实现方法可以用来实现trie节点中的子项。以下是这两种实现方法的详细信息:
1) 使用长度为26的trie节点数组来存储trie节点的子项。
2) 使用HashMap来存储trie节点的子项,其中字符作为键,trie节点作为值。
请告诉我哪种实现方法更好,为什么?
我正在阅读有关trie数据结构的内容,发现两种实现方法可以用来实现trie节点中的子项。以下是这两种实现方法的详细信息:
1) 使用长度为26的trie节点数组来存储trie节点的子项。
2) 使用HashMap来存储trie节点的子项,其中字符作为键,trie节点作为值。
请告诉我哪种实现方法更好,为什么?
用于Trie节点的两种结构非常常见:
CharNode
char letter
CharNode[26] children
CharNode
char letter
Dictionary<char, CharNode> children
这些方法可以很好地工作,但它们浪费了大量的内存,因为子节点列表非常稀疏。在我看来,两种方法都没有提供性能上的优势来抵消内存成本。我更喜欢使用:
CharNode
char letter
CharNode[] children
或者
CharNode
char letter
CharNode* firstChild
CharNode* sibling
children
数组的大小是可变的,只需容纳实际使用的孩子数量,并且孩子按最常用的字母排序。顺序搜索找到所需的子项。数组是经典的教科书实现,在默认选择中使用。
哈希表在字母表很大且实际使用的键的数量相对较小时,占用的内存较少。但哈希表本身的结构比数组占用更多的内存。因此这是一种权衡,并取决于实际trie的键。
每个子链接的访问速度几乎相同,为O(1)。
unordered_map
所需的内存是array
的5倍,而map
所需的内存是array
的6(至8)倍。请参见-https://dev59.com/iUIEtIcB2Jgan1znlxpN - Manohar Reddy Poreddy