为什么搜索引擎用这个Trie树存储词组而不是Hash容器?

weichuang02

Trie和其他的树形结构一样，查找需要O(lgN)时间，为什么搜索引擎用这个存储而不是Hash容器? cpu和内存消耗Hash都低啊。Trie是O(lgN)吧

Hash的搜索是O(1)。除了大数据情况下，hash冲突的概率会升高以外，例如我的hash函数(fnv1.a)冲突概率大概是13万分之一，那么如果1亿个数据，那么相当于每10个hash bucket里面有一个key冲突的，需要比较两次，但是这样还是O(1)啊。

为什么不同Hash容器呢?

请高手指点!

weichuang02

hbmhalley 发表于 2012-09-05 17:59
回复 1# weichuang02

Hash都是O(1)，这个有疑问吗?
树形结构搜索是lgN，这个有疑问吗?

weichuang02

_Rayx 发表于 2012-09-05 20:54
呵呵，乱说。
复杂度全算错。

那大侠说，这两个复杂度应该是什么样子的?

weichuang02

edshea 发表于 2012-09-14 08:57
回复 19# hijzhang

查找串的长度是多少？一般的单词长度有限，即可认为是常量，就是O(1)

随着树越来越大，查找一个单词需要的时间也在增长.

而Hash是不增长的。怎么能说trie的查找性能更好呢?