欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2023-12-25 19:49:33
...
采用那种存储最好?比如只需检测这个数据库中是否存在一个“9d97c57dfc685f9b10d8d1b944330c09”即可,返回true or false

回复内容:

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

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

  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的相关东西,对你的问题很有帮助哦。

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

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

比如 B-樹等

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

相关标签: php

上一篇:

下一篇: