我们知道在列表中对数据项查找的复杂度是O(n),而利用二分查找的复杂度是O()。
而散列(Hashing)这种数据结构能使查找算法的复杂度降到O(1)这种常数级别,因为散列事先能知道要找的数据项应该在数据集的什么位置,就可以直接到那个位置看看数据项是否存在即可。那它是怎么做到这一点呢?答案在于散列表
散列表(hash table,又称哈希表)是一种数据集,其中数据项的存储方式尤其有利于将来快速的查找定位。散列表中的每一个存储位置,称为槽(slot),可以保存数据项,每个槽有一个唯一的名称。如下例子,一个包含11个槽的散列表,槽的名称分别为0~10,在插入数据项之前,每个槽的值都是None,表示空槽。
散列表而实现从数据项到存储槽名称的转换的,称为散列函数(hash function)。散列函数接受数据项作为参数,返回整数值0~10,表示数据项存储的槽号(名称)。
我们设计一个简单的散列函数,例如有数据项:54,26,93,17,77,31,有一种简单的散列方法是“求余数”,将数据项除以散列表的大小,得到的余数作为槽号,就可以将数据项存入相应的槽中。
所以本例中我们的散列函数是h(item) = item % 11,所以数据项将如下存储。
哈希表但是例子中的6个数据插入之后只占据了散列表11个槽的6个,所以负载因子为6/11。要查找某个数据项是否存在在表中,我们只需要使用同一个散列函数,对查找项进行计算,看看返回的槽好所对应的槽中是否有数据项就行。因此实现了O(1)时间复杂度的查找算法。
但是如果数据项再增加44,h(44)=0,它跟77被分配到同一个槽中,这种情况叫做“冲突collision”。如何解决冲突呢,这就需要完美散列函数。
给定一组数据项,如果一个散列函数能把每个数据项映射到不同的槽中,那么这个散列函数就可以称为“完美散列函数”。对于一组固定数据,总是能想办法设计除完美散列函数。但如果数据项经常性的变动,很难有一个系统性的方法来设计对应的完美散列函数。当然冲突也不是致命性的错误,我们会有办法处理的。
获得完美散列函数的一种方法是扩大散列表的容量,大到所有可能出现的数据项都能够占据不同的槽。(用空间换时间)但这种方法对数据项范围过大的情况并不适用,例如保存手机号11位数字,那完美散列函数要求散列表具有百亿个槽!!!会浪费太多存储空间。
所以好的散列函数需要具备如下特性:冲突最少、计算难度低、节约空间。
由于完美散列函数能够对任意不同的数据生成不同的散列值(长度固定),如果把散列值当作数据的“指纹”,要求具有唯一性,这种特性被广泛应用在数据的一致性校验上。
作为一致性校验的数据函数需要具备如下特性:
1、压缩性:任意长度的数据,得到的“指纹”长度固定
2、易计算性:即对原数据加密容易解密难
3、抗修改性:对原数据的微小改动,都会引起“指纹”的大改变
4、抗冲突性:已知原数据和“指纹”,要伪造相同指纹的数据是非常困难的
最著名的近似完美散列函数(哈希算法)是MD5和SHA系列函数。常见应用场景:后台保存加密形式的密码,用户输入密码后计算散列值并对比,无需保存密码的明文即可判定用户是否输入了正确的密码。
MD5(Message Digest)将任何长度的数据变换为固定长为128位(16字节)的“指纹”,128为二进制已经是一个极为巨大的数字空间:据说是地球沙粒的数量。
而SHA(secure Hash Algorithm)是另一组散列函数,包括SHA-0/SHA-1,输出散列值160位(20字节),SHA-256/SHA-224/SHA-512/SHA-384 分别输出256、224、512、384位。
而近年发现MD5/SHA-0/SHA-1三种散列函数能够以极特殊的情况来构造散列冲突(个别碰撞),而SHA-1已经被破解,SHA-3应用较少,目前应用广泛相对安全的是SHA-2算法。
python自带MD5和SHA系列的散列函数库:hashlib,包括了md5、sha1、sha224、sha256、sha384、sha512等6种散列函数。
使用方法如下:
hashlib库除了对单个字符串进行散列计算,还可以用update方法来对任意长的数据分部分来计算,且不管多大的数据都不会有内存不足的问题。
update方法完美散列函数(哈希算法)还可以用于其他的数据一致性校验,如判定数据文件一致性。例如用于网络文件下载完整性校验(相同不重复下载),为每个文件计算其散列值,仅对比其散列值即可得知是否下载文件内容相同,而不用对比两个文件的内容(数据流)这么复杂。
网友评论