去重效率对比:HashTree与BloomFilter

请注意,本文编写于 210 天前,最后修改于 147 天前,其中某些信息可能已经过时。

二者去重的效率从几个维度做了简单的对比

一、MD5码原理

1、MD5码简介

MD5讯息摘要演算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码杂凑函数,可以产生出一个128位元(16位元组)的散列值(hash value),用于确保信息传输完整一致。

2、MD5功能
  • 输入任意长度的信息,经过处理,输出为128位的信息(数字指纹)
  • 不同的输入得到的不同的结果(唯一性)
  • 由MD5码不能看到原文,即不可逆
  • MD5相当于超损压缩
3、MD5原理

image
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、算法简介

算法:

  1. 首先需要k个hash函数,每个函数可以把key散列成为1个整数
  2. 初始化时,需要一个长度为n比特的数组,每个比特位初始化为0
  3. 某个key加入集合时,用k个hash函数计算出k个散列值,并把数组中对应的比特位置为1
  4. 判断某个key是否在集合时,用k个hash函数计算出k个散列值,并查询数组中对应的比特位,如果所有的比特位都是1,认为在集合中。

优点:不需要存储key,节省空间

缺点:

  1. 算法判断key在集合中时,有一定的概率key其实不在集合中
  2. 无法删除

image
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_Tree1.7897s4471633071
MD5_SHA1_Tree4.4616s4471633071
BloomFilter0.4333s4471633071
实验算法平均实验时间单词量总数去除单词总数
MD5_Tree5.1712s199120178400
MD5_SHA1_Tree11.8915s199120178400
BloomFilter4.0211s199120178406
2、BloomFilter算法的哈希函数个数
哈希函数个数错误数错误单词率单词量总数去除单词总数所花费时间
13160.1587%1991201787160.8661s
2280.0141%1991201784281.4371s
390.0045%1991201784092.0398s
470.0035%1991201784072.6319s
560.0030%1991201784063.0578s
660.0030%1991201784063.6117s
760.0030%1991201784064.0211s
3、MD5_SHA1_Tree树的深度
MD5_Tree深度SHA1_Tree深度单词量总数去除单词总数所花费时间
10101991201784003.8420s
15151991201784005.8535s
20201991201784007.3574s
25251991201784009.5419s
30301991201784009.8669s
323519912017840011.8635s
324019912017840012.0854s
10401991201784008.3019s
32101991201784007.2578s
5401991201784007.6795s
3251991201784006.6093s
4、空间复杂度对比
算法所用内存(MB)单词量总数去除单词总数所花费时间
Bloom Filter(BitSize = 1 << 25, HashFuc = 4)4.1021991201783972.8720s
Bloom Filter(BitSize = 1 << 26, HashFuc = 4)8.2731991201783973.2647s
Bloom Filter(BitSize = 1 << 27, HashFuc = 4)16.2581991201783973.4571s
Bloom Filter(BitSize = 1 << 28, HashFuc = 4)32.2661991201783973.8581s
Bloom Filter(BitSize = 1 << 28, HashFuc = 5)32.2611991201783964.5075s
Bloom Filter(BitSize = 1 << 28, HashFuc = 6)32.1991991201783965.6712s
Bloom Filter(BitSize = 1 << 28, HashFuc = 7)32.2111991201783966.1807s
MD5_Tree(5位)15.3551991201785821.4704s
MD5_Tree(6位)22.8391991201784011.5527s
MD5_Tree(7位)29.8791991201783901.7214s
MD5_Tree(8位)37.1481991201783901.9458s
MD5_SHA1_Tree(4,4)15.7961991201789342.0936s
MD5_SHA1_Tree(4,5)23.0001991201784302.2481s
MD5_SHA1_Tree(5,4) :MD5 = 523.0621991201784272.1942s
MD5_SHA1_Tree(5,5) :MD5 = 530.1671991201783912.5586s
MD5_SHA1_Tree(5,6) :MD5 = 537.4061991201783902.7099s
MD5_SHA1_Tree(4,5) :SHA1 = 523.0201991201784302.3741s
MD5_SHA1_Tree(5,5) :SHA1 = 530.1671991201783912.5586s
MD5_SHA1_Tree(6,5) :SHA1 = 537.4141991201783902.7485s
MD5_SHA1_Tree(6,6)44.6641991201783902.8742s
MD5_SHA1_Tree_Pro(4,4)21.7141991201789342.1883s
MD5_SHA1_Tree_Pro(4,5)31.6321991201784302.3765s
MD5_SHA1_Tree_Pro(5,5)41.5941991201783912.577s
MD5_SHA1_Tree_Pro(5,6)51.6681991201783902.7406s
MD5_SHA1_Tree_Pro(6,5)52.1331991201784003.8420s
MD5_SHA1_Tree_Pro(7,7)59.2661991201784003.8420s
没有啦~ 下一篇 →
Comments

添加新评论

已有 2 条评论

感谢刘师傅的建议!

深入浅出,由表及里,感情丰富,总之一句话“主席tql”,望一起努力。另外建议把阅读全文的分割线拉上一点,否则主页上一条博客太长了,有失雅观