Tries对现代建筑仍然是一个好主意吗？

我最喜欢的大学数据结构之一就是Trie.如果共享前缀,它是一个很好的数据结构,用于保存大量字符串.查找也很好,因为它们是在字符串的O(| length |)处完成的,无论集合中有多少字符串.

相比之下,平衡树的设置项数量为O(log N),加上您为比较支付的费用.哈希表将涉及哈希计算,比较等.

因此,令我惊讶的是,在大多数语言的标准库中没有Trie实现.

我能想到的唯一原因是内存访问成本太高的可能性.如果进行树查找,则不是在调查O(log N)位置,而是在进行O(| length |)不同的位置,并产生所有后果.如果字符串很长,这可能会导致太多.

所以我想知道:我刚才描述的问题有多少？当您需要存储大型字符串或字符串映射时,您会怎么做？

我之前没有想到这是一个值得关注的领域,但是现在你提到它,有时候标准的Trie实现可能会很方便.另一方面,据我所知,Tries由Python和Perl以及我现在使用的其他字符串精通语言使用.

最后我检查过,很久以前,BSD内核代码在代码中使用Tries(Patricia Tries)来选择最佳的发送数据包接口.看起来维基百科有一些信息.