[算法] 为什么搜索引擎用这个Trie树存储词组而不是Hash容器? [复制链接]

1楼 [报告]

发表于 2012-09-05 17:52 |显示全部楼层

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

2楼 [报告]

发表于 2012-09-07 10:02 |显示全部楼层

O(1)是指平均查找长度为常数，和数据的规模无关。
有序表或树的折半查找算法平均查找长度为log2N，即查找算法的时间复杂度为O(N*log2N)。

任何查找算法都是要比较的！否则不能确定是否找到了。
Tire不懂，但Hash表是不错的查找表，而且构造和查找的思路一致，好实现！