`

字符串常用的hash算法

阅读更多

转自:http://blog.csdn.net/wenchao126/article/details/8364988

 

MurmurHash2是最近比较流行的一个hash算法,据说性能优越。于是我做了一些测试。

 

murmur: len 20,used 171.30 mili
murmur: len 19,used 163.68 mili
murmur: len 18,used 158.20 mili
murmur: len 17,used 159.94 mili
murmur: len 16,used 155.63 mili
murmur: len 15,used 147.29 mili
murmur: len 14,used 145.16 mili
murmur: len 13,used 145.12 mili
murmur: len 12,used 138.94 mili
murmur: len 11,used 135.30 mili
murmur: len 10,used 131.71 mili
murmur: len 9,used 129.11 mili
murmur: len 8,used 122.59 mili
murmur: len 7,used 117.09 mili
murmur: len 6,used 108.61 mili
murmur: len 5,used 113.07 mili
murmur: len 4,used 100.49 mili
murmur: len 3,used 93.98 mili
murmur: len 2,used 88.14 mili
murmur: len 1,used 86.02 mili
djb: len 20,used 272.66 mili
djb: len 19,used 257.07 mili
djb: len 18,used 242.63 mili
djb: len 17,used 228.25 mili
djb: len 16,used 214.33 mili
djb: len 15,used 200.17 mili
djb: len 14,used 186.42 mili
djb: len 13,used 171.60 mili
djb: len 12,used 158.15 mili
djb: len 11,used 145.17 mili
djb: len 10,used 130.69 mili
djb: len 9,used 121.37 mili
djb: len 8,used 107.93 mili
djb: len 7,used 97.16 mili
djb: len 6,used 87.17 mili
djb: len 5,used 76.95 mili
djb: len 4,used 66.98 mili
djb: len 3,used 56.86 mili
djb: len 2,used 46.84 mili
djb: len 1,used 36.79 mili

 

只有当key的长度大于10字节的时候,MurmurHash的运算速度才快于DJB。而且前提是外部给出key的长度。MurmurHash2(key, strlen(key), seed)的调用方式是惨不忍睹的:

 

murmur: len 20,used 812.83 mili
murmur: len 19,used 802.80 mili
murmur: len 18,used 776.02 mili
murmur: len 17,used 752.58 mili
murmur: len 16,used 719.21 mili
murmur: len 15,used 699.04 mili
murmur: len 14,used 675.73 mili
murmur: len 13,used 655.55 mili
murmur: len 12,used 625.90 mili
murmur: len 11,used 617.32 mili
murmur: len 10,used 593.83 mili
murmur: len 9,used 567.01 mili
murmur: len 8,used 536.72 mili
murmur: len 7,used 516.73 mili
murmur: len 6,used 493.17 mili
murmur: len 5,used 469.66 mili
murmur: len 4,used 439.49 mili
murmur: len 3,used 405.99 mili
murmur: len 2,used 385.84 mili
murmur: len 1,used 358.96 mili
djb: len 20,used 293.64 mili
djb: len 19,used 258.24 mili
djb: len 18,used 244.04 mili
djb: len 17,used 228.52 mili
djb: len 16,used 215.22 mili
djb: len 15,used 200.68 mili
djb: len 14,used 187.65 mili
djb: len 13,used 172.02 mili
djb: len 12,used 158.67 mili
djb: len 11,used 145.40 mili
djb: len 10,used 157.98 mili
djb: len 9,used 120.30 mili
djb: len 8,used 106.59 mili
djb: len 7,used 95.54 mili
djb: len 6,used 86.32 mili
djb: len 5,used 76.11 mili
djb: len 4,used 67.41 mili
djb: len 3,used 57.02 mili
djb: len 2,used 50.33 mili
djb: len 1,used 43.64 mili

 

 

结论:从计算速度上来看,MurmurHash只适用于已知长度的、长度比较长的字符串。长度未知或者长度不超过10字节,都应该使用DJB。在C/C++编程里,你很难保证每个char*的key都会带着一个单独length传递,因此MurmurHash的适用场景会受到限制(让外部调用者去strlen消耗的仍然是计算机的计算能力)。另外,对于最常见的userID之类的key,长度一般都不会超过10字节,MurmurHash对于这种最常见的key仍然表现不佳。

 

hash的分布情况则更难说明,我知道的是选择合适的bucket size之后,DJB平均只要1.2次strcmp,因此MurmurHash不可能大幅超越DJB,最多和DJB大致相当。

 

结论之结论:还是DJB好。只有在特别的数据特别的场合,才应该考虑单独的使用MurmurHash。

两个hash算法

 

1、djb算法

 

[cpp] view plaincopy
 
  1. /* the famous DJB Hash Function for strings */    
  2. unsigned int DJBHash(char *str)    
  3. {    
  4.     unsigned int hash = 5381;    
  5.      
  6.     while (*str){    
  7.         hash = ((hash << 5) + hash) + (*str++); /* times 33 */    
  8.     }    
  9.     hash &= ~(1 << 31); /* strip the highest bit */    
  10.     return hash;    
  11. }    

以上代码取自http://blog.csdn.net/chaosinux/article/details/7853394
2、murmurhash2算法

 

 

[cpp] view plaincopy
 
  1. uint32_t  
  2. ngx_murmur_hash2(u_char *data, size_t len)  
  3. {  
  4.     uint32_t  h, k;  
  5.   
  6.     h = 0 ^ len;  
  7.   
  8.     while (len >= 4) {  
  9.         k  = data[0];  
  10.         k |= data[1] << 8;  
  11.         k |= data[2] << 16;  
  12.         k |= data[3] << 24;  
  13.   
  14.         k *= 0x5bd1e995;  
  15.         k ^= k >> 24;  
  16.         k *= 0x5bd1e995;  
  17.   
  18.         h *= 0x5bd1e995;  
  19.         h ^= k;  
  20.   
  21.         data += 4;  
  22.         len -= 4;  
  23.     }  
  24.   
  25.     switch (len) {  
  26.     case 3:  
  27.         h ^= data[2] << 16;  
  28.     case 2:  
  29.         h ^= data[1] << 8;  
  30.     case 1:  
  31.         h ^= data[0];  
  32.         h *= 0x5bd1e995;  
  33.     }  
  34.   
  35.     h ^= h >> 13;  
  36.     h *= 0x5bd1e995;  
  37.     h ^= h >> 15;  
  38.   
  39.     return h;  
  40. }  

以上代码取自是nginx
murmurhash算法评测

 

速度评测

    OneAtATime -354.163715 mb/sec
    FNV -443.668038 mb/sec
   SuperFastHash - 985.335173 mb/sec
    lookup3 -988.080652 mb/sec
    MurmurHash1.0 - 1363.293480 mb/sec
    MurmurHash2.0 - 2056.885653 mb/sec

 

3、原始版本的murmurhash2算法(Google Code 的 Murmurhash 开源项目主页上的 Murmurhash2)

 

[cpp] view plaincopy
 
  1. uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )  
  2. {  
  3.   // 'm' and 'r' are mixing constants generated offline.  
  4.   // They're not really 'magic', they just happen to work well.  
  5.   
  6.   const uint32_t m = 0x5bd1e995;  
  7.   const int r = 24;  
  8.   
  9.   // Initialize the hash to a 'random' value  
  10.   
  11.   uint32_t h = seed ^ len;  
  12.   
  13.   // Mix 4 bytes at a time into the hash  
  14.   
  15.   const unsigned char * data = (const unsigned char *)key;  
  16.   
  17.   while(len >= 4)  
  18.   {  
  19.     uint32_t k = *(uint32_t*)data;  
  20.   
  21.     k *= m;  
  22.     k ^= k >> r;  
  23.     k *= m;  
  24.   
  25.     h *= m;  
  26.     h ^= k;  
  27.   
  28.     data += 4;  
  29.     len -= 4;  
  30.   }  
  31.   
  32.   // Handle the last few bytes of the input array  
  33.   
  34.   switch(len)  
  35.   {  
  36.   case 3: h ^= data[2] << 16;  
  37.   case 2: h ^= data[1] << 8;  
  38.   case 1: h ^= data[0];  
  39.       h *= m;  
  40.   };  
  41.   
  42.   // Do a few final mixes of the hash to ensure the last few  
  43.   // bytes are well-incorporated.  
  44.   
  45.   h ^= h >> 13;  
  46.   h *= m;  
  47.   h ^= h >> 15;  
  48.   
  49.   return h;  
  50. }  
分享到:
评论

相关推荐

    字符串的哈希Key算法

    字符串哈希Key算法是计算机科学中一种用于快速查找和存储字符串的重要技术。它通过将字符串转化为固定长度的数值,即哈希值,使得在大量数据中查找特定字符串变得高效。这种算法广泛应用于数据库索引、缓存系统、...

    C语言中压缩字符串的简单算法小结

    本文将重点介绍三种简单的字符串压缩算法,包括哈夫曼编码,以及它们在不同场景中的应用。 首先,最基础的字符串压缩方法是简单累加法。这个方法直接将字符串中的每个字符的ASCII码值相加,并对结果取模以适应目标...

    字符串hash算法比较

    字符串哈希算法是一种将任意长度的字符串映射到固定长度哈希值的算法,通常用于快速查找、数据索引和内存管理等。在计算机科学中,哈希函数的设计至关重要,因为它直接影响到哈希表的性能。本文将探讨几种经典的字符...

    字符串处理算法

    Hash算法在字符串处理中常常被用来快速判断两个字符串是否相等,或者快速定位特定字符串的位置。在处理Hash冲突时,通常有开散列和闭散列两种策略。开散列通过在冲突位置建立链表来解决问题,而闭散列则通过移动到...

    hash字符串函数总结

    在计算机科学中,哈希(Hash)函数是一种用于将任意长度的数据映射为固定长度输出的算法。这种输出通常称为哈希值,它在数据结构(如哈希表)、密码学、数字签名等领域有着广泛的应用。本文将对几种常见的字符串哈希...

    C#实现字符串SHA-256加密算法

    这段代码首先将输入的字符串转换为字节数组,然后创建一个SHA256实例,通过调用ComputeHash方法计算摘要。计算出的摘要是一个字节数组,为了方便展示和比较,通常会将每个字节转换为其16进制表示并连接成字符串。 ...

    MySQL分库分表,读写分离与Mycat的使用文章中字符串hash解析算法分片sql

    MySQL分库分表,读写分离与Mycat的使用文章中字符串hash解析算法分片sql

    最快的排序算法 最快的内容查找算法-----暴雪的Hash算法,排序算法数据结构

    在暴雪的Hash算法中,使用了一个经典的字符串Hash公式,能够快速地生成哈希值。该算法的核心思想是使用一个循环来计算字符串的哈希值,循环中使用了两个种子数seed1和seed2,通过对字符串的每个字符进行toupper操作...

    主流字符串哈希算法简明介绍及实例代码

    主流字符串哈希算法简明介绍及实例代码 哈希算法是计算机科学中的一种基础算法,广泛应用于数据存储、检索、加密等领域。字符串哈希算法是哈希算法中的一种特殊类型,专门用于处理字符串类型的数据。在本文中,我们...

    数据结构(字符串匹配,hash,二叉树)训练

    传统的朴素字符串匹配算法时间复杂度较高,而哈希函数的引入可以显著提高效率。哈希函数将字符串转化为固定大小的数值,使得比较变得快速。在这个实验中,你需要设计一个哈希函数,确保不同的字符串能生成不同的哈希...

    获取一个字符串的散列hash

    在给定的标题和描述中,“获取一个字符串的散列hash”指的是利用特定算法将一个字符串转换为其对应的散列值。这个过程对于JavaScript开发者来说尤其有用,因为可以用于创建唯一标识符、验证数据完整性或加密敏感信息...

    自己实现的字符串hash类

    在编程领域,哈希表(Hash Table)是一种高效的数据结构,它通过计算字符串的哈希值来实现快速的查找、插入和删除操作。哈希表通常由数组和哈希函数组成,其中哈希函数将键(Key)映射到数组的特定位置。在这个场景...

    字符串哈希成数字的C实现的代码(含测试)

    将字符串哈希成数字的几种经典的方法:其中的一部分 #ifndef INCLUDE_GENERALHASHFUNCTION_C_H #define INCLUDE_GENERALHASHFUNCTION_C_H #include typedef unsigned int (*hash_function)(char*, unsigned int...

    hash算法相关介绍

    ### Hash算法相关介绍 在计算机科学领域,哈希(Hash)是一种将任意长度的数据映射为固定长度数据的技术。哈希算法广泛应用于多种场景中,包括但不限于数据完整性验证、密码存储、快速查找等。本文主要介绍了几种...

    Java实现GeoHash算法

    Java实现GeoHash算法是一种在IT领域中用于地理位置数据存储和检索的技术。GeoHash将经纬度坐标转换为字符串,使得地理位置可以被高效地索引和查询。这种算法利用了空间分割和编码策略,使得相邻的位置在编码后具有...

    javascript实现获取字符串hash值

    性能很高的计算字符串或文件hash值的函数,比md5速度快得多,自己一直用着,重复的几率为很底,一般的应用足够, var I64BIT_TABLE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-'.split...

    String Hash algorithm, 字符串HASH算法

    list some String Hash algorithm, you can use it directly.

    ACM-字符串处理专练

    2. **字符串搜索**:包括线性搜索和更高效的算法,如KMP(Knuth-Morris-Pratt)算法,Boyer-Moore算法,以及Rabin-Karp rolling hash。这些算法用于在一个字符串中查找子串,且在某些情况下可以实现快速定位。 3. *...

    字符串常用处理的实例大全(SHAI、MD5加解密等)

    本资源“字符串常用处理的实例大全(SHAI、MD5加解密等)”聚焦于字符串的常见操作,包括加密与解密,以及特定的哈希算法如SHA1和MD5。以下是对这些知识点的详细解释: 1. **HTML转换字符**:在Web开发中,HTML字符...

Global site tag (gtag.js) - Google Analytics