去重效率对比：HashTree与BloomFilter
2019-04-27 本文已影响0人
Muyun99
一、MD5码原理
1、MD5码简介
MD5讯息摘要演算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码杂凑函数，可以产生出一个128位元（16位元组）的散列值（hash value），用于确保信息传输完整一致。
2、MD5功能
- 输入任意长度的信息，经过处理，输出为128位的信息（数字指纹）
- 不同的输入得到的不同的结果（唯一性）
- 由MD5码不能看到原文,即不可逆
- MD5相当于超损压缩
3、MD5原理
image
简述：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
第一步、填充
如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)；
第二步、记录信息长度
用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N * 512+448+64=(N+1)*512位。
第三步、装入标准的幻数（四个整数）
标准的幻数（物理顺序）是
- A=(01234567)16
- B=(89ABCDEF)16
- C=(FEDCBA98)16
- D=(76543210)16
如果在程序中定义应该是:
- A=0X67452301L
- B=0XEFCDAB89L
- C=0X98BADCFEL
- D=0X10325476L
第四步、四轮循环运算
循环的次数是分组的个数（N+1）
1）将每一512字节细分成16个小组，每个小组64位（8个字节）
2）先认识四个线性函数(&是与,|是或,~是非,^是异或)
F(X, Y, Z)=(X & Y)|((~X) & Z)
G(X, Y, Z)=(X & Z)|(Y & (~Z))
H(X, Y, Z)=X ^ Y ^ Z
I(X, Y, Z)=Y ^ (X | (~Z))
3）设Mj表示消息的第j个子分组（从0到15）
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<<<s)
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<<<s)
4）四轮运算
第一轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)
第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)
5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。
二、bloom过滤器
1、简介
bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。
和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。
2、算法简介
算法：
- 首先需要k个hash函数，每个函数可以把key散列成为1个整数
- 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
- 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
- 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
优点：不需要存储key，节省空间
缺点：
- 算法判断key在集合中时，有一定的概率key其实不在集合中
- 无法删除
image
三、性能评价
32位MD5码：128bit --> 16byte
16位MD5码：64bit --> 8byte
内存：4GB = 4 * 1024 * 1024 * 1024 = 4294967296 byte
若用一位bit存放MD5码中的一位:
即4G内存大约能存放
- 268435456组32位MD5码
- 536870912组16位MD5码
四、实验结果性能对比
1、三种算法概述
| 实验算法 | 平均实验时间 | 单词量总数 | 去除单词总数 |
|---|---|---|---|
| MD5_Tree | 1.7897s | 44716 | 33071 |
| MD5_SHA1_Tree | 4.4616s | 44716 | 33071 |
| BloomFilter | 0.4333s | 44716 | 33071 |
| 实验算法 | 平均实验时间 | 单词量总数 | 去除单词总数 |
|---|---|---|---|
| MD5_Tree | 5.1712s | 199120 | 178400 |
| MD5_SHA1_Tree | 11.8915s | 199120 | 178400 |
| BloomFilter | 4.0211s | 199120 | 178406 |
2、BloomFilter算法的哈希函数个数
| 哈希函数个数 | 错误数 | 错误单词率| 单词量总数 | 去除单词总数 | 所花费时间 |
| --- | --- | -- | -- | --| -- | -- |
| 1 | 316 | 0.1587% | 199120 | 178716 | 0.8661s |
| 2 | 28 | 0.0141% | 199120 | 178428 | 1.4371s |
| 3 | 9 | 0.0045% |199120 | 178409 | 2.0398s |
| 4 | 7 | 0.0035% |199120 | 178407 | 2.6319s |
| 5 | 6 |0.0030% |199120 | 178406 | 3.0578s |
| 6 | 6 | 0.0030% |199120 | 178406 | 3.6117s |
| 7 | 6 | 0.0030% |199120 | 178406 | 4.0211s |
3、MD5_SHA1_Tree树的深度
| MD5_Tree深度 | SHA1_Tree深度 | 单词量总数 | 去除单词总数 | 所花费时间 |
|---|---|---|---|---|
| 10 | 10 | 199120 | 178400 | 3.8420s |
| 15 | 15 | 199120 | 178400 | 5.8535s |
| 20 | 20 | 199120 | 178400 | 7.3574s |
| 25 | 25 | 199120 | 178400 | 9.5419s |
| 30 | 30 | 199120 | 178400 | 9.8669s |
| 32 | 35 | 199120 | 178400 | 11.8635s |
| 32 | 40 | 199120 | 178400 | 12.0854s |
| 10 | 40 | 199120 | 178400 | 8.3019s |
| 32 | 10 | 199120 | 178400 | 7.2578s |
| 5 | 40 | 199120 | 178400 | 7.6795s |
| 32 | 5 | 199120 | 178400 | 6.6093s |
4、空间复杂度对比
| 算法 | 所用内存(MB) | 单词量总数 | 去除单词总数 | 所花费时间 |
|---|---|---|---|---|
| Bloom Filter(BitSize = 1 << 25, HashFuc = 4) | 4.102 | 199120 | 178397 | 2.8720s |
| Bloom Filter(BitSize = 1 << 26, HashFuc = 4) | 8.273 | 199120 | 178397 | 3.2647s |
| Bloom Filter(BitSize = 1 << 27, HashFuc = 4) | 16.258 | 199120 | 178397 | 3.4571s |
| Bloom Filter(BitSize = 1 << 28, HashFuc = 4) | 32.266 | 199120 | 178397 | 3.8581s |
| Bloom Filter(BitSize = 1 << 28, HashFuc = 5) | 32.261 | 199120 | 178396 | 4.5075s |
| Bloom Filter(BitSize = 1 << 28, HashFuc = 6) | 32.199 | 199120 | 178396 | 5.6712s |
| Bloom Filter(BitSize = 1 << 28, HashFuc = 7) | 32.211 | 199120 | 178396 | 6.1807s |
| MD5_Tree(5位) | 15.355 | 199120 | 178582 | 1.4704s |
| MD5_Tree(6位) | 22.839 | 199120 | 178401 | 1.5527s |
| MD5_Tree(7位) | 29.879 | 199120 | 178390 | 1.7214s |
| MD5_Tree(8位) | 37.148 | 199120 | 178390 | 1.9458s |
| MD5_SHA1_Tree(4,4) | 15.796 | 199120 | 178934 | 2.0936s |
| MD5_SHA1_Tree(4,5) | 23.000 | 199120 | 178430 | 2.2481s |
| MD5_SHA1_Tree(5,4) ：MD5 = 5 | 23.062 | 199120 | 178427 | 2.1942s |
| MD5_SHA1_Tree(5,5) ：MD5 = 5 | 30.167 | 199120 | 178391 | 2.5586s |
| MD5_SHA1_Tree(5,6) ：MD5 = 5 | 37.406 | 199120 | 178390 | 2.7099s |
| MD5_SHA1_Tree(4,5) ：SHA1 = 5 | 23.020 | 199120 | 178430 | 2.3741s |
| MD5_SHA1_Tree(5,5) ：SHA1 = 5 | 30.167 | 199120 | 178391 | 2.5586s |
| MD5_SHA1_Tree(6,5) ：SHA1 = 5 | 37.414 | 199120 | 178390 | 2.7485s |
| MD5_SHA1_Tree(6,6) | 44.664 | 199120 | 178390 | 2.8742s |
| MD5_SHA1_Tree_Pro(4,4) | 21.714 | 199120 | 178934 | 2.1883s |
| MD5_SHA1_Tree_Pro(4,5) | 31.632 | 199120 | 178430 | 2.3765s |
| MD5_SHA1_Tree_Pro(5,5) | 41.594 | 199120 | 178391 | 2.577s |
| MD5_SHA1_Tree_Pro(5,6) | 51.668 | 199120 | 178390 | 2.7406s |
| MD5_SHA1_Tree_Pro(6,5) | 52.133 | 199120 | 178400 | 3.8420s |
| MD5_SHA1_Tree_Pro(7,7) | 59.266 | 199120 | 178400 | 3.8420s |
