php - 1亿个32位的md5的密码值，怎样查询其中一个md5值是否存在效率最快？

Question

采用那种存储最好？比如只需检测这个数据库中是否存在一个“9d97c57dfc685f9b10d8d1b944330c09”即可，返回true or false

Answer 1

你的业务模型不清晰，没法得到一个好的回答，我说几个方法并说明优缺点吧

1. 排序并顺序存储到硬盘，就32bit32bit32bit去顺序存储即可。搜索采用最简单的二分查找（号称90%的程序员面试的时候写不出正确的二分查找，不过你可以找个现成的）。时间复杂度O(logn)，简直飞快无比
   优点：速度很快，磁盘空间压缩到极限，无内存占用
   缺点：需要先做一次全排列（还好，一劳永逸）很难加入新的索引值（每次加入都要重排列，关键是需要重写去dump磁盘）
   结论：适合不再变动的数据

2. 布隆过滤器。具体实现Google啊，比如这里有个Python版的实现
   优点：速度比较快，良好的插入性能
   缺点：有错误率，虽然可控
   结论：适合不是100%精确的需求，适合经常变动的数据

3. 分片（类似于1楼的办法）先哈希，然后取模，比如5000，拆分成5000个子文件。然后各子文件分别排序。查找时对key做hash并取模，找到对应的子文件，然后再二分查找。当然MD5一般可以认为是哈希均匀的，那么就不用哈希，直接取模就好了。
   优点：速度不错且插入性能还可以（单次插入只用对单个分片进行插入排序）
   缺点：貌似没啥缺点，比较折衷

4. 纯Hash表，这个就不用说了吧，把所有数据读到内存中，建立哈希表（一亿的话，哈希表不大，也就几个G）
   优点：时间复杂度O(1)，呵呵 插入复杂度O(1)
   缺点：内存占用。。。
   结论：除了需要花钱，所有性能都是No1

最终结论：

1. 源数据永不变动，那就第一方案
2. 不要求100%精确，那就第二方案
3. 有钱买内存，就第四方案
4. 普通人，第三方案

上面的几种方法逻辑都非常简单，实现起来很快的。有时间可以都实现下，测一测性能。

补充，Hash表到底有多快。。

生成1000w 随机字符串（单行长度32字节）

$ head -1 1000w
bCxshZTroH6OukITgLsCccK9SlBd7CHL

取后100条字符串（grep的最坏情况）

$ tail -100 1000w> q100
$ time (cat q100 | while read line;do grep -Fx $line 1000w >/dev/null;done)
 6.87s user 7.36s system 99% cpu 14.322 total

可以看到grep最坏性能是 7req/s，时间复杂度是O(n)

使用awk评估hash表的性能(awk的dict是hash表实现的）

$ time awk 'ARGIND==1{a[$0]}' 1000w
14.24s user 0.61s system 99% cpu 14.861 total 

可以看到哈希表的载入时间是15s，注意写成服务的话载入一次就够了，所以载入时间是不算的

查询性能，我们直接全量查询

$ time awk 'ARGIND==1{a[$0]} ARGIND>1&&($0 in a){print $0}' 1000w 1000w >/dev/null
27.88s user 0.73s system 99% cpu 28.734 total

hash表的性能是 10000000/(28.734 - 14.861) = 720824req/s 是grep的10w倍，时间复杂度是O(1)

Answer 2

本人算法比较差，给一个我的简单思路
用过git的都知道，git的object对象名就是一个哈希值(sha-1)的后38位，
git的objects目录里的子目录，是objects对象的哈希值的前两位
查找一个objects对象，先根据前两位找到对应目录，再去目录下找具体文件
如下是git objects目录下的部分显示：

00  06  0c  12  18  1e  24  2a  30  36  3c  42  48  4e  54  5a  60  66  6c  72  78  

这样就能保证数据被比较均匀的分散在不同的目录里

同理，你可以在你的数据库中创建一些这样的表
比如 md5_3e,md5_06,...
当你想查找 3eabecb5ff177ebadd305fe52e278d92df3754是否存在
首先看存在表md5_3e吗，如果存在，则继续在md5_3e里查看是否存在abecb5ff177ebadd305fe52e278d92df3754 这样的值

此方案中，每个表大概存储数据为30多万，给字段加上索引，查询速度肯定飞快的

这是我的思路，应该也算最简单的能实现需求的方法

Answer 3

楼主可以去研究下bit-map的相关东西，对你的问题很有帮助哦。

Answer 4

可以试下布隆过滤器，bloom filter，在判断一个元素是否属于某个集合时，有可能把不属于这个集合的元素误认为属于这个集合，但不会把属于这个集合的元素误认为不属于这个集合，不适合零错误的场景

Answer 5

可以試試基於二分法的存儲結構。

比如 B-樹等

詳見 http://blog.csdn.net/v_july_v/article/details/6530142

Answer 6

几万亿个密码都可以秒查，你可以看看 http://www.ttmd5.com