My Opera搜索引擎的Hash特性
Saturday, September 16, 2006 5:37:57 AM
Hash表简单来说就是一种数据的存储结构。在这种结构中，数据会通过一个Hash函数 y=f(x) 计算得出唯一（理论上）的位置，然后保存在这个位置上。查找的时候只需要利用同样的函数进行一次计算，就可以得出数据的位置，直接去读取就行了。因此，Hash表是一种相当高效的查找表，决定它性能的关键因素是Hash函数的优劣。
互联网上承载着海量的数据，利用搜索引擎，我们可以快速搜索到自己需要的信息。因此从这个角度来看，我认为搜索引擎也是一种抽象的Hash表。它的Hash函数是： Result=SearchEngine(keywords)。认识了这点之后，我不禁从Hash函数的角度对搜索引擎的评价标准进行了一番思考：
1. 冲突少
从这个角度来看，我们在Google或者百度上面搜索一个关键词如“汽车”，出现成千上万的结果并不是好事。这说明成千上万条结果都具有相同的Hash值，冲突太多了，必将降低用户的检索效率。
理论上，如果搜索只有一条结果将是最优化的，不过这也不现实，因为搜索引擎无法接受我们的脑电波，不知道我们在想什么。就算知道了，以它们的IQ也无法明白我们想要什么。但是，通过修改现有的Hash函数算法来实现更加精确的搜索却是行之有效的方法。目前，Google正在这个方面努力着。
2. keywords可描述性很强
Hash函数变化了，参数也很有可能会发生变化。这是因为新的Hash函数需要利用更多的输入条件来确定唯一的位置值。这时，用户使用体验可能会发生变化。为了不导致用户的体验变差，搜索引擎需要提供一种可描述性很强的Keywords。简单来说就是很容易上手、而且描述很清晰。
3. 运算速度快
前两个问题都解决了，那么最后一个需要注意的问题就是速度一定要快。毕竟，大家什么都不缺，缺的就是时间，做为互联网基础设施的搜索引擎，又怎么能够浪费大家的宝贵时间呢？
最后我把几个搜索引擎的Hash函数拿出来比较一下：
Result1=Google(keywords1)
Result2=Baidu(keywords2)
Result3=Webus(keywords3)
Result1.Length >= Result2.Length >> Result3.Length
这是因为Google的数据量是很大的，超过了百度的数据量。因此Result1.Length >= Result2.Length
Webus的Hash算法考虑了更多输入条件，因此散列程度更高，冲突会少很多，因此Result2.Length >> Result3.Length
keywords1.complexity = keywords2.Complexity < keywords3.Complexity
Google和百度是同类型的搜索引擎，关键词复杂程度相同。但是Webus由于要考虑更多的输入条件，因此关键词复杂度会超过前两个。
Baidu.Speed > Google.Speed > Webus.Speed
百度的缓存机制比较极端，因此效果也是最好的。Google的分布式查询效果很稳定，速度也不错。Webus刚刚起步，限于资源和程序分布度的原因，速度比Google的慢。相关：http://www.cppblog.com/inwind/articles/1590.html
互联网上承载着海量的数据，利用搜索引擎，我们可以快速搜索到自己需要的信息。因此从这个角度来看，我认为搜索引擎也是一种抽象的Hash表。它的Hash函数是： Result=SearchEngine(keywords)。认识了这点之后，我不禁从Hash函数的角度对搜索引擎的评价标准进行了一番思考：
1. 冲突少
从这个角度来看，我们在Google或者百度上面搜索一个关键词如“汽车”，出现成千上万的结果并不是好事。这说明成千上万条结果都具有相同的Hash值，冲突太多了，必将降低用户的检索效率。
理论上，如果搜索只有一条结果将是最优化的，不过这也不现实，因为搜索引擎无法接受我们的脑电波，不知道我们在想什么。就算知道了，以它们的IQ也无法明白我们想要什么。但是，通过修改现有的Hash函数算法来实现更加精确的搜索却是行之有效的方法。目前，Google正在这个方面努力着。
2. keywords可描述性很强
Hash函数变化了，参数也很有可能会发生变化。这是因为新的Hash函数需要利用更多的输入条件来确定唯一的位置值。这时，用户使用体验可能会发生变化。为了不导致用户的体验变差，搜索引擎需要提供一种可描述性很强的Keywords。简单来说就是很容易上手、而且描述很清晰。
3. 运算速度快
前两个问题都解决了，那么最后一个需要注意的问题就是速度一定要快。毕竟，大家什么都不缺，缺的就是时间，做为互联网基础设施的搜索引擎，又怎么能够浪费大家的宝贵时间呢？
最后我把几个搜索引擎的Hash函数拿出来比较一下：
Result1=Google(keywords1)
Result2=Baidu(keywords2)
Result3=Webus(keywords3)
Result1.Length >= Result2.Length >> Result3.Length
这是因为Google的数据量是很大的，超过了百度的数据量。因此Result1.Length >= Result2.Length
Webus的Hash算法考虑了更多输入条件，因此散列程度更高，冲突会少很多，因此Result2.Length >> Result3.Length
keywords1.complexity = keywords2.Complexity < keywords3.Complexity
Google和百度是同类型的搜索引擎，关键词复杂程度相同。但是Webus由于要考虑更多的输入条件，因此关键词复杂度会超过前两个。
Baidu.Speed > Google.Speed > Webus.Speed
百度的缓存机制比较极端，因此效果也是最好的。Google的分布式查询效果很稳定，速度也不错。Webus刚刚起步，限于资源和程序分布度的原因，速度比Google的慢。相关：http://www.cppblog.com/inwind/articles/1590.html
