精华内容
下载资源
问答
  • 常用哈希函数
    2016-08-15 15:57:34
    int32_t BKDRHash(const std::string &name){
        int32_t hash = 0, seed = 131;
        for (uint32_t i = 0; i < name.length(); i++){
            hash = hash * seed + name[i];
            //transform hash into 131 system
        }
    //to get  positive number by using hash & 0111 111 111 1111b
    }
    
    //hash function 2
    int32_t APHash(const std::string &name){
        int32_t hash = 0;
        for (uint32_t i = 0; i < name.length(); i++){
            if (i % 2){
                hash ^= (~((hash << 11) ^ (name[i]) ^ (hash >> 5)));
            }
            else {
                hash ^= ((hash << 7) ^ (name[i]) ^ (hash >> 3));
            }
        }
        return (hash & 0x7fffffff);
    }
    更多相关内容
  • 常用哈希函数介绍

    千次阅读 2021-03-31 16:21:32
    哈希函数介绍 什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为...

    转载自:
    常用哈希函数介绍


    哈希函数介绍

    什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为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函数里面使用。

    哈希函数的选择

    那么多种哈希函数,我们究竟该选择哪种呢? 不同的应用场景对哈希的算法设计要求也不一样,但一个好的哈希函数应该具备以下三点:

    1. 抗碰撞性,尽量避免冲突。
    2. 抗篡改性,只要改动一个字节,其哈希值也会很大不同。
    3. 查找效率。

    在加密方面,哈希函数应该对抗碰撞性和抗篡改性要求很高,而会牺牲查找效率。 而且随着时代的变化我们最好还是选择更现代化的哈希函数。 目前来说我们可以选择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。

    展开全文
  • 所谓完美哈希函数。就是指没有冲突的哈希函数。即对随意的 key1 != key2 有h(key1) != h(key2)。 设定义域为X,值域为Y, n=|X|,m=|Y|。那么肯定有m>=n,假设对于不同的key1,key2属于X,有h(key1)!=h(key2),那么称h...

    基本概念
    所谓完美哈希函数。就是指没有冲突的哈希函数。即对随意的 key1 != key2 有h(key1) != h(key2)。
    设定义域为X,值域为Y, n=|X|,m=|Y|。那么肯定有m>=n,假设对于不同的key1,key2属于X,有h(key1)!=h(key2),那么称h为完美哈希函数,当m=n时,h称为最小完美哈希函数(这个时候就是一一映射了)。

    在处理大规模字符串数据时。常常要为每一个字符串分配一个整数ID。这就须要一个字符串的哈希函数。怎么样找到一个完美的字符串hash函数呢?

    有一些经常使用的字符串hash函数。

    像BKDRHash,APHash。DJBHash。JSHash,RSHash。SDBMHash,PJWHash。ELFHash等等。都是比較经典的。

    经常使用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。

    这些函数使用位运算使得每个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数。这些函数差点儿不可能找到碰撞。

    经常使用字符串哈希函数有 BKDRHash。APHash。DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数。我对其进行了一个小小的评測。

    Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均分
    BKDRHash20477448196.5510090.9582.0592.64
    APHash23475449396.5588.4610051.2886.28
    DJBHash22497547496.5592.31010083.43
    JSHash14476150610084.6296.8317.9581.94
    RSHash10486150510010051.5820.5175.96
    SDBMHash32484950493.192.3157.0123.0872.41
    PJWHash302648785130043.89021.95
    ELFHash302648785130043.89021.95

    当中数据1为100000个字母和数字组成的随机串哈希冲突个数。

     

    数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。

    数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

    经过比較。得出以上平均得分。

    平均数为平方平均数。能够发现,BKDRHash不管是在实际效果还是编码实现中。效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

    C语言实现的hash()如下:

    unsigned int SDBMHash(char *str)
    {
        unsigned int hash = 0;
     
        while (*str)
        {
            // equivalent to: hash = 65599*hash + (*str++);
            hash = (*str++) + (hash << 6) + (hash << 16) - hash;
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // RS Hash Function
    unsigned int RSHash(char *str)
    {
        unsigned int b = 378551;
        unsigned int a = 63689;
        unsigned int hash = 0;
     
        while (*str)
        {
            hash = hash * a + (*str++);
            a *= b;
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // JS Hash Function
    unsigned int JSHash(char *str)
    {
        unsigned int hash = 1315423911;
     
        while (*str)
        {
            hash ^= ((hash << 5) + (*str++) + (hash >> 2));
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // P. J. Weinberger Hash Function
    unsigned int PJWHash(char *str)
    {
        unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
        unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
        unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
        unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
        unsigned int hash             = 0;
        unsigned int test             = 0;
     
        while (*str)
        {
            hash = (hash << OneEighth) + (*str++);
            if ((test = hash & HighBits) != 0)
            {
                hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // ELF Hash Function
    unsigned int ELFHash(char *str)
    {
        unsigned int hash = 0;
        unsigned int x    = 0;
     
        while (*str)
        {
            hash = (hash << 4) + (*str++);
            if ((x = hash & 0xF0000000L) != 0)
            {
                hash ^= (x >> 24);
                hash &= ~x;
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // BKDR Hash Function
    unsigned int BKDRHash(char *str)
    {
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
        unsigned int hash = 0;
     
        while (*str)
        {
            hash = hash * seed + (*str++);
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // DJB Hash Function
    unsigned int DJBHash(char *str)
    {
        unsigned int hash = 5381;
     
        while (*str)
        {
            hash += (hash << 5) + (*str++);
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // AP Hash Function
    unsigned int APHash(char *str)
    {
        unsigned int hash = 0;
        int i;
     
        for (i=0; *str; i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }

    上面部分参考了:https://www.cnblogs.com/yxwkf/p/5397780.html

    或者使用模板的方式(C++)://6种字符串哈希算法

    
    template<class T>
    size_t BKDRHash(const T * str)
    {
    	register size_t hash = 0;
    	while (size_t ch = (size_t)*str++)
    	{
    		hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..         
    	}
    	return hash;
    }
    template<class T>
    size_t SDBMHash(const T *str)
    {
    	register size_t hash = 0;
    	while (size_t ch = (size_t)*str++)
    	{
    		hash = 65599 * hash + ch;
    		//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
    	}
    	return hash;
    }
    template<class T>
    size_t RSHash(const T *str)
    {
    	register size_t hash = 0;
    	size_t magic = 63689;
    	while (size_t ch = (size_t)*str++)
    	{
    		hash = hash * magic + ch;
    		magic *= 378551;
    	}
    	return hash;
    }
    template<class T>
    size_t APHash(const T *str)
    {
    	register size_t hash = 0;
    	size_t ch;
    	for (long i = 0; ch = (size_t)*str++; i++)
    	{
    		if ((i & 1) == 0)
    		{
    			hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    		}
    		else
    		{
    			hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    		}
    	}
    	return hash;
    }
    template<class T>
    size_t JSHash(const T *str)
    {
    	if (!*str)        // 这是由本人添加,以保证空字符串返回哈希值0  
    		return 0;
    	register size_t hash = 1315423911;
    	while (size_t ch = (size_t)*str++)
    	{
    		hash ^= ((hash << 5) + ch + (hash >> 2));
    	}
    	return hash;
    }
    template<class T>
    size_t DEKHash(const T* str)
    {
    	if (!*str)        // 以保证空字符串返回哈希值0  
    		return 0;
    	register size_t hash = 1315423911;
    	while (size_t ch = (size_t)*str++)
    	{
    		hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
    	}
    	return hash;
    }
    

     

    展开全文
  • 常用哈希函数的比较及其C语言实现

    千次阅读 2015-07-22 23:36:23
    所谓完美哈希函数,就是指没有冲突的哈希函数,即对任意的 key1 != key2 有h(key1) != h(key2)。 设定义域为X,值域为Y, n=|X|,m=|Y|,那么肯定有m>=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2),那么称h为...
    基本概念
    所谓完美哈希函数,就是指没有冲突的哈希函数,即对任意的 key1 != key2 有h(key1) != h(key2)。
    设定义域为X,值域为Y, n=|X|,m=|Y|,那么肯定有m>=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2),那么称h为完美哈希函数,当m=n时,h称为最小完美哈希函数(这个时候就是一一映射了)。

    在处理大规模字符串数据时,经常要为每个字符串分配一个整数ID。这就需要一个字符串的哈希函数。怎么样找到一个完美的字符串hash函数呢?

    有一些常用的字符串hash函数。像BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。都是比较经典的。

    常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。

    常用字符串哈希函数有 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。

    Hash函数 数据1 数据2 数据3 数据4 数据1得分 数据2得分 数据3得分 数据4得分 平均分
    BKDRHash 2 0 4774 481 96.55 100 90.95 82.05 92.64
    APHash 2 3 4754 493 96.55 88.46 100 51.28 86.28
    DJBHash 2 2 4975 474 96.55 92.31 0 100 83.43
    JSHash 1 4 4761 506 100 84.62 96.83 17.95 81.94
    RSHash 1 0 4861 505 100 100 51.58 20.51 75.96
    SDBMHash 3 2 4849 504 93.1 92.31 57.01 23.08 72.41
    PJWHash 30 26 4878 513 0 0 43.89 0 21.95
    ELFHash 30 26 4878 513 0 0 43.89 0 21.95
    其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。


    经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

    unsigned int SDBMHash(char *str)
    {
        unsigned int hash = 0;
     
        while (*str)
        {
            // equivalent to: hash = 65599*hash + (*str++);
            hash = (*str++) + (hash << 6) + (hash << 16) - hash;
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // RS Hash Function
    unsigned int RSHash(char *str)
    {
        unsigned int b = 378551;
        unsigned int a = 63689;
        unsigned int hash = 0;
     
        while (*str)
        {
            hash = hash * a + (*str++);
            a *= b;
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // JS Hash Function
    unsigned int JSHash(char *str)
    {
        unsigned int hash = 1315423911;
     
        while (*str)
        {
            hash ^= ((hash << 5) + (*str++) + (hash >> 2));
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // P. J. Weinberger Hash Function
    unsigned int PJWHash(char *str)
    {
        unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
        unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
        unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
        unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
        unsigned int hash             = 0;
        unsigned int test             = 0;
     
        while (*str)
        {
            hash = (hash << OneEighth) + (*str++);
            if ((test = hash & HighBits) != 0)
            {
                hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // ELF Hash Function
    unsigned int ELFHash(char *str)
    {
        unsigned int hash = 0;
        unsigned int x    = 0;
     
        while (*str)
        {
            hash = (hash << 4) + (*str++);
            if ((x = hash & 0xF0000000L) != 0)
            {
                hash ^= (x >> 24);
                hash &= ~x;
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // BKDR Hash Function
    unsigned int BKDRHash(char *str)
    {
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
        unsigned int hash = 0;
     
        while (*str)
        {
            hash = hash * seed + (*str++);
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // DJB Hash Function
    unsigned int DJBHash(char *str)
    {
        unsigned int hash = 5381;
     
        while (*str)
        {
            hash += (hash << 5) + (*str++);
        }
     
        return (hash & 0x7FFFFFFF);
    }
     
    // AP Hash Function
    unsigned int APHash(char *str)
    {
        unsigned int hash = 0;
        int i;
     
        for (i=0; *str; i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }

    编程珠玑中的一个hash函数

    //用跟元素个数最接近的质数作为散列表的大小
    #define NHASH 29989
    #define MULT 31
    
    unsigned in hash(char *p)
    {
        unsigned int h = 0;
        for (; *p; p++)
            h = MULT *h + *p;
        return h % NHASH;
    }


    展开全文
  • 目前比较有名的哈希函数 C语言 数据结构
  • C++哈希表概念及常用函数方法

    千次阅读 2021-07-13 14:39:36
    哈希(散列)函数的定义 关键值key: 实现过程: 键值对和Entry(一个意思) 哈希冲突: 处理哈希冲突的方法: 1、开放寻址法 2、拉链法 3、冲突过多 哈希表的扩容: 本文根据以下地址进行再一次整理 ...
  • 用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等
  • 常用哈希函数

    千次阅读 2014-09-17 10:20:26
    常用哈希函数包括:直接定址法、数字分析法、除留余数法、乘留余数法、平方取中法、折叠法等。应该根据实际工作中关 键码的特点选用适当的方法。 虽然采用合适的哈希方法能够降低冲突的概率,但是冲突仍然是不...
  • 区块链与哈希函数

    2022-07-19 22:03:48
    直接设计哈希函数 ​编辑 常用哈希函数简介 1.SHA-256算法 ​编辑 2.Keccak算法 3.SM3算法 哈希函数在区块链中的应用 1.以太坊用户地址的生成 2.默克尔哈希树 3. 挖矿难度的设置 4. 数字签名 5. 软件发布 哈希函数 ...
  • 关于哈希函数的构造方法

    千次阅读 2022-04-08 15:44:16
    构造哈希函数的方法很多。在介绍各种方法之前,首先需要明确什么是“好”的哈希函数。 若对于关键字集合中的任一个...常用的构造哈希函数的方法有: 1.直接定址法 取关键字或关键字的某个线性函数值为哈希地址。即...
  • 常见的六种哈希构造函数

    千次阅读 2021-02-23 09:46:53
    文章目录相关概念介绍一、直接寻址法二、数字分析法三、折叠法四、平方取中法五、除留余数法...简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 散列表: 散列表(Hash table,也叫哈希表),是.
  • 系统里有许多不规则的二维点,点(x,y)(x,y)(x,y)坐标规被约为整数类型(乘以放大因子取整),需要在集合内快速查找时候包含有某个点,所以采用unorder容器存储,需要一个性能较好的哈希函数。该问题起源于地震资料处理...
  • 常用hash函数

    2020-08-17 14:49:32
    * 由Justin Sobel编写的按位散列函数 */ function JSHash($string, $len = null) { $hash = 1315423911; $len || $len = strlen($string); for ($i = 0; $i < $len; $i++) { $hash ^= (($hash << 5) ...
  • 在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。 在介绍一些...
  • 哈希表与哈希函数

    2021-11-14 14:18:11
    哈希表(散列表):基于哈希函数的一种查找表/一种根据关键字直接进行访问的数据结构,哈希表(散列表)建立了关键字和存储地址之间的映射关系。 哈希函数(散列函数):把查找表中的关键字映射成该关键字对应地址的...
  • 1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。 2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。 3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,...
  • 哈希原理与常见哈希函数

    千次阅读 多人点赞 2020-01-09 18:11:06
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。在介绍一些集合...
  • 全面理解哈希函数及其应用

    千次阅读 2021-06-09 20:41:08
    1. 哈希函数 哈希函数是指一种能够讲任意数据转换为固定长度编码的一种函数,因为不同数据得到的哈希值可能相同,因此哈希过程一般是不可逆的,哈希函数可以应用的密码加密,哈希存储等方面。 好的哈西函数应该具备...
  • 常用的构造哈希函数方法有 1、除留余数法 除留余数法是用关键字k除以某个不大于哈希长度m的数p (p<=m),将所得的余数作为哈希地址的方法。 h(k) = k mod p 这种方法的关键是选好p,使得元素集合中的每一个...
  • HashMap 的 hash 函数、hash函数的其他构造方法、如何解决哈希冲突
  • 认识哈希函数

    千次阅读 2019-06-20 12:35:54
    首先,先来介绍一下哈希函数的概念。哈希函数的输入域可以是非常大的范围,比如,一个字符串,但是它的输出域是固定的范围。并具有以下性质: 典型的哈希函数都有无限的输入值域。 当给哈希函数传入相同的输入值...
  • 几种常见的哈希函数(散列函数)构造方法 直接定址法 取关键字或关键字的某个线性函数值为散列地址。 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。 比如 除留余数法 取关键字被某个不大于散...
  • 哈希算法(哈希函数)基本

    千次阅读 2021-09-19 16:33:42
    一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M...这是哈希函数安全性的基础。 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同
  • 哈希函数就是映射关系 三、哈希表应用举例: Leetcode上第387题: 思路:通过s.charAt(i)-'a’将字符串中的字符映射成hash表,出现一次,在相应位置加一,左后找到第一个值为1的下标 其他思路:当然此题解决方案很...
  • 哈希函数和哈希表

    千次阅读 2019-05-08 16:31:12
    经典哈希函数的性质(散列函数) 1.输入域无穷大 2.输出域是有穷尽的 3.输入参数相同,返回哈希值不变(不是随机函数) 4.输入不同,哈希值亦可能相同,哈希碰撞 5.离散性:举例:input-0~98,out-0、1、2,...
  • 各种哈希函数的C语言程序代码

    千次阅读 2014-06-19 11:46:54
    常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。 BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RS...
  • 文章目录前言1、哈希表与哈希函数的引入2、哈希表一、设计1、一般、通用哈希函数的设计2、默认哈希函数二、哈希冲突1、链地址法。(seperate chaining )1、1实现1.2、测试2、哈希表的动态空间优化参考 前言 1、哈希...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 97,613
精华内容 39,045
关键字:

常用哈希函数