给你一个含有1亿个QQ号码的文件,如何快速的查找某个QQ号码?

井迪迪迪迪迪


一个个qq的文件放在一起,肯定很很很很小,要想找出来不是件很容易的事情,不过我有办法,就是买个显微镜把这个文件放在显微镜下,不就一下子找到来了吗!


圣爵无敌


我来捣乱一下,1亿个QQ号的文件,不用管他是怎么存放,放在那都行。

然后你只要告诉我你要找的那个qq号,我就能立即告诉你你要找的QQ号是什么。这个什么算法都不用。

好吧话回正题,1亿个QQ号,对应着什么?用一个QQ号是要确定在不在这个文件当中,还是说,这个文件里每个qq号都对应着一个昵称,要得到这个昵称呢?

这两种算法是完全不一样的,如果只需要确定是否存在,最价办法应该是布隆过滤器,只需要构建一个信息指纹的大文件,通过集群,可以把速度缩减到毫秒级。

如果是找对应关系,之前的信息指纹就不行了,如果想够快,依然需要一个集群,先按qq号的最大位数做一个大集合,然后把这1亿个qq号按对应位置存入集合,最后把这个集合按0xFF分解到对应的机器上,查找时,只要把QQ号换算成地址,就可以直接访问了,速也不慢,只是空间上比较浪费,实际做的时候,应该还会做一定的压缩,以避免空间浪费,但这就需要使用cpu时间了,极限速度挑战的话,应该不会用这个。


迷人的呆子


哈哈,我看了下都是扯犊子,什么文本直接点开,你试过没有。

我来给大家吹吹牛,大概是在15.16年左右,脱库非常猖狂,网上流传了各大网站平台的注册账号数据库,网易的,腾讯的,以及各种中小企业网站数据库,比如YY,那时候360云盘可以存40TB+的内容,我就逛各大黑客网站论坛,有幸搜集了多达38T的数据库资料以及视频,只要泄露了,基本上都被收集了,大多数dat这些数据库文件,需要******才能打开看,还有些是txt文件格式的,比如最出名的一个就是3亿QQ账号密码那个文件,整个文件有几G,如果按照其他答主的说法直接打开就行了,可以基本上点开就会卡死,打不开。

其实有很多种办法可以打开,最简单的一种,用****软件切割,把一个txt文件分割为几十个几百个几千个,比如分割为每个文件为100kb,或者把1开头的分成一个文件,分为多个。这样子你就能打开了,但是这样子分割好之后不用打开,搜集到一个目录用*****汇总搜索自己需要的就行了。还有一种就是用SQL server这些打开。当然还有其他方法就不一一阐述。

好了牛吹完了360云盘也封了给你们验证不了。。。就当吹牛的吧


欢乐深圳


1亿qq号,按照每个文qq号11位算,大概占用1.02g空间,因为数据量不大,可以全加载进内存。这样的话可以有好多方法。

第一种是内存映射文件,Windows内存映射文件可以映射磁盘上的大文件,别说1g,就算10g也没问题,然后操作就跟在内存操作一样,我之前试过500m的纯文本(打印的π),用c语言函数strstr查找字符串就能秒得结果,1g跟500m区别不大。

第二种方法,同样是建立在数据量不大的基础上,可以构造map存在内存中qq号就是key,因为map基于hash预算,查询效率非常高,也是秒得结果。

第三种存数据库,因为数据达到亿级,还是考虑oracle这种单表性能爆表的比较好,放mysql估计比较悬。

第四种可以用内存数据库,如redis,其中key存为qq号,人家专业干这个的,也是秒得结果。

第五种es,其实es干这个有点大材小用。


清风14518071


布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

基本思路如下:

如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的



互联网说事儿


我看了很多小伙伴的回答都说的还不错,但是很多都想当然的说的,我来说说真实案例,相信大家看了之后,对这一大类知识都有很全面的了解。

先科普一下QQ密码为什么会被泄露相关知识。只要是软件和网站就会存在漏洞,当这个漏洞被发现的时候相关公司就会紧急修复,但是有时候这个漏洞没有被发现或者只是个别的黑客发现没有公布出来,这个时候漏洞就叫0day漏洞。还有就是某些漏洞是没办法修复的,比如三次握手时候容易被抓取密码,所以腾讯有时候也没办法避免有漏洞,所以也曾被脱裤。

大概是13年左右时候,腾讯曾遭到黑客攻击,当然后面被紧急修复了。但是在这过程中大约有三亿QQ账号和密码被脱裤(脱裤是只黑客从窃取公司数据库相关信息),至此在各大黑客论坛网站都流传着一个3亿QQ数据库的文TXT文档,这个文档大约占2G内存,里面存在着3亿qq和对应的明文密码。这个是真实的,我有一个朋友也曾下载下来验证证明是真实的。

以这个文件为例,查看最有效的方案有两个。

1、txt文件切割,用txt文件切割器把这几G文件切割成100kb/50kb文件,因为单独一个几G的TXT文件你用电脑肯定打不开的,一定会卡死。所以切割成几十份几百份才能进行查看,当分割成几百份之后我们可以建立一个本地数据库,道理很简单,在自己电脑上新建一个文件夹,把这些切割好的txt文档归纳到这个文件夹,再用txt搜索软件**对这个文件夹进行搜索,比如搜索某个QQ,他就会出现相对应的QQ密码,这样子搭好了本地数据库并对里面的密码进行了查看。

2、存数据库,挂到mysql上。挂到mysql上之后我们就可以直接对数据库进行查看,当然也就可以检索某个数值了,甚至你还可以就行分类,比如1开头的QQ分类,比如对6/78位数的QQ进行分类,分类的原因就是便于管理,甚至便于做坏事儿,比如6位数的qq人那大都是很久之前的大老板了,再针对性的进行***,对吧,当然现在腾讯已经修复这个漏洞,你的密码也强制性换了,所以也几乎不存在因为这个原因你再被盗号的风险了。

对不起,太强的求生欲只能叙述成这样,本来可以更加简洁明了的解释,但我怕犯了忌讳。不单单QQ曾被脱库,流传于世最出名的是QQ群关系这个数据库,有了它之后,人肉就方便多了,只要通过搜索一个QQ就能查到这个人的同学群公司群兴趣群等等,以此为媒介跳板,能查到大片大片的用户。还有网易的、某某酒店的数据库非常多,因为确实是没有绝对安全的数据库,也不能怪这些个公司。

在刚才写完这篇回答之后,我又再去百度搜索相关裤子时候,没想到轻松地就搜到了,我已举报。请条友们不要去下载,没有意义,说不定已经被挂马了,当心中毒。了解网络安全知识是为了更好的保护好自己,保护未来的生活中信息不被窃取,请条友们一定要珍重。




IT老胡


我的实录是用bloom filter 或者cock filter 算法来实现快速查找QQ号,具体做法是每一个Qq号映射到内存的一个位,就像red is 的bitset ,这样1亿个位内存不过几百兆,完全胜任,以判断是否存在,你可以在GitHub收java. go或者你需要或者熟悉的语言的具体实现,跑一局程序即可,很高兴回答你的问题。谢谢


玉玺读书


如果是只查找一次,就用文本文件打开Ctrl+F。

如果以后需要经常查找,则采用以下方法:

第一步排序,自己开发一个排序函数。

第二步,采用折中法查找。一亿个号码,查找次数不会超过26次即可命中目标。

算法大概如下:

用数组装入已排好序的数据。

第一步:获取需要查找到号码。

第二步:获取数组第5000万个(一亿的中间)号码进行对比。

第三步:如果比要查找的号码大,则再取第7500万个号码(后半段的中间)进行比对。如果比要查找的号码小,则取第2500万个号码(前半段的中间)进行比对。

第四步:按第三步的方法循环,直到找到目标号码。

循环次数不会超过26次。


IT与隐私安全


最简单的,grep命令搞定。想加快,先split,再并行跑多个grep。另外一个办法,perl脚本,先把整个文件读入内存,在内存里操作速度很快,再一条条比对。qq号只有十多位,按16位算,16字节,3亿为48亿字节,大约4.8GB,对服务器来说小case


用户1362944465344


这是个比较有意思的问题,信息也比较模糊,首先,是在讨论检索的做法(比如用工具)还是在讨论检索的算法(自己写代码实现)。

假设在讨论检索的做法,那么最快的必然是ag了,the silver searcher,ag要比grep快得多,用ag在linux下检索一遍内核也是极快的,当然,如果是win系统就另说了。

假设在讨论检索算法,那么要先考虑检索是一次性的,还是以后还会再检索其他号码。

如果以后还会再检索其他号码,那么就首先对1亿个qq的文件进行处理,典型的方法比如是前导补0,让所有号码长度一致,再排序,然后按地址偏移做hash表存储,这种做法虽然首次处理需要耗时很长,但以后查询的话几乎是直接按照号码计算偏移来直接访问,速度极快,如果做1万次甚至1亿次检索的话,效率就体现出来了。

如果检索是一次性的,也就是1亿个号码的记录文件收到并仅检索一次的话,那么使用多线程分段暴力检索是我目前想到最快的方法了。因为任何的对记录文件的预处理工作都已经相当于把所有记录撸了一遍,有这个时间已经完成检索了。


分享到:


相關文章: