Chinaunix

标题: hash和trie树比较 [打印本页]

作者: pengjianbokobe 时间: 2010-08-27 14:44
标题: hash和trie树比较
刚接触trie树，请达人说说他们各自的优缺点和什么时候用最好？

作者: ecjtubaowp 时间: 2010-08-27 14:50
都可以对付字符串的处理。

作者: daybreakcx 时间: 2010-08-27 15:02
对于hash来说，字符串的hash求值复杂度基本上是和字符长长度相关的，因为你需要遍历一次你要求hash值的字符串，这点上Trie与其是相同的，树的深度和字符串的长度相同，因此单从检索效率来说，我个人的观点是两者差不多
但是从应用范围来说，hash会更广一点，因为与其说hash是一种数据结构，倒不如说它是一种方法，一种映射的方法，除了字符串，hash对于数值等的表现也非常好，而Trie基本上多数用在字符串上
从空间使用来说，个人观点是hash占优，因为虽然Trie的主要空间损耗还是在数据部分，但是每个节点的子节点未占满的情况下是需要保留指针域的，未出现的分支就置空，可是却占据了一个指针域，而相比之下，hash就没有这个顾虑，基本上附加损耗是常数的，我们以拉链的方式来看，本身除了链的头需要一个指针域之外，其余的都是对于一个新节点才会产生一个新的next指针，额外的消耗不会超过整个hash的模数（也就是求出hash值之后取余那个数）
但是hash如此的优秀却有它的一个不确定因素，也就是hash函数的选取，选好了你的查找效率就非常的高，选得不好可能比直接一个个比较还烂，而相比起来Trie则较为稳定，不管怎么样查找的比较次数总是一个串的长度，这是其优势
总的说个人会倾向于使用hash，但是根据不同场合我可能会选Trie，比如空间充足而且时间要求严格或者是找不到很好的hash函数的情况下
但是不管如何，多知道一点总是好多的

作者: pengjianbokobe 时间: 2010-08-27 15:27
回复 3# daybreakcx

辛苦了，daybreakcx，谢谢

作者: zboom 时间: 2010-08-27 15:42
谈一下个人的理解吧，把要查找的数据比作字典里的字的话，可以把trie比作音序查字法，而hash则是部首查字法或四角查字法。

于是，相对于trie来说，hash更灵活，选用不同的hash方法，效率和hash冲突的概率也不同（同一个部首的字也许有很多）；
而trie树主要问题是树的层高，如果要索引的字的拼音很长很变态，我们也要建一个很高很变态的树么？所以如果能固定层高，或是能将相同的特征抽取出来，岂不更好，于是有了radix树。

从查找效率来说，两者差不多；例证就是linux内核中路由表的组织是基于hash的，而free bsd中内核中路由表的组织是基于radix树的。

至于具体选择哪个，个人认为看具体情况了。

作者: pengjianbokobe 时间: 2010-08-27 16:18
回复 5# zboom

字典比喻很形象啊！radix树没听过，孤陋寡闻啊。。

作者: zboom 时间: 2010-08-27 16:28
A radix trie/tree, Patricia trie/tree, or crit bit trie/tree is a specialized set data structure based on the trie that is used to store a set of strings.
详细内容见：http://en.wikipedia.org/wiki/Radix_tree

作者: daybreakcx 时间: 2010-08-27 16:45
实际上Radix Tree是在Trie的基础之上将树中的链状部分集合起来，这样来降低树的高度

作者: ecjtubaowp 时间: 2010-08-27 17:20
内核中就有Radix Tree

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)