精华内容
下载资源
问答
  • 常用哈希函数

    2016-08-15 15:57:34
    int32_t BKDRHash(const std::string &name){ int32_t hash, seed = 131; for (uint32_t i = 0; i (); i++){ hash = hash * seed + name[i]; //transform hash into 131 system
    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得分 平均分
    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效果最差,但得分相似,其算法本质是相似的。

    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语言 数据结构
  • 常用哈希函数的比较及其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;
    }


    展开全文
  • 常用哈希函数

    千次阅读 2014-09-17 10:20:26
    常用哈希函数包括:直接定址法、数字分析法、除留余数法、乘留余数法、平方取中法、折叠法等。应该根据实际工作中关 键码的特点选用适当的方法。 虽然采用合适的哈希方法能够降低冲突的概率,但是冲突仍然是不...
  • 哈希函数
  • 哈希查找的第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果有一个数组大小为M,那么就需要一个能够将任意键转换为该数组范围内的索引(0~M-1)的哈希函数哈希函数需要易于计算并且能够均匀...
  • 哈希函数

    千次阅读 2013-09-18 23:45:59
    简介哈希方法学哈希函数和素数位偏向各种形式的哈希常用哈希函数各版本哈希代码下载 简介 哈稀函数按照定义可以实现一个伪随机数生成器(PRNG),从这个角度可以得到一个公认的结论:哈希函数...
  • 用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等
  • 常用哈希函数构造方法
  • C-常用构造哈希函数

    2014-04-25 22:19:00
    1.定址法(比如0-100岁的人数统计, 可以按年龄作为散列地址, 1980年后每年出生人数的统计, 可以把"年限 - 1980"作为散列地址) 2.取余法 3.数字分析法(比如一串字符串中的某几位进行分析) 4.平方取中法(先平方, ...
  • 常用的构造哈希函数方法有 1、除留余数法 除留余数法是用关键字k除以某个不大于哈希长度m的数p (p<=m),将所得的余数作为哈希地址的方法。 h(k) = k mod p 这种方法的关键是选好p,使得元素集合中的每一个...
  • 目录哈希函数的构建: 哈希表:通过关键码来映射到值的一个数据结构; 哈希函数:键与值映射的一个映射关系; 哈希函数的构建: 常用方法: 1、直接寻址法:f(x) = kx+b (k、b都是常数) ,一旦确定了哈希函数,那么...
  • 转一下常见的常用哈希函数

    千次阅读 2016-07-04 17:57:30
    转载自 http://blog.csdn.net/alongela/article/details/8247713 const int MOD = 10007; unsigned int RSHash(const char* str) { unsigned int b = 378551; unsigned int a = 63689;... u
  • 常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。经过测试,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JS...
  • (2) 设计Hash函数,将关键字key散射到Hash表中。其中hash函数设计是最为关键的,均匀分布、冲突概率小全在它; (3) 通常采用拉链方法来解决hash冲突问题,即散射到同一个hash表项的关键字,以链表形式来表示; (4) ...
  • 字符串哈希函数

    千次阅读 2019-01-23 11:05:11
    本文将介绍什么是字符串哈希函数,字符串哈希函数常见用法,以及字符串哈希函数的实现原理和常用算法。 2、概念 哈希之所以广泛存在,是因为它能在绝大多数情况下可以在O(1)的时间复杂度中完成元素的查找。它的...
  • 散列函数(哈希函数)算法

    千次阅读 2014-11-07 16:19:19
    常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。 C++代码 对于以上几种哈希函数,对其进行了一个小小的评测。 Hash函数 数据1 数据2...
  • 单向散列函数-指纹-哈希函数1. 什么是单向散列函数2.单向散列函数的性质2.1. 根据任意长度的消息计算出固定长度的散列值2.2. 能够快速计算出散列值2.3. 消息不同散列值也不同2.4. 具备单向性3.术语4. 单向散列函数的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,156
精华内容 462
关键字:

常用哈希函数