-
2021-03-31 16:21:32
转载自:
常用哈希函数介绍
哈希函数介绍
什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为什么在哈希表中搜索数据的时间复杂度会被认为是"平均为O(1)的复杂度".
在讲解具体内容前,首先我们要清楚以下几个概念:
冲突(碰撞) 对于不同的关键字ki、kj,若ki != kj,但H(ki) = H(kj)的现象叫冲突(collision) ,即不同的输入却有相同的输出。我们应该尽量避免冲突,因为冲突不仅会使我们在查找的时候效率变慢,还甚至会被攻击者利用从而大量消耗系统资源。 至于冲突的解决方案有很多种,具体可以参考这篇添加哈希表针对冲突的两种方式优缺点是什么?。
哈希函数的应用
哈希算法广泛应用于很多场景,例如安全加密和数据结构中哈希表的查找,布隆过滤器和负载均衡(一致性哈希)等等。 下面介绍几个常用的哈希算法。
加密哈希算法
在安全方面应用主要体现在以下三个方面: (1) 文件校验 (2) 数字签名 (3) 鉴权协议
在nodejs中我们可以使用原生crypto模块对数据进行加密,crypto.getHashes()查看支持的哈希算法。
const crypto = require('crypto'); console.log(crypto.getHashes()); /* [ 'DSA', 'DSA-SHA', 'DSA-SHA1', 'DSA-SHA1-old', 'RSA-MD4', 'RSA-MD5', 'RSA-MDC2', 'RSA-RIPEMD160', 'RSA-SHA', 'RSA-SHA1', 'RSA-SHA1-2', 'RSA-SHA224', 'RSA-SHA256', 'RSA-SHA384', 'RSA-SHA512', 'dsaEncryption', 'dsaWithSHA', 'dsaWithSHA1', 'dss1', 'ecdsa-with-SHA1', 'md4', 'md4WithRSAEncryption', 'md5', 'md5WithRSAEncryption', 'mdc2', 'mdc2WithRSA', 'ripemd', 'ripemd160', 'ripemd160WithRSA', 'rmd160', 'sha', 'sha1', 'sha1WithRSAEncryption', 'sha224', 'sha224WithRSAEncryption', 'sha256', 'sha256WithRSAEncryption', 'sha384', 'sha384WithRSAEncryption', 'sha512', 'sha512WithRSAEncryption', 'shaWithRSAEncryption', 'ssl2-md5', 'ssl3-md5', 'ssl3-sha1', 'whirlpool' ] */
除了我们常用的md5,sha-1,sha-2族外,还有像DSA-SHA1,RSA-SHA1,sha1WithRSAEncryption,其中sha1WithRSAEncryption和RSA-SHA1等价,DSA和RSA都是加密算法,DSA和RSA的区别在于,DSA用于签名,而RSA可用于签名和加密。
下面简单介绍下几种比较常用的加密哈希算法:
1、 MD5 MD5即Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一,主流编程语言普遍已有MD5实现。将数据(如汉字)运算为另一固定长度值,是杂凑算法的基础原理,MD5的前身有MD2、MD3和MD4。 MD5是输入不定长度信息,输出固定长度128-bits的算法。经过程序流程,生成四个32位数据,最后联合起来成为一个128-bits散列。基本方式为,求余、取余、调整长度、与链接变量进行循环运算。得出结果。 NodeJS中使用MD5:
var hash = crypto.createHash('md5'); hash.update('test'); console.log(hash.digest('hex')); // 098f6bcd4621d373cade4e832627b4f6 var hash = crypto.createHash('md5'); hash.update('test1'); console.log(hash.digest('hex')); // 5a105e8b9d40e1329780d62ea2265d8a
MD5一度被广泛应用于安全领域。但是在2004年王小云教授公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术,在数个小时内就可以找到MD5碰撞。使本算法不再适合当前的安全环境。目前,MD5计算广泛应用于错误检查。例如在一些BitTorrent下载中,软件通过计算MD5和检验下载到的碎片的完整性。
2、SHA-1 SHA-1曾经在许多安全协议中广为使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被视为是MD5的后继者。 SHA-1是如今很常见的一种加密哈希算法,HTTPS传输和软件签名认证都很喜欢它,但它毕竟是诞生于1995年的老技术了(出自美国国安局NSA),已经渐渐跟不上时代,被破解的速度也是越来越快。 微软在2013年的Windows 8系统里就改用了SHA-2,Google、Mozilla则宣布2017年1月1日起放弃SHA-1。 当然了,在普通民用场合,SHA-1还是可以继续用的,比如校验下载软件之类的,就像早已经被淘汰的MD5。
var hash = crypto.createHash('sha1'); hash.update('test'); console.log(hash.digest('hex')); // a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
3、SHA-2 SHA-224、SHA-256、SHA-384,和SHA-512并称为SHA-2。 新的哈希函数并没有接受像SHA-1一样的公众密码社区做详细的检验,所以它们的密码安全性还不被大家广泛的信任。 虽然至今尚未出现对SHA-2有效的攻击,它的算法跟SHA-1基本上仍然相似;因此有些人开始发展其他替代的哈希算法。
var hash = crypto.createHash('sha256'); hash.update('test'); console.log(hash.digest('hex')); // 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
4、SHA-3 SHA-3,之前名为Keccak算法,是一个加密杂凑算法。 由于对MD5出现成功的破解,以及对SHA-0和SHA-1出现理论上破解的方法,NIST感觉需要一个与之前算法不同的,可替换的加密杂凑算法,也就是现在的SHA-3。
5、RIPEMD-160 RIPEMD-160 是一个 160 位加密哈希函数。 它旨在用于替代 128 位哈希函数 MD4、MD5 和 RIPEMD。 RIPEMD-160没有输入大小限制,在处理速度方面比SHA2慢。 安全性也没SHA-256和SHA-512好。
var hash = crypto.createHash('ripemd160'); hash.update('test'); console.log(hash.digest('hex')); // 5e52fee47e6b070565f74372468cdc699de89107
其它加密算法相关
nodejs除了提供常用加密算法,还提供了HMAC(密钥相关的哈希运算消息认证,类似加盐处理),对称加密算法Cipher(加密)和Decipher(解密),非对称加密算法Signer(签名)和Verify(验证),这里篇幅太长,详细可以参考这几篇讲解得很详细的文章:
Node.js加密算法库Crypto
浅谈nodejs中的Crypto模块
浅谈nodejs中的Crypto模块(补完)查找哈希算法
下面列举几个目前在查找方面比较快的哈希算法(不区分先后),比较老的或者慢的就没举例了,毕竟篇幅有限。
1、lookup3 Bob Jenkins在1997年发表了一篇关于哈希函数的文章《A hash function for hash Table lookup》,这篇文章自从发表以后现在网上有更多的扩展内容。这篇文章中,Bob广泛收录了很多已有的哈希函数,这其中也包括了他自己所谓的“lookup2”。随后在2006年,Bob发布了lookup3。 Bob很好的实现了散列的均匀分布,但是相对来说比较耗时,它有两个特性,1是具有抗篡改性,既更改输入参数的任何一位都将带来一半以上的位发生变化,2是具有可逆性,但是在逆运算时,它非常耗时。
2、Murmur3 murmurhash是 Austin Appleby于2008年创立的一种非加密哈希算法,适用于基于哈希进行查找的场景。murmurhash最新版本是MurMurHash3,支持32位、64位及128位值的产生。 MurMur经常用在分布式环境中,比如Hadoop,其特点是高效快速,但是缺点是分布不是很均匀。
3、FNV-1a FNV又称Fowler/Noll/Vo,来自3位算法设计者的名字(Glenn Fowler、Landon Curt Noll和Phong Vo)。FNV有3种:FNV-0(已过时)、FNV-1、FNV-1a,后两者的差别极小。FNV-1a生成的哈希值有几个特点:无符号整形;哈希值的bits数,是2的n次方(32, 64, 128, 256, 512, 1024),通常32 bits就能满足大多数应用。
4、CityHash 2011年,google发布CityHash(由Geoff Pike 和Jyrki Alakuijala编写),其性能好于MurmurHash。 但后来CityHash的哈希算法被发现容易受到针对算法漏洞的攻击,该漏洞允许多个哈希冲突发生。
5、SpookyHash 又是Bob Jenkins哈希牛人的一巨作,于2011年发布的新哈希函数性能优于MurmurHash,但是只给出了128位的输出,后面发布了SpookyHash V2,提供了64位输出。
6、FarmHash FarmHash也是google发布的,FarmHash从CityHash继承了许多技巧和技术,是它的后继。FarmHash声称从多个方面改进了CityHash。
7、xxhash xxhash由Yann Collet发表,http://cyan4973.github.io/xxHash/ ,这是它的官网,据说性能很好,似乎被很多开源项目使用,Bloom Filter的首选。
查找哈希函数的性能比较
一般性能好的哈希算法都会根据不同系统做优化。 这里有一篇文章详细介绍了各种非加密哈希的性能比较(More Hash Function Tests )。
文章详细列出了各个平台(甚至包括手机和XBOXOne以及asm.js)之间的哈希算法性能比较,同时也对不同输入数据量做了对比。 似乎在跨平台使用方面CityHash64在64位系统性能最佳,而xxHash32在32位系统性能最好。 在数据量大方面,不同平台也有不同的选择 Intel CPU:总体来说xxhash64更好,随之FarmHash64(如果使用了SSE4.2),xxHash32更适合32位系统。 苹果手机CPU(A9):CityHash64在64位系统性能最佳,而xxHash32在32位系统性能最好。 SpookyV2更适合在XBOXOne中使用。 而短字符串输入使用FNV-1a性能最优(在pc,手机和XBOX中少于8字节,在asm.js中少于20字节),而且它的实现很简单。
哈希函数的分类
介绍了那么多哈希函数,实际上哈希函数主要分为以下几类:
1、加法Hash; 所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果,prime是素数。
function addictiveHash(key = '', prime){ let hash = 0; for(let i = 0; i < key.length; ++i){ hash += key.charCodeAt(i); } return hash % prime; } console.log(addictiveHash('test', 31)); // 14 console.log(addictiveHash('abc', 31)); // 15 console.log(addictiveHash('abb', 31)); // 14
2、位运算Hash; 这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。
function rotatingHash(key = '', prime) { let hash = 0; for (let i = 0; i < key.length; ++i) { hash = (hash << 4) ^ (hash >> 28) ^ key.charCodeAt(i); } return (hash % prime); } console.log(rotatingHash('test', 31)); // 13 console.log(rotatingHash('abc', 31)); // 23 console.log(rotatingHash('abb', 31)); // 22
3、乘法Hash; 这样的类型的哈希函数利用了乘法的不相关性.乘法哈希里最有名的就是adler32,reactJS的checksum校验就是使用的adler32的改良版。 facebook/react
function adler32(str) { var a = 1, b = 0, L = str.length, M = 0, c = 0, d = 0; for (var i = 0; i < L;) { M = Math.min(L - i, 3850); while (M > 0) { c = str.charCodeAt(i++); if (c < 0x80) { a += c; } else if (c < 0x800) { a += 192 | ((c >> 6) & 31); b += a; --M; a += 128 | (c & 63); } else if (c >= 0xD800 && c < 0xE000) { c = (c & 1023) + 64; d = str.charCodeAt(i++) & 1023; a += 240 | ((c >> 8) & 7); b += a; --M; a += 128 | ((c >> 2) & 63); b += a; --M; a += 128 | ((d >> 6) & 15) | ((c & 3) << 4); b += a; --M; a += 128 | (d & 63); } else { a += 224 | ((c >> 12) & 15); b += a; --M; a += 128 | ((c >> 6) & 63); b += a; --M; a += 128 | (c & 63); } b += a; --M; } a = (15 * (a >>> 16) + (a & 65535)); b = (15 * (b >>> 16) + (b & 65535)); } return ((b % 65521) << 16) | (a % 65521); } console.log(adler32('test', 31)); // 73204161 console.log(adler32('abc', 31)); // 38600999 console.log(adler32('abb', 31)); // 38535462
4、除法Hash; 和乘法一样用了不相关性,但性能不好。
5、查表Hash; 查表Hash最有名的样例莫过于CRC系列算法。尽管CRC系列算法本身并非查表,可是,查表是它的一种最快的实现方式。以下是CRC32的实现:
function signed_crc_table() { var c = 0, table = new Array(256); for(var n =0; n != 256; ++n){ c = n; c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1)); table[n] = c; } return typeof Int32Array !== 'undefined' ? new Int32Array(table) : table; } var T = signed_crc_table(); function crc32(str, seed) { var C = seed ^ -1; for(var i = 0, L=str.length, c, d; i < L;) { c = str.charCodeAt(i++); if(c < 0x80) { C = (C>>>8) ^ T[(C ^ c)&0xFF]; } else if(c < 0x800) { C = (C>>>8) ^ T[(C ^ (192|((c>>6)&31)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF]; } else if(c >= 0xD800 && c < 0xE000) { c = (c&1023)+64; d = str.charCodeAt(i++)&1023; C = (C>>>8) ^ T[(C ^ (240|((c>>8)&7)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|((c>>2)&63)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|((d>>6)&15)|((c&3)<<4)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|(d&63)))&0xFF]; } else { C = (C>>>8) ^ T[(C ^ (224|((c>>12)&15)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|((c>>6)&63)))&0xFF]; C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF]; } } return C ^ -1; } console.log(crc32('test', 31)); // -804963899 console.log(crc32('abc', 31)); // 576628111 console.log(crc32('abb', 31)); // 1431934233
查表Hash中有名的样例有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。
6、混合Hash; 混合Hash算法利用了以上各种方式。各种常见的Hash算法,比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。
哈希函数的选择
那么多种哈希函数,我们究竟该选择哪种呢? 不同的应用场景对哈希的算法设计要求也不一样,但一个好的哈希函数应该具备以下三点:
- 抗碰撞性,尽量避免冲突。
- 抗篡改性,只要改动一个字节,其哈希值也会很大不同。
- 查找效率。
在加密方面,哈希函数应该对抗碰撞性和抗篡改性要求很高,而会牺牲查找效率。 而且随着时代的变化我们最好还是选择更现代化的哈希函数。 目前来说我们可以选择SHA-2族用于安全加密中,SHA-3更安全但对性能损耗更大。更保险的做法是加盐后混合加密。 在nodejs中我们可以很方便地用crypto.pbkdf2()函数加盐加密,默认会调用hmac算法,用sha-1进行加密,并且可以设置迭代次数和密文长度。常用于用户注册和登录校验流程中。下面的例子我们用伪随机函数randomBytes()生成16字节的盐(更安全的做法是多于16字节)
const crypto = require('crypto'); let txt = 'test'; //通过伪随机码生成salt,进行加密 crypto.randomBytes(128, function (err, salt) { if (err) throw err; salt = salt.toString('hex'); console.log(salt); //生成salt crypto.pbkdf2(txt, salt, 4096, 256, function (err,hash) { if (err) throw err; hash = hash.toString('hex'); console.log(hash);//生成密文 }) }) /* 6e5e20869916c5aea5f6188807abb0dcd83ca0d3c21ec880bab71c483e7cca624af8c5b6fe2ec820e296452e6e43476 98411aa545d4c3a21056e02659446b694383b3eedd3a7cbcb9592ede2d5875206f6b764fee69e65271c99d73b818837 9d0c92e345b046d760b84954babd6740b6928e76ef86e9bfd07c2867837678b575 (node:1264) DeprecationWarning: crypto.pbkdf2 without specifying a digest is deprecated. Please specify a digest 4572e319f6f5e05ee2507dacc43cd9c6f970e1ed37e76c2a86c99afde11c75f35f04322ee3fec4775a21f1181c0e357 d00bdf1f1aef4cffe9f11f7859fea658df76553ae37deacc5e085d5e7e38a13ec0f7b0d8f29d738f0cd00cddbd74493 53547eb651244a6c3e599d86878f80e1be2d269afd3d9ea678982150163fa9e61385f40fabedae2403085e8432a723e da8693466068523c9e26afdd0764a21d2372bde7f607af6bcbc8fd4a325ad942688ee770efdf038332a470b7ed7c49e 7c9b0f8d6a1f9557dd51c3747ac4a7ecabda7089d5685403e6af525de5f84d0b4d7a53ea1fb879afa2cfee4a60775b5 39614ef451de2dd1ca995a14a79c4236d6089 */
而在查找方面,哈希函数更追求查找的效率和良好的抗碰撞性。 短字符串输入使用FNV-1a,数量大的在32位系统使用xxhash,64位系统使用FarmHash。
更多相关内容 -
哈希原理与常见哈希函数
2020-01-09 18:11:06转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...一,什么是哈希
哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。
转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。1.哈希特点
(1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。
F(x)=rand() :每次返回一个随机值,是不好的哈希
(2)散列性:不同的值的哈希值尽量不同,理想情况下每个值对应于不同的数字。
F(x)=1 : 不管输入什么都返回1,是不好的哈希
2.冲突怎么解决
把一个大的集合映射到一个固定大小的集合中,肯定是存在冲突的。这个是抽屉原理或者叫鸽巢理论。
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。
(1)拉链法:
链表地址法是使用一个链表数组来存储相应数据,当hash遇到冲突的时候依次添加到链表的后面进行处理。Java里的HashMap是拉链法解决冲突的典型应用场景。
Java8的HashMap中,使用一个链表数组来存储数据,根据元素的哈希值确定存储的数组索引位置,当冲突时,就链接到元素后面形成一个链表,Java8中当链表长度超过8的时候就变成红黑树以优化性能,红黑树也可以视为拉链法的一种变形。
(2)开放地址法
开放地址法是指大小为 M 的数组保存 N 个键值对,其中 M >N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。
线性探测法,就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。简单来说就是:一旦发生冲突,就去寻找下 一个空的散列表地址,只要散列表足够大,空的散列地址总能找到。
Java8中的HashTable就是用线性探测法来解决冲突的。
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; }
(2)冲突解决示例
举个例子,假如散列长度为8,哈希函数是:y=x%7。两种解决冲突的方式如下:
拉链法解决冲突
线性探测法解决冲突
二,几个常见哈希算法
1.MD5
MD5哈希算法是将任意字符散列到一个长度为128位的Bit数组中,得出的结果表示为一个32位的十六进制数字。
MD5哈希算法有以下几个特点:
- 正像快速:原始数据可以快速计算出哈希值
- 逆向困难:通过哈希值基本不可能推导出原始数据
- 输入敏感:原始数据只要有一点变动,得到的哈希值差别很大
- 冲突避免:很难找到不同的原始数据得到相同的哈希值
算法过程:
- 数据填充:
将原数据的二进制值进行补齐。
(1)填充数据:使得长度模除512后得到448,留出64个bit来存储原信息的长度。填充规则是填充一个1,后面全部是0。
(2)填充长度数据:计算原数据的长度数据,填充到最后的64个bit上,如果消息长度数据大于64bit就使用低64位的数据。
- 迭代计算:
将填充好的数据按照每份512的长度进行切分,对每一份依次进行处理,每份的处理方式是使用四个函数进行依次进行计算,每个函数都有四个输入参数,输出也是四个数字,输出的数字作为下一份数据的输入,所有份数的数据处理完毕,得到的四个数字连接起来就是最终的MD5值。
以下图片是整个迭代计算的过程示意图,其中四个初始参数和四个函数定义如下:
//四个初始参数值 A=0x67452301; B=0xefcdab89; C=0x98badcfe; D=0x10325476; //四个函数的定义 // a、b、c、d是每次计算时候的四个参数 F=(b&c)|((~b)&d); F=(d&b)|((~d)&c); F=b^c^d; F=c^(b|(~d));
- md5的java实现
package com.chybin.algorithm.chapter2; /** * Create By 鸣宇淳 on 2019/12/26 **/ public class MD5{ /* *四个链接变量 */ private final int A=0x67452301; private final int B=0xefcdab89; private final int C=0x98badcfe; private final int D=0x10325476; /* *ABCD的临时变量 */ private int Atemp,Btemp,Ctemp,Dtemp; /* *常量ti *公式:floor(abs(sin(i+1))×(2pow32) */ private final int K[]={ 0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee, 0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8, 0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193, 0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51, 0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8, 0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905, 0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681, 0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60, 0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05, 0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244, 0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92, 0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314, 0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391}; /* *向左位移数,计算方法未知 */ private final int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7, 12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20, 4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10, 15,21,6,10,15,21,6,10,15,21,6,10,15,21}; /* *初始化函数 */ private void init(){ Atemp=A; Btemp=B; Ctemp=C; Dtemp=D; } /* *移动一定位数 */ private int shift(int a,int s){ return(a<<s)|(a>>>(32-s));//右移的时候,高位一定要补零,而不是补充符号位 } /* *主循环 */ private void MainLoop(int M[]){ int F,g; int a=Atemp; int b=Btemp; int c=Ctemp; int d=Dtemp; for(int i = 0; i < 64; i ++){ if(i<16){ F=(b&c)|((~b)&d); g=i; }else if(i<32){ F=(d&b)|((~d)&c); g=(5*i+1)%16; }else if(i<48){ F=b^c^d; g=(3*i+5)%16; }else{ F=c^(b|(~d)); g=(7*i)%16; } int tmp=d; d=c; c=b; b=b+shift(a+F+K[i]+M[g],s[i]); a=tmp; } Atemp=a+Atemp; Btemp=b+Btemp; Ctemp=c+Ctemp; Dtemp=d+Dtemp; } /* *填充函数 *处理后应满足bits≡448(mod512),字节就是bytes≡56(mode64) *填充方式为先加一个0,其它位补零 *最后加上64位的原来长度 */ private int[] add(String str){ int num=((str.length()+8)/64)+1;//以512位,64个字节为一组 int strByte[]=new int[num*16];//64/4=16,所以有16个整数 for(int i=0;i<num*16;i++){//全部初始化0 strByte[i]=0; } int i; for(i=0;i<str.length();i++){ strByte[i>>2]|=str.charAt(i)<<((i%4)*8);//一个整数存储四个字节,小端序 } strByte[i>>2]|=0x80<<((i%4)*8);//尾部添加1 /* *添加原长度,长度指位的长度,所以要乘8,然后是小端序,所以放在倒数第二个,这里长度只用了32位 */ strByte[num*16-2]=str.length()*8; return strByte; } /* *调用函数 */ public String getMD5(String source){ init(); int strByte[]=add(source); for(int i=0;i<strByte.length/16;i++){ int num[]=new int[16]; for(int j=0;j<16;j++){ num[j]=strByte[i*16+j]; } MainLoop(num); } return changeHex(Atemp)+changeHex(Btemp)+changeHex(Ctemp)+changeHex(Dtemp); } /* *整数变成16进制字符串 */ private String changeHex(int a){ String str=""; for(int i=0;i<4;i++){ str+=String.format("%2s", Integer.toHexString(((a>>i*8)%(1<<8))&0xff)).replace(' ', '0'); } return str; } /* *单例 */ private static MD5 instance; public static MD5 getInstance(){ if(instance==null){ instance=new MD5(); } return instance; } private MD5(){}; public static void main(String[] args){ String str=MD5.getInstance().getMD5("123"); System.out.println(str); } }
2.SHA
SHA类似MD5,也是一种信息摘要算法,也是将任意长度的字符串转换为固定长度的数字的算法。SHA算法是一个家族,有五个算法:SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512。这些变体除了生成摘要的长度、循环运行的次数等一些微小差异外,算法的基本结构是一致的。
SHA-1算法的结果是一个160个bit的数字,比MD5的128个bit要长32位,碰撞几率要低了2^32倍。可是SHA-1和MD5一样已经被人破解,已经不安全了。
SHA-256从名字上看就表明了它的值存储在长度为256的bit数组中的,SHA-512信息摘要长度是512个bit。
SHA-224是SHA256的精简版本,SHA-384是SHA-512的精简版本,精简版本主要用在安全等级要求不太高的场景,比如只是验证下文件的完整性。使用什么版本的SHA取决于安全要求和算法速度,毕竟长度越长算法计算时间约长,但是安全等级高。
SHA算法过程:
SHA算法的底层原理和MD5很相似,只是在摘要分段和处理细节上有少许差别,他们都是第一步将原数据进行填充,填充到512的整数倍,填充的信息包括10数据填充和长度填充,第二步切分为相同大小的块,第三步进行对每一块迭代,每块进行N轮运算,最终得到的值拼接起来就是最终的哈希值。
以下是MD5、SHA-1、SHA-2系列的算法过程比较:
MD5算法过程示意图:
MD5是对每一块数据分为四个部分,用四个函数进行运算。最终生成128位的哈希值。
SHA-1算法过程示意图:
SHA-1是将每一块数据分为五个部分。
SHA-2算法过程示意图:
SHA-2是分为八个部分,算法也更加复杂。
3.SimHash
SimHash是Google提出的一种判断文档是否重复的哈希算法,他是将文本转换为一个64位的哈希值,然后计算两个哈希值的距离,如果小于n(n一般是3)就认为这两个文本是相似的。
之所以能够这样判断是否相似是因为SimHash算法不同于MD5之类的算法,SimHash算法是局部敏感的哈希算法,MD5算法是全局敏感的哈希算法。在MD5中原数据只要有一个字符的变化,哈希值就会变化很大,而在SimHash算法中,原数据变化一小部分,哈希值也只有很小一部分的变化,所以只要哈希值很类似,就意味着原数据就很类似。
算法实现:
参考这个博客【[Algorithm] 使用SimHash进行海量文本去重】
(1)第一步:哈希
- 分词: 将文本进行分词,并给单词分配权重。
- hash: 对每个次进行hash计算,得到哈希值。
- 加权: 对每个单词的has进行加权。
- 合并: 把上一步加权hash值合并累计起来。
- 降维: 把上一步累加起来的值变为01。如果每一位大于0 记为 1,小于0 记为 0。
(2)第二步:计算海明距离
两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。
举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。
异或就是如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。两个simhash值进行异或,得出的结果中1的个数就是海明距离。
判断两个文本是否相似,就计算两个simhash哈希值的海明距离,根据经验,如果海明距离小于3就可以判定两个文本是相似的。
4.GeoHash
GeoHash 算法将经纬度哈希为一个数字,然后将数字base32编码为一个字符串。
比如:北海公园的经纬度是:(39.928167,116.389550),对应的GeoHash值可以为wx4g、wx4g0、wx4g0s、wx4g0s8、wx4g0s8q。GeoHash值代表的是这个经纬度点所在的一个矩形区域,长度越长矩形面积约小,表示的越精确。
两个位置的GeoHash值前部分一样的位数越多,说明两个位置离得越近,百度地图的查找附近、滴滴打车查找附近的车辆功能就可以使用这个算法。
GeoHash算法过程
下面对于北海公园的经纬度(39.928167,116.389550)进行编码,了解下算法过程。
(1)第一步:纬度编码
将整个地球从水平方向上进行逐步切分,确定纬度39.928167在哪个区域中。
纬度范围是-90到90,每次平均分为两份,进行逐步细化地迭代。
- 第一次迭代:处于-90到0的标记为0,0到90的标记为1,39.928167处于1的区间,所以最终结果的第一位是1。
- 第二次迭代:对上一步标记为1的部分平分,0到45标记为0,45到90标记为1,39.928167标记为1处于0的区间,所以最终结果的第二位是0。
- 第三次迭代:对上一步标记为0的部分平分,0到22.5标记为0,22.5到45标记为1,39.928167标记为1处于0的区间,所以最终结果的第三位是0
- 第四次迭代:对上一步标记为0的部分平分,22.5到33.75标记为0,33.75到45标记为1,39.928167标记为1处于1的区间,所以最终结果的第三位是1。
经过N次迭代后,得到一个长度为N的二进制值,比如得到的值为1011100011,这个就是对纬度进行的编码最终值。
(2)第二步:经度编码
对经度的编码过程跟对纬度编码过程十分类似,不同点是经度范围是-180到180,对经度116.389550经过N次迭代后得到编码值。比如得到1101001011。这个就是对经度编码的最终值。
(3)第三步:合并经纬度
对纬度编码值、经度编码值进行合并,合并规则是奇数位放纬度、偶数位放经度,合并为一个新的二进制串。
(4)第四步:转换为字符串
将上一步合并的二进制11100 11101 00100 01111每5位一段转换为十进制,结果是28、29、4、15,Base32编码后为wx4g。这个就是北海公园的经纬度(39.928167,116.389550)最终的GeoHash编码值。
以下图表是二进制数字、base32字符对应表:
Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Base 32 0 1 2 3 4 5 6 7 8 9 b c d e f Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Base 32 h j k m n p q r s t u v w x y -
什么是哈希函数?|哈希表(hash table)的原理——【python数据结构】
2020-05-17 19:02:57一,什么是哈希函数? 二,哈希碰撞(hash collision)的解决方式 三,什么是好的哈希函数? 四,哈希函数的构造方法 五,哈希表(hash table)原理目录
一,什么是哈希函数?
二,哈希表(hash table)原理
三,为什么不是所有的 hash 函数都可以被用来加密?
四,哈希碰撞(hash collision)的解决方式
五,什么是好的哈希函数?
六,哈希函数的构造方法
七,为什么不能对可变的对象进行 hash 处理?
八,大型网站如何利用 hash 函数保护用户密码?
九,Python3.x 增加的随机性
十,其他 hash 算法
背景
哈希(hash)算法,原先是一种被用在资料编码中的技术,可以被用来加密要隐藏的资料,还可以被用来,比较不同文本的相似度。哈希算法属于信息摘要(Message Digest)算法。
区块链技术背后的底层原理之一,即为哈希算法。理解了哈希函数,自然就会理解区块链的挖矿模式。
全面的 hash 算法列表网址: ( http://burtleburtle.net/bob/hash/ )
一,什么是哈希函数?
哈希函数(hash function): 也称为「散列函数」或「杂凑函数」。
h = H(M)
哈希函数将任意长度的消息 M,映射成为一个长度较短且长度固定的值 H(M)。H(M)即为散列值或哈希值(hash value)。
哈希算法是一种信息摘要(Message Digest)算法。对象的 hash 值比原对象拥有更低的内存复杂度。是一种压缩映射。
根据哈希函数所建立的表为哈希表。
2
二,哈希表(hash table)原理
哈希表(hash table)|散列表,是根据关键码值进行访问的数据结构。属于键和值之间的一 一对应关系。
通常提供查找(search),插入(insert),删除(delete)等操作。跟数组一样都是一种数据结构。与字典类似,通过键值对(key-indexed)来保存数据。
目前大部分动态语言的实现中都使用了哈希表。有些语音将哈希表乘坐字典,但是哈希表跟字典并不完全相同。哈希表是弱类型的,而字典是强类型的。
哈希表查找一个元素的时间复杂度为0(1),效率极高,这也是它的一个重要优点。
键(key):操作数据的标识。
槽(bucket):用于存放数据的单元。
创建自己的哈希表的一种方法:
class hashtable(object): def _int_ (self,length = 4): #在这里length = 4,即设置哈希表的初始长度为4 self.array = [none]*length def hash1(self,key): length = len(self.array) return hash(key)%length # key的哈希值除以array列表的长度取余 def is_full(self): # 根据哈希表里面项目的数量来更新长度 items = 0 for item in self.array: #通过self.array将项目的数量增加 if items is not None: items +=1 return items > len(self.array)/2 #判断项目个数是否比array列表总长度的1/2大 def double(self): #定义当容量过小时更新列表的方法 hashtable2 = hashtable(length = len(self.array)*2) #设置hashble2的长度 for i in range(len(self.array)): if self.array[i] is None: contune for zep in self.array[i]: hashble2.add(zep[0] , zep[1]) #将原hashtable2中的数据转移到hashtable2中 self.array = hashtable2.array def add(self,key,value): index = self.hash1(key) #index设为(key)的hash1值 if self.array[index] is not None: #如果array列表中的该位置已被占领 for zep in self.array[index]: if zep[0] == key: #如果zep为[key,_],则设置zep为[key,value], zep[1] == value #即更新该位置存储的键对值 break else: self.array[index].append([key,value]) #否则,在该位置添加键值对 else: self.array[index] = [] self.array[index].append([key,value]) #该位置为None,直接添加键值对 if self.is_full(): self.double() def get(self , key): index = self.hash(key) if self.zed[index] is None: raise KeyError() #所要寻找的键并不存在 else: for zep in self.array[index]: if zep[0] == key: return zep[1] raise KeyError() #并不存在
三,大型网站如何利用 hash 函数保护用户密码?
即使大型网站的数据库被攻破,也不会造成太大损失。为什么呢?这涉及到了哈希函数的两个主要特性:不可逆性与抗碰撞性。
利用哈希函数对用户密码进行加密:用户设置完密码后,会被转换成 hash 值,并保存到数据库中。如下图。
pip3 installsimhash
被保存的只是转换后的哈希值,而不是原密码。
由于哈希(hash)函数是不可逆的,只能由输入产生输出,不能由输出产生输入。系统服务器无法根据每个 hash 值逆过来推算出原密码。因此即使是后台工作人员,也无法得知用户的原密码。
用户登录的时候,输入密码,经过 hash 操作后转换成 hash 值,再与数据库中被保存的 hash 值进行对比。hash 值完全一样,则密码正确。
四,为什么不是所有的 hash 函数都可以被用来加密?
不是所有的 hash 函数都可以被用来加密,这就涉及到了哈希碰撞(hash collision)。
对于 hash 算法,一般情况下,不同的数据会生成不同的哈希值。但是如果两个不同的数据,经过 Hash 函数计算后,得到的 Hash 值一样,则为哈希碰撞(collision)。
即 f (key1) = f(key2)
哈希碰撞无法被完全避免。只能降低其发生概率。
碰撞攻击则是找到另一个跟原密码具有相同 hash 值的字符串。
为了提高安全性,只有加密哈希函数(cryptgraphic hash functions)可以被用来加密。如 SHA256, SHA512, Ripemd, WHIRLPOOL 等 。这类函数的 hash 破解异常困难,几乎不太可能出现 hash 碰撞。
五,哈希碰撞(hash collision)的解决方式
一,开放寻址法(open addressing)
二,拉链法
开放寻址法的总体设计原理为:出现哈希碰撞时,重新检测一个空闲位置,并插入。
但是这样会产生一个问题,即占用其他槽位的空间,以致于后续的插入操作更容易出现冲突。因此在利用开放寻址法的时候,装载因子最好保持在0.5以下。
装载因子 =
[1] 开放寻址法有:
- 线性探测器(Linear Probing)
- 二次探测法(Quadratic Probing)
- 随机探测法
- 双散列(Double hashing)
- 再哈希法
- 建立一个公共溢出区
线性探测法介绍:
线性探测法为开放寻址法最简单的一种实现。
线性探测法用来解决哈希碰撞的原理是:当某个被给定键在散列表中的对应单元已被占用时(即我们向当前哈希表写入数据时发生了冲突),会检测散列表中离冲突单元最近的空闲单元。并把该键值对写入到下一个不为空的位置。
只要哈希表未被填满,总能找到一个不发生冲突的单元。
再哈希法:
再哈希法用来解决哈希碰撞的原理是:两个值产生冲突时,通过下面算式,计算另一地址,直到不再冲突。
Hi = R * Hi(key) [i = 1,2,...k]
同样的关键字,同样的哈希函数,用不同的处理哈希碰撞的方法,得到的哈希函数值也不同。
6
六,什么是好的哈希函数?
哈希表的关键点就在于哈希函数的选择。
若对于关键字集合中的,任意一个关键字,经过哈希函数,映像到地址集合中,任何一个地址的概率是相等的,则为均匀散列函数(uniform hash function)。也即好的哈希函数。
这种方法通过将关键字映射到“均匀分布的随机地址”来减少冲突。
目前的哈希算法都能良好的将key进行比较均匀的分布。
6
七,哈希函数的构造方法:
- 直接定址法
- 除留余数法
- 数字分析法
- 折叠法
- 平方取中法
直接定址法:取关键字,或关键字的某个线性函数值,为哈希地址。
即:H(key) = key 或 H (key) = a * key + b
链地址法:将所有相似关键词的记录存储在同一线性链表中。
8
八,为什么不能对可变的对象进行 hash 处理?
首先要了解两个概念,可哈希性(hashable)与不可哈希性(unhashable)。
可哈希性(hashable):可哈希的数据类型为不可变的数据结构(如字符串 srt,元组 tuple,对象集 objects 等)。这种数据被称为可哈希性。
不可哈希性:不可哈希的数据类型,为可变的数据结构(如字典 dict,列表 list 和集合 set 等)。
如果对可变的对象进行哈希处理,则每次对象更新时,都需要更新哈希表。这样我们则需要将对象移至不同的数据集,这种操作会使花费过大。
因此设定不能对可变的对象进行 hash 处理。
九,Python3.x 增加的随机性
Python3.x添加了 hash 算法的随机性,以提高安全性,因此对于每个新的 python 调用,同样的数据源生成的结果都将不同。 下面为算法实例。
哈希方法有(MD5, SHA1, SHA256 与 SHA512 等)。常用的有 SH256 与 SHA512,即上文提到的加密哈希函数(cryptgraphic hash functions)。MD5 与 SHA1 不再常用。
- MDH5 (不常用)
- SHA1 (不常用)
- SHA256 (常用)
- SHA512 (常用)
10
十,其他 hash 算法**
1. simhash 算法:
这是一种局部敏感的 hash 算法,它产生的签名在一定程度上可以表征原内容的相似度。
可以被用来比较文本的相似度。
如下代码安装 simhash 模块。
pip3 installsimhash
2. Imagehash 算法:
Imagehash 算法为感知哈希算法(perceptual Hash Algorithm)。
常被用来检测图像和视频的差异。
如下代码安装 Imagehash 模块。
pip3 install simhash
例如:可以通过比较两张图片的 hash 值来判断相似度。下面为比较两张相似图片的代码示例。
输出为:
hash(image1) =00fd43c3**f**fffffff hash(image2) =00fd43c3f**e**ffffff
从输出结果可以看到两张图片的 hash 值非常相似。相似的图片可以生成相似的哈希值是 Imagehash 的特点。
后续再详细更新哈希碰撞的解决方式
-
哈希原理
2020-03-10 12:20:03哈希原理 C++11提供的unordered系列的容器之所以在查找方面能够达到O(1)O(1)O(1)的复杂度,是因为其底层使用了哈希的结构 一、哈希的概念: 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此...哈希原理
C++11提供的unordered系列的容器之所以在查找方面能够达到 O ( 1 ) O(1) O(1)的复杂度,是因为其底层使用了
哈希的结构
一、哈希的概念:
顺序结构以及平衡树中
,元素关键码与其存储位置之间没有对应的关系
,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为 O ( N ) O(N) O(N),平衡树中为树的高度,即 O ( l o g 2 N ) O(log~2 N) O(log 2N),搜索的效率取决于搜索过程中元素的比较次数
。理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素
当向该结构中:
-
插入元素
根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放 -
搜索元素
对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功
该方式即为
哈希(散列)方法
,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
问题:按照上述哈希方式,向集合中插入元素44,会出现什么问题?
二、哈希冲突
对于两个数据元素的关键字ki 和kj (i != j),有 ki != kj ,但有:Hash( ki) == Hash(kj),即:
不同关键字通过 相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞
。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢?
三、哈希函数
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
- 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0 到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数
-
直接定制法–(常用)
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
优点:简单、均匀 。
缺点:需要事先 知道关键字的分布情况
使用场景:适合查找比较小且连续的情况 -
除留余数法--(常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函 数:Hash(key) = key% p(p<=m)
,将关键码转换成哈希地址 -
平方取中法
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况 -
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加 求和,并按散列表表长,取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况 -
随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为 随机数函数。
通常应用于关键字长度不等时采用此法 -
数学分析法
四、解决哈希冲突的方法
1. 闭散列
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那 么可以把key存放到冲突位置中的“下一个” 空位置中去。
那如何寻找下一个空位置呢?
线性探测
比如前面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4,因此44理论 上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突
。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止
- 插入
a.通过哈希函数获取待插入元素在哈希表中的位置
b.如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探 测找到下一个空位置,插入新元素
- 删除
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他 元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响
。因此线性探测采用标 记的伪删除法来删除一个元素
// 哈希表每个空间给个标记 // EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除 enum State{EMPTY, EXIST, DELETE}
线性探测的实现
// 注意:假如实现的哈希表中元素唯一,即key相同的元素不再进行插入 // 为了实现简单,此哈希表中我们将比较直接与元素绑定在一起 template<class K, class V> class HashTable { struct Elem { pair<K, V> _val; State _state; }; public: HashTable(size_t capacity = 3) : _ht(capacity) , _size(0) { for(size_t i = 0; i < capacity; ++i) _ht[i]._state = EMPTY; } bool Insert(const pair<K, V>& val) { // 检测哈希表底层空间是否充足 // _CheckCapacity(); size_t hashAddr = HashFunc(key); // size_t startAddr = hashAddr; while(_ht[hashAddr]._state != EMPTY) { if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key) return false; hashAddr++; if(hashAddr == _ht.capacity()) hashAddr = 0; /* // 转一圈也没有找到,注意:动态哈希表,该种情况可以不用考 虑,哈希表中元素个数 到达一定的数量,哈希冲突概率会增大,需要扩容来降低哈希冲突, 因此哈希表中元素是不会存满的 if(hashAddr == startAddr) return false; */ } // 插入元素 _ht[hashAddr]._state = EXIST; _ht[hashAddr]._val = val; _size++; return true; } int Find(const K& key) { size_t hashAddr = HashFunc(key); while(_ht[hashAddr]._state != EMPTY) { if(_ht[hashAddr]._state == EXIST && _ht[hashAddr]._val.first == key) return hashAddr; hashAddr++; } return hashAddr; } bool Erase(const K& key) { int index = Find(key); if(-1 != index) { _ht[index]._state = DELETE; _size++; return true; } return false; } size_t Size()const; bool Empty() const; void Swap(HashTable<K, V, HF>& ht); private: size_t HashFunc(const K& key) { return key % _ht.capacity(); } private: vector<Elem> _ht; size_t _size; };
思考:
哈希表什么情况下进行扩容?如何扩容
?void CheckCapacity() { if(_size * 10 / _ht.capacity() >= 7) { HashTable<K, V, HF> newHt(GetNextPrime(ht.capacity)); for(size_t i = 0; i < _ht.capacity(); ++i) { if(_ht[i]._state == EXIST) newHt.Insert(_ht[i]._val); } Swap(newHt); } }
线性探测优点:实现非常简单,
线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,
容易产生数据“堆积”
,即:不同关键码占据 了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。如何缓解
呢?2.
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块,
这与其找下一个空位置有关系,因为找空位置的方式就 是挨着往后逐个去找
,因此二次探测为了避免该问题,找下一个空位置的方法为:Hi = (H0 + i^2)%m
, 或者:Hi = (H0 + i^2)% m
,H(i + 1) = (H0 + (i + 1)^2)% m
,所以H(i + 1) = Hi + 2i + 1
。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行 计算得到的位置,m是表的大小。对于前面如果要插入44,产生冲突,使用解决后的情况为:
研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置 都不会被探查两次。
因此只要表中有一半的空位置,就不会存在表满的问题
。在搜索时可以不考虑表装 满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容
。因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷
2. 开散列
- 开散列概念
开散列法又叫链地址法
(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码 归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结 点存储在哈希表中。
从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素
。- 开散列实现
template<class V> struct HashBucketNode { HashBucketNode(const V& data) : _pNext(nullptr), _data(data) {} HashBucketNode<V>* _pNext; V _data; }; // 本文所实现的哈希桶中key是唯一的 template<class V> class HashBucket { typedef HashBucketNode<V> Node; typedef Node* PNode; public: HashBucket(size_t capacity = 3) : _size(0) { _ht.resize(GetNextPrime(capacity), nullptr); } // 哈希桶中的元素不能重复 PNode* Insert(const V& data) { // 确认是否需要扩容。。。 // _CheckCapacity(); // 1. 计算元素所在的桶号 size_t bucketNo = HashFunc(data); // 2. 检测该元素是否在桶中 PNode pCur = _ht[bucketNo]; while(pCur) { if(pCur->_data == data) return pCur; pCur = pCur->_pNext; } // 3. 插入新元素 pCur = new Node(data); pCur->_pNext = _ht[bucketNo]; _ht[bucketNo] = pCur; _size++; return pCur; } // 删除哈希桶中为data的元素(data不会重复),返回删除元素的下一个节点 PNode* Erase(const V& data) { size_t bucketNo = HashFunc(data); PNode pCur = _ht[bucketNo]; PNode pPrev = nullptr, pRet = nullptr; while(pCur) { if(pCur->_data == data) { if(pCur == _ht[bucketNo]) _ht[bucketNo] = pCur->_pNext; else pPrev->_pNext = pCur->_pNext; pRet = pCur->_pNext; delete pCur; _size--; return pRet; } } return nullptr; } PNode* Find(const V& data); size_t Size()const; bool Empty()const; void Clear(); bool BucketCount()const; void Swap(HashBucket<V, HF>& ht; ~HashBucket(); private: size_t HashFunc(const V& data) { return data%_ht.capacity(); } private: vector<PNode*> _ht; size_t _size; // 哈希表中有效元素的个数 };
- 开散列增容
桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件
怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容
void _CheckCapacity() { size_t bucketCount = BucketCount(); if(_size == bucketCount) { HashBucket<V, HF> newHt(bucketCount); for(size_t bucketIdx = 0; bucketIdx < bucketCount; ++bucketIdx) { PNode pCur = _ht[bucketIdx]; while(pCur) { // 将该节点从原哈希表中拆出来 _ht[bucketIdx] = pCur->_pNext; // 将该节点插入到新哈希表中 size_t bucketNo = newHt.HashFunc(pCur->_data); pCur->_pNext = newHt._ht[bucketNo]; newHt._ht[bucketNo] = pCur; pCur = _ht[bucketIdx]; } } newHt._size = _size; this->Swap(newHt); } }
- 开散列的思考
只能存储key为整形的元素,其他类型怎么解决?
// 哈希函数采用处理余数法,被模的key必须要为整形才可以处理,此处提供将key转化为整形的方法 // 整形数据不需要转化 template<class T> class DefHashF { public: size_t operator()(const T& val) { return val; } }; // key为字符串类型,需要将其转化为整形 class Str2Int { public: size_t operator()(const string& s) { const char* str = s.c_str(); unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } }; // 为了实现简单,此哈希表中我们将比较直接与元素绑定在一起 template<class V, class HF> class HashBucket { // …… private: size_t HashFunc(const V& data) { return HF()(data.first)%_ht.capacity(); } };
除留余数法,最好模一个素数,如何每次快速取一个类似两倍关系的素数?
const int PRIMECOUNT = 28; const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t GetNextPrime(size_t prime) { size_t i = 0; for(; i < PRIMECOUNT; ++i) { if(primeList[i] > prime) return primeList[i]; } return primeList[PRIMECOUNT - 1]; }
开散列与闭散列比较
应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间
最后最后再说一下开散列和闭散列
能否用vector自定义的扩容方式
?
答案是不可以
。- vector底层的扩容方式为:申请新空间–>拷贝元素—>释放旧空间,
- 在闭散列和开散列中共同的问题是:在计算哈希地址的时候用到data%capacity,而vector是直接拷贝过来,在完成扩容后,capacity已经改变,再去用data%capacity就无法正确找到元素。
- 而在开散列中,vector每个元素存放的是每个哈希链的首地址,在释放旧空间的时候就已经把哈希链释放掉了,在新空间中却仍然在使用,就会发生错误
五、模拟实现哈希
-
-
网络安全原理与应用:哈希函数.pptx
2022-05-16 12:44:57网络安全原理与应用:哈希函数.pptx -
哈希算法(哈希函数)基本
2021-09-19 16:33:42一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M...这是哈希函数安全性的基础。 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同 -
SPARK_SipHash:一个实现SipHash键控哈希函数的Ada 2012 SPARK 2014项目
2021-05-12 01:14:22这是一个实现键控哈希函数的Ada 2012 / 项目。 SipHash是由Jean-Philippe Aumasson和Daniel J. Bernstein设计的,尽管此实现与它们无关。 SipHash是一种针对短消息速度进行了优化的哈希函数,但是它使用了现代密码... -
【区块链学习笔记01】BTC-密码学原理-哈希函数
2022-05-10 21:59:48区块链中最基础的密码学原理就是哈希算法,以下为哈希函数的简单介绍: 哈希函数是一种只只能加密但是不能解密的算法,哈希函数可以将任意长度的信息转化为固定长度的字符串。类似“8b46ec792e943de34605981980751... -
哈希函数原理及实现
2013-01-11 10:54:47下面这个hash函数是一个能够较好的处理字符串的哈希函数,它通过一系列的位操作将健强制转换为整数。此函数改编自《compilers principles techniques and tools》 也就是《编译原理》--龙书 int hashpjw... -
数据结构与算法五:哈希表-哈希函数设计原则-哈希冲突解决方案
2022-01-29 19:51:15哈希函数就是映射关系 三、哈希表应用举例: Leetcode上第387题: 思路:通过s.charAt(i)-'a’将字符串中的字符映射成hash表,出现一次,在相应位置加一,左后找到第一个值为1的下标 其他思路:当然此题解决方案很... -
哈希函数特征,哈希表原理及冲突的解决办法
2022-01-19 18:45:33哈希函数特征,哈希表原理及冲突的解决办法 -
哈希原理和JAVA中的实现
2021-08-24 17:19:43哈希函数 https://blog.csdn.net/tanggao1314/article/details/51457585 常见的Hash函数有以下几个: 直接定址法:直接以关键字k或者k加上某个常数(k+c)作为哈希地址。 数字分析法:提取关键字中取值比较均匀... -
哈希函数实现原理(一)
2020-04-20 15:55:27认识一下31这个神奇的数, 31是一个奇素数(即是奇数又是素数) 31 * i 可以写成(i << 5)- i (JVM可以把31 * i ...哈希表类似数组一样,根据索引去存放值,添加、搜索、删除的都可以达到O(1)的级别,索引的计... -
哈希函数和消息认证
2020-12-29 21:39:24文章目录一、哈希(Hash)函数1、...Hash函数也称散列函数、哈希函数、杂凑函数等。,是一个从消息空间到像空间的不可逆映射。hash函数能将“任意长度”的消息经过hash变换为固定长度的像。所以Hash函数是一种具有压缩性 -
区块链重要基础知识2——哈希函数的原理以及应用于区块头部
2020-06-18 00:58:02哈希函数 1.特性[1] 1.1三个特性: 其输入可为任意大小的字符串。 它产生固定大小的输出。为使本章讨论更具体,我们假设输出值大小为256位,但是,我们的讨论适用于任意规模的输出,只要其足够大。 它能进行... -
哈希函数
2019-02-16 23:55:40希实现原理和常用算法 所有的字符串哈希算法都是基于对字符编码的迭代运算,只是运算规则不同而已。 1)BKDRHash算法 // BKDR Hash Function unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 ... -
【哈希】关于哈希表和哈希函数的理解与应用
2020-08-05 13:09:08之所以要介绍这一小节,主要是几乎所有的哈希函数的应用都离不开定义和性质,也正是因为哈希函数拥有这些性质才在各种场景发挥着优秀的性能。 定义: ,其中输入域为无穷,值域为有限域。 哈希函数的定 -
哈希函数2:用于哈希表的存储和扩容
2022-05-27 21:46:571)哈希表的存储,查询,都是要经过哈希函数转换地址的,f%N 2)哈希表往往是固定长度,当容量不够,自动扩容,但是整体上哈希表的操作仍然是o(1)时间复杂度! 3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑... -
SQL Server2014 哈希索引原理详解
2020-09-10 07:08:30SQL Server 2014推出的的新索引类型叫做 hash index。介绍hash index之前一定要介绍哈希函数这样会让大家更明白哈希索引的原理,有需要的朋友可以参考下 -
哈希函数与布隆过滤器
2021-01-16 18:17:04认识哈希函数 Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。 这种转换是一种压缩映射,也就是,散列值的空间通常远小于... -
Go-哈希函数与消息认证详解(含代码)
2021-06-27 17:59:56Go-哈希函数与消息认证详解(含代码)哈希函数简介历史特性安全性MD族md4md5SHA系列SHA-1SHA-2消息认证消息认证的目的消息认证码认证码与检错码HMAC的Go实现crypto/hmac包hash包crypto/sha1包代码实现截图参考 哈希... -
字符串哈希函数
2018-03-10 16:58:161.简介本文将介绍什么是字符串哈希函数,字符串哈希函数常见用法,以及字符串哈希函数的实现原理和常用算法。2.概念哈希之所以广泛存在,是因为它能在绝大多数情况下可以在O(1)的时间复杂度中完成元素的查找。它的... -
python算法复习(五)----哈希函数及大数据问题
2022-04-21 16:57:53本章简单讲讲哈希函数的实现,和大数据问题的处理方法 认识哈希函数 1.输入域是无穷的,输出域是有限的. 2.相同的输入会返回相同的输出 3.不同的输入可能会返回相同的输出(哈希碰撞,因为输入域是无穷的,输出是有限... -
python字典实现原理-哈希函数-解决哈希冲突方法
2019-05-27 14:22:00哈希表是key-value类型的数据结构, 可以理解为一个键值需要按照一定规则存放的数组, 而哈希函数就是这个规则 字典本质上是一个散列表(总有空白元素的数组, python至少保证1/3的数组是空的), 字典中的每个键都占用一... -
什么是哈希函数
2019-09-20 15:21:34哈希函数(Hash Function),也称为散列函数,给定一个输入x,它会算出相应的输出H(x)。哈希函数的主要特征是: 输入x可以是任意长度的字符串 输出结果即H(x)的长度是固定的 计算 H(x) 的过程是高效的(对于长度... -
哈希算法原理和实现
2020-09-13 10:32:32哈希算法原理和实现 前言 当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二... -
哈希函数的生成方法
2017-07-30 21:22:49本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至记录总数之间;第二,尽可能避免冲突。 设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希... -
Hash(哈希)相关知识(哈希函数、哈希查找)
2020-05-18 21:04:17函数特性1.1 基本的哈希函数1.2 加密的哈希函数2. 常见的哈希函数构造法2.1 直接寻址法2.2 数字分析法2.3 平方取中法2.4 折叠法2.5 随机数法2.6 除留余数法2.7 加密哈希函数3. 哈希函数总结二. 哈希查找1. 操作步骤... -
Hash的基本原理
2020-04-11 00:02:25Hash表也叫散列表,是一种线性数据结构。在一般情况下,可以用o(1)的时间复杂度...在进行数据增删改查的时候,Hash表首先通过Hash函数对某个键值进行Hash操作,这个Hash操作会将这个键映射到数组的某个下标,获得...