Jadual Kandungan
回复内容:
Rumah pembangunan bahagian belakang tutorial php 1亿个32位的md5的密码值,怎样查询其中一个md5值是否存在效率最快?

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

Jun 06, 2016 pm 08:46 PM
php

采用那种存储最好?比如只需检测这个数据库中是否存在一个“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字节)

<code>$ head -1 1000w
bCxshZTroH6OukITgLsCccK9SlBd7CHL
</code>
Salin selepas log masuk

取后100条字符串(grep的最坏情况)

<code>$ 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
</code>
Salin selepas log masuk

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

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

<code>$ time awk 'ARGIND==1{a[$0]}' 1000w
14.24s user 0.61s system 99% cpu 14.861 total 
</code>
Salin selepas log masuk

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

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

<code>$ 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
</code>
Salin selepas log masuk

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

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

<code>00  06  0c  12  18  1e  24  2a  30  36  3c  42  48  4e  54  5a  60  66  6c  72  78  
</code>
Salin selepas log masuk

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

同理,你可以在你的数据库中创建一些这样的表
比如 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

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

7 Fungsi PHP Saya Menyesal Saya Tidak Tahu Sebelum ini 7 Fungsi PHP Saya Menyesal Saya Tidak Tahu Sebelum ini Nov 13, 2024 am 09:42 AM

Jika anda seorang pembangun PHP yang berpengalaman, anda mungkin merasakan bahawa anda telah berada di sana dan telah melakukannya. Anda telah membangunkan sejumlah besar aplikasi, menyahpenyahpepijat berjuta-juta baris kod dan mengubah suai sekumpulan skrip untuk mencapai op

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Jelaskan JSON Web Tokens (JWT) dan kes penggunaannya dalam PHP API. Apr 05, 2025 am 12:04 AM

JWT adalah standard terbuka berdasarkan JSON, yang digunakan untuk menghantar maklumat secara selamat antara pihak, terutamanya untuk pengesahan identiti dan pertukaran maklumat. 1. JWT terdiri daripada tiga bahagian: header, muatan dan tandatangan. 2. Prinsip kerja JWT termasuk tiga langkah: menjana JWT, mengesahkan JWT dan muatan parsing. 3. Apabila menggunakan JWT untuk pengesahan di PHP, JWT boleh dijana dan disahkan, dan peranan pengguna dan maklumat kebenaran boleh dimasukkan dalam penggunaan lanjutan. 4. Kesilapan umum termasuk kegagalan pengesahan tandatangan, tamat tempoh, dan muatan besar. Kemahiran penyahpepijatan termasuk menggunakan alat debugging dan pembalakan. 5. Pengoptimuman prestasi dan amalan terbaik termasuk menggunakan algoritma tandatangan yang sesuai, menetapkan tempoh kesahihan dengan munasabah,

Bagaimana anda menghuraikan dan memproses HTML/XML dalam PHP? Bagaimana anda menghuraikan dan memproses HTML/XML dalam PHP? Feb 07, 2025 am 11:57 AM

Tutorial ini menunjukkan cara memproses dokumen XML dengan cekap menggunakan PHP. XML (bahasa markup extensible) adalah bahasa markup berasaskan teks yang serba boleh yang direka untuk pembacaan manusia dan parsing mesin. Ia biasanya digunakan untuk penyimpanan data

Program PHP untuk mengira vokal dalam rentetan Program PHP untuk mengira vokal dalam rentetan Feb 07, 2025 pm 12:12 PM

Rentetan adalah urutan aksara, termasuk huruf, nombor, dan simbol. Tutorial ini akan mempelajari cara mengira bilangan vokal dalam rentetan yang diberikan dalam PHP menggunakan kaedah yang berbeza. Vokal dalam bahasa Inggeris adalah a, e, i, o, u, dan mereka boleh menjadi huruf besar atau huruf kecil. Apa itu vokal? Vokal adalah watak abjad yang mewakili sebutan tertentu. Terdapat lima vokal dalam bahasa Inggeris, termasuk huruf besar dan huruf kecil: a, e, i, o, u Contoh 1 Input: String = "TutorialSpoint" Output: 6 menjelaskan Vokal dalam rentetan "TutorialSpoint" adalah u, o, i, a, o, i. Terdapat 6 yuan sebanyak 6

Terangkan pengikatan statik lewat dalam php (statik: :). Terangkan pengikatan statik lewat dalam php (statik: :). Apr 03, 2025 am 12:04 AM

Mengikat statik (statik: :) Melaksanakan pengikatan statik lewat (LSB) dalam PHP, yang membolehkan kelas panggilan dirujuk dalam konteks statik dan bukannya menentukan kelas. 1) Proses parsing dilakukan pada masa runtime, 2) Cari kelas panggilan dalam hubungan warisan, 3) ia boleh membawa overhead prestasi.

Apakah kaedah Magic PHP (__construct, __destruct, __call, __get, __set, dll) dan menyediakan kes penggunaan? Apakah kaedah Magic PHP (__construct, __destruct, __call, __get, __set, dll) dan menyediakan kes penggunaan? Apr 03, 2025 am 12:03 AM

Apakah kaedah sihir PHP? Kaedah sihir PHP termasuk: 1. \ _ \ _ Membina, digunakan untuk memulakan objek; 2. \ _ \ _ Destruct, digunakan untuk membersihkan sumber; 3. \ _ \ _ Call, mengendalikan panggilan kaedah yang tidak wujud; 4. \ _ \ _ Mendapatkan, melaksanakan akses atribut dinamik; 5. \ _ \ _ Set, melaksanakan tetapan atribut dinamik. Kaedah ini secara automatik dipanggil dalam situasi tertentu, meningkatkan fleksibiliti dan kecekapan kod.

See all articles