英文:
Which data structure is used to implement a trie?
问题
Trie在Java中应使用哪些数据结构?
我使用链表、数组、映射吗?
英文:
Which data structures should I use to implement a trie in Java?
Do I use a linked list, array, map?
答案1
得分: 3
我实现Trie的方法是使用自定义类来表示节点,并将外部链接存储为HashMap或ArrayList(取决于子节点的数量)。
将这两种情况分开的原因是因为许多节点只有少数子节点,使用Map实际上会减慢速度。如果我记得没错,我将子节点的数量限制在大约4个。
英文:
The way I implemented a Trie was to use a custom class for the node and store outgoing links as either a HashMap or ArrayList (depending on the number of child nodes).
The reason to split the two cases was that many of the nodes would have just a few child nodes and using a Map would actually slow things down. If I recall correctly I put the limit at about 4 child nodes.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论