php - 1亿个32位的md5的密码值,怎样查询其中一个md5值是否存在效率最快?
PHPz
PHPz 2017-04-10 14:43:07
0
6
706

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

PHPz
PHPz

学习是最好的投资!

reply all (6)
Peter_Zhu

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

  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)

    刘奇

    本人算法比较差,给一个我的简单思路
    用过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多万,给字段加上索引,查询速度肯定飞快的

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

      刘奇

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

        Ty80

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

          黄舟

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

          比如 B-樹等

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

            PHPzhong

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

              Latest Downloads
              More>
              Web Effects
              Website Source Code
              Website Materials
              Front End Template
              About us Disclaimer Sitemap
              php.cn:Public welfare online PHP training,Help PHP learners grow quickly!