php - 1亿个32位的md5的密码值，怎样查询其中一个md5值是否存在效率最快？
采用那种存储最好？比如只需检测这个数据库中是否存在一个“9d97c57dfc685f9b10d8d1b944330c09”即可，返回true or false
采用那种存储最好？比如只需检测这个数据库中是否存在一个“9d97c57dfc685f9b10d8d1b944330c09”即可，返回true or false
天蓬老师2017-04-10 14:45:07
你的业务模型不清晰，没法得到一个好的回答，我说几个方法并说明优缺点吧
排序并顺序存储到硬盘，就32bit32bit32bit去顺序存储即可。搜索采用最简单的二分查找（号称90%的程序员面试的时候写不出正确的二分查找，不过你可以找个现成的）。时间复杂度O(logn)，简直飞快无比
优点：速度很快，磁盘空间压缩到极限，无内存占用
缺点：需要先做一次全排列（还好，一劳永逸）很难加入新的索引值（每次加入都要重排列，关键是需要重写去dump磁盘）
结论：适合不再变动的数据
布隆过滤器。具体实现Google啊，比如这里有个Python版的实现
优点：速度比较快，良好的插入性能
缺点：有错误率，虽然可控
结论：适合不是100%精确的需求，适合经常变动的数据
分片（类似于1楼的办法）先哈希，然后取模，比如5000，拆分成5000个子文件。然后各子文件分别排序。查找时对key做hash并取模，找到对应的子文件，然后再二分查找。当然MD5一般可以认为是哈希均匀的，那么就不用哈希，直接取模就好了。
优点：速度不错且插入性能还可以（单次插入只用对单个分片进行插入排序）
缺点：貌似没啥缺点，比较折衷
纯Hash表，这个就不用说了吧，把所有数据读到内存中，建立哈希表（一亿的话，哈希表不大，也就几个G）
优点：时间复杂度O(1)，呵呵 插入复杂度O(1)
缺点：内存占用。。。
结论：除了需要花钱，所有性能都是No1
最终结论：
上面的几种方法逻辑都非常简单，实现起来很快的。有时间可以都实现下，测一测性能。
补充，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)
怪我咯2017-04-10 14:45:07
本人算法比较差，给一个我的简单思路
用过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多万，给字段加上索引，查询速度肯定飞快的
这是我的思路，应该也算最简单的能实现需求的方法
PHP中文网2017-04-10 14:45:07
可以试下布隆过滤器，bloom filter，在判断一个元素是否属于某个集合时，有可能把不属于这个集合的元素误认为属于这个集合，但不会把属于这个集合的元素误认为不属于这个集合，不适合零错误的场景
黄舟2017-04-10 14:45:07
可以試試基於二分法的存儲結構。
比如 B-樹等
詳見 http://blog.csdn.net/v_july_v/article/details/6530142
