hash加速搜索的原理？

[jason52]

在网上下到2000w的csv，基于文本的搜索最快的的方式就是grep了吧。

1.那么如果 grep 'foo|bar' finename.txt 是否相当于先做一遍grep foo，再做一遍grep bar?

对大文件搜索才体会到了性能问题。

2.google的秒搜是基于一种什么思想呢？

http://v2ex.com/t/65589 这里提到

===========
我提供一个思路给你，在索引里面，定长数据查询效率要远远高于不定长数据，url是不定长数据，但是可以转变成为定长，如果散列足够随机，冲突不大的话，那么可以考虑，比如：
把url转换成为long值，hash(url) -> id
long值的范围是 2^64，说实话，我不认为你能达到产生冲突的可能性
然后做非uniq索引，在每次查询结果列表里面做遍历，在冲突小的情况下，每次基本返回一条数据。

如果你的数据量很小，允许一定误差，那就根本不考虑冲突的情况。

这其实就是hash的基本思想。
===========


hash都定长的话，就不需要通过诸如Knuth–Morris–Pratt algorithm的算法来匹配吗？

已读了

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://en.wikipedia.org/wiki/String_searching_algorithm

[miaoever]

都 hash 了，得到的 key 是一个数字，所以可以用 O(1) 的时间复杂度找到对应的值，而不用再进行字符串查找。

[jason52]

哦，对~~相当于查字典，知道一个词在第几页，就不用从a到z顺序遍历，直接翻页码就好了。是这个比方吧。

[jason52]

建hash相当于费一点空间给字典建一个目录，都是以空间换时间，但建好了在找速度就快了。

[senghoo]

Google 的搜索思想请参考hadoop的原理，差不多。大规模分布式计算。不是这种常规的hash查找。

[rrfeng]

求 csv 下载 XD……

[faceair]

@rrfeng 同求 ^ω^