Trie使用哪种数据结构来实现?

huangapple go评论68阅读模式
英文:

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.

huangapple
  • 本文由 发表于 2020年9月28日 22:40:25
  • 转载请务必保留本文链接:https://go.coder-hub.com/64104383.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定