为什么搜索引擎用这个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容器呢?

请高手指点!

fenghw8088

Hash表记录的存储特性是，存储在附近的记录没有任何关系，只能进行单记录精确查找！
而Tire树相对于Hash表虽然查找效率低，但：
1、可以快速完成大量记录的部分匹配
2、应该还能用文件存储聚集的类似数据，以应对内存的不足

hbmhalley

回复 1# weichuang02


    怎么算出来的lgN? 又是怎么来的O(1)?
    Trie<Hash这是定死的

weichuang02

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

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

hbmhalley

回复 3# weichuang02


    Trie 是基于比较的吗？

hbmhalley

回复 3# weichuang02


    Hash 不需要遍历字符串+内的所有字符吗？

zhaohongjian000

回复 1# weichuang02


    如果你不了解trie，还是先搜搜看trie到底怎么做的吧。

_Rayx

呵呵，乱说。
复杂度全算错。

weichuang02

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

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

justmao945

树形是按照单词查找。所以复杂度是单词长度
hash是把单词hash了再查找，平均o1,但是hash占用内存不是一点大，而是很大。。。bucket要占内存，链式hash还要指针
树形可以搜类似的词？？