`
ssxxjjii
  • 浏览: 931613 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Hash算法大全(java实现）

 
阅读更多

https://weblogs.java.net/blog/2007/11/27/consistent-hashing  java 版本的例子

http://www.java3z.com/cwbwebhome/article/article5/51002.html

Hash算法有很多很多种类。具体的可以参考之前我写的Hash算法的一些分析。本处给大家提供一个集合了很多使用的Hash算法的类，应该可以满足不少人的需要的：

Java代码
  1.   
  2. /**  
  3. * Hash算法大全<br>  
  4. * 推荐使用FNV1算法  
  5. * @algorithm None  
  6. * @author Goodzzp 2006-11-20  
  7. * @lastEdit Goodzzp 2006-11-20   
  8. * @editDetail Create  
  9. */  
  10. public class HashAlgorithms   
  11. {   
  12. /**  
  13. * 加法hash  
  14. * @param key 字符串  
  15. * @param prime 一个质数  
  16. * @return hash结果  
  17. */  
  18. public static int additiveHash(String key, int prime)   
  19. {   
  20.    int hash, i;   
  21.    for (hash = key.length(), i = 0; i < key.length(); i++)   
  22.     hash += key.charAt(i);   
  23.    return (hash % prime);   
  24. }   
  25.   
  26. /**  
  27. * 旋转hash  
  28. * @param key 输入字符串  
  29. * @param prime 质数  
  30. * @return hash值  
  31. */  
  32. public static int rotatingHash(String key, int prime)   
  33. {   
  34.    int hash, i;   
  35.    for (hash=key.length(), i=0; i<key.length(); ++i)   
  36.      hash = (hash<<4)^(hash>>28)^key.charAt(i);   
  37.    return (hash % prime);   
  38. //   return (hash ^ (hash>>10) ^ (hash>>20));   
  39. }   
  40.   
  41. // 替代：   
  42. // 使用：hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;   
  43. // 替代：hash %= prime;   
  44.   
  45.   
  46. /**  
  47. * MASK值，随便找一个值，最好是质数  
  48. */  
  49. static int M_MASK = 0x8765fed1;   
  50. /**  
  51. * 一次一个hash  
  52. * @param key 输入字符串  
  53. * @return 输出hash值  
  54. */  
  55. public static int oneByOneHash(String key)   
  56. {   
  57.    int   hash, i;   
  58.    for (hash=0, i=0; i<key.length(); ++i)   
  59.    {   
  60.      hash += key.charAt(i);   
  61.      hash += (hash << 10);   
  62.      hash ^= (hash >> 6);   
  63.    }   
  64.    hash += (hash << 3);   
  65.    hash ^= (hash >> 11);   
  66.    hash += (hash << 15);   
  67. //   return (hash & M_MASK);   
  68.    return hash;   
  69. }   
  70.   
  71. /**  
  72. * Bernstein's hash  
  73. * @param key 输入字节数组  
  74. * @param level 初始hash常量  
  75. * @return 结果hash  
  76. */  
  77. public static int bernstein(String key)   
  78. {   
  79.    int hash = 0;   
  80.    int i;   
  81.    for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);   
  82.    return hash;   
  83. }   
  84.   
  85. //   
  86. //// Pearson's Hash   
  87. // char pearson(char[]key, ub4 len, char tab[256])   
  88. // {   
  89. //   char hash;   
  90. //   ub4 i;   
  91. //   for (hash=len, i=0; i<len; ++i)    
  92. //     hash=tab[hash^key[i]];   
  93. //   return (hash);   
  94. // }   
  95.   
  96. //// CRC Hashing，计算crc,具体代码见其他   
  97. // ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256])   
  98. // {   
  99. //   ub4 hash, i;   
  100. //   for (hash=len, i=0; i<len; ++i)   
  101. //     hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]];   
  102. //   return (hash & mask);   
  103. // }   
  104.   
  105. /**  
  106. * Universal Hashing  
  107. */  
  108. public static int universal(char[]key, int mask, int[] tab)   
  109. {   
  110.    int hash = key.length, i, len = key.length;   
  111.    for (i=0; i<(len<<3); i+=8)   
  112.    {   
  113.      char k = key[i>>3];   
  114.      if ((k&0x01) == 0) hash ^= tab[i+0];   
  115.      if ((k&0x02) == 0) hash ^= tab[i+1];   
  116.      if ((k&0x04) == 0) hash ^= tab[i+2];   
  117.      if ((k&0x08) == 0) hash ^= tab[i+3];   
  118.      if ((k&0x10) == 0) hash ^= tab[i+4];   
  119.      if ((k&0x20) == 0) hash ^= tab[i+5];   
  120.      if ((k&0x40) == 0) hash ^= tab[i+6];   
  121.      if ((k&0x80) == 0) hash ^= tab[i+7];   
  122.    }   
  123.    return (hash & mask);   
  124. }   
  125.   
  126. /**  
  127. * Zobrist Hashing  
  128. */    
  129. public static int zobrist( char[] key,int mask, int[][] tab)   
  130. {   
  131.    int hash, i;   
  132.    for (hash=key.length, i=0; i<key.length; ++i)   
  133.      hash ^= tab[i][key[i]];   
  134.    return (hash & mask);   
  135. }   
  136.   
  137. // LOOKUP3    
  138. // 见Bob Jenkins(3).c文件   
  139.   
  140. // 32位FNV算法   
  141. static int M_SHIFT = 0;   
  142. /**  
  143. * 32位的FNV算法  
  144. * @param data 数组  
  145. * @return int值  
  146. */  
  147.     public static int FNVHash(byte[] data)   
  148.     {   
  149.         int hash = (int)2166136261L;   
  150.         for(byte b : data)   
  151.             hash = (hash * 16777619) ^ b;   
  152.         if (M_SHIFT == 0)   
  153.             return hash;   
  154.         return (hash ^ (hash >> M_SHIFT)) & M_MASK;   
  155.     }   
  156.     /**  
  157.      * 改进的32位FNV算法1  
  158.      * @param data 数组  
  159.      * @return int值  
  160.      */  
  161.     public static int FNVHash1(byte[] data)   
  162.     {   
  163.         final int p = 16777619;   
  164.         int hash = (int)2166136261L;   
  165.         for(byte b:data)   
  166.             hash = (hash ^ b) * p;   
  167.         hash += hash << 13;   
  168.         hash ^= hash >> 7;   
  169.         hash += hash << 3;   
  170.         hash ^= hash >> 17;   
  171.         hash += hash << 5;   
  172.         return hash;   
  173.     }   
  174.     /**  
  175.      * 改进的32位FNV算法1  
  176.      * @param data 字符串  
  177.      * @return int值  
  178.      */  
  179.     public static int FNVHash1(String data)   
  180.     {   
  181.         final int p = 16777619;   
  182.         int hash = (int)2166136261L;   
  183.         for(int i=0;i<data.length();i++)   
  184.             hash = (hash ^ data.charAt(i)) * p;   
  185.         hash += hash << 13;   
  186.         hash ^= hash >> 7;   
  187.         hash += hash << 3;   
  188.         hash ^= hash >> 17;   
  189.         hash += hash << 5;   
  190.         return hash;   
  191.     }   
  192.   
  193.     /**  
  194.      * Thomas Wang的算法，整数hash  
  195.      */    
  196.     public static int intHash(int key)   
  197.     {   
  198.       key += ~(key << 15);   
  199.       key ^= (key >>> 10);   
  200.       key += (key << 3);   
  201.       key ^= (key >>> 6);   
  202.       key += ~(key << 11);   
  203.       key ^= (key >>> 16);   
  204.       return key;   
  205.     }   
  206.     /**  
  207.      * RS算法hash  
  208.      * @param str 字符串  
  209.      */  
  210.     public static int RSHash(String str)   
  211.     {   
  212.         int b    = 378551;   
  213.         int a    = 63689;   
  214.         int hash = 0;   
  215.   
  216.        for(int i = 0; i < str.length(); i++)   
  217.        {   
  218.           hash = hash * a + str.charAt(i);   
  219.           a    = a * b;   
  220.        }   
  221.   
  222.        return (hash & 0x7FFFFFFF);   
  223.     }   
  224.     /* End Of RS Hash Function */  
  225.   
  226.     /**  
  227.      * JS算法  
  228.      */  
  229.     public static int JSHash(String str)   
  230.     {   
  231.        int hash = 1315423911;   
  232.   
  233.        for(int i = 0; i < str.length(); i++)   
  234.        {   
  235.           hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));   
  236.        }   
  237.   
  238.        return (hash & 0x7FFFFFFF);   
  239.     }   
  240.     /* End Of JS Hash Function */  
  241.   
  242.     /**  
  243.      * PJW算法  
  244.      */  
  245.     public static int PJWHash(String str)   
  246.     {   
  247.         int BitsInUnsignedInt = 32;   
  248.         int ThreeQuarters     = (BitsInUnsignedInt * 3) / 4;   
  249.         int OneEighth         = BitsInUnsignedInt / 8;   
  250.         int HighBits          = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);   
  251.         int hash              = 0;   
  252.         int test              = 0;   
  253.   
  254.        for(int i = 0; i < str.length();i++)   
  255.        {   
  256.           hash = (hash << OneEighth) + str.charAt(i);   
  257.   
  258.           if((test = hash & HighBits) != 0)   
  259.           {   
  260.              hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));   
  261.           }   
  262.        }   
  263.   
  264.        return (hash & 0x7FFFFFFF);   
  265.     }   
  266.     /* End Of P. J. Weinberger Hash Function */  
  267.   
  268.     /**  
  269.      * ELF算法  
  270.      */  
  271.     public static int ELFHash(String str)   
  272.     {   
  273.         int hash = 0;   
  274.         int x    = 0;   
  275.   
  276.        for(int i = 0; i < str.length(); i++)   
  277.        {   
  278.           hash = (hash << 4) + str.charAt(i);   
  279.           if((x = (int)(hash & 0xF0000000L)) != 0)   
  280.           {   
  281.              hash ^= (x >> 24);   
  282.              hash &= ~x;   
  283.           }   
  284.        }   
  285.   
  286.        return (hash & 0x7FFFFFFF);   
  287.     }   
  288.     /* End Of ELF Hash Function */  
  289.   
  290.     /**  
  291.      * BKDR算法  
  292.      */  
  293.     public static int BKDRHash(String str)   
  294.     {   
  295.         int seed = 131; // 31 131 1313 13131 131313 etc..   
  296.         int hash = 0;   
  297.   
  298.        for(int i = 0; i < str.length(); i++)   
  299.        {   
  300.           hash = (hash * seed) + str.charAt(i);   
  301.        }   
  302.   
  303.        return (hash & 0x7FFFFFFF);   
  304.     }   
  305.     /* End Of BKDR Hash Function */  
  306.   
  307.     /**  
  308.      * SDBM算法  
  309.      */  
  310.     public static int SDBMHash(String str)   
  311.     {   
  312.         int hash = 0;   
  313.   
  314.        for(int i = 0; i < str.length(); i++)   
  315.        {   
  316.           hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;   
  317.        }   
  318.   
  319.        return (hash & 0x7FFFFFFF);   
  320.     }   
  321.     /* End Of SDBM Hash Function */  
  322.   
  323.     /**  
  324.      * DJB算法  
  325.      */  
  326.     public static int DJBHash(String str)   
  327.     {   
  328.        int hash = 5381;   
  329.   
  330.        for(int i = 0; i < str.length(); i++)   
  331.        {   
  332.           hash = ((hash << 5) + hash) + str.charAt(i);   
  333.        }   
  334.   
  335.        return (hash & 0x7FFFFFFF);   
  336.     }   
  337.     /* End Of DJB Hash Function */  
  338.   
  339.     /**  
  340.      * DEK算法  
  341.      */  
  342.     public static int DEKHash(String str)   
  343.     {   
  344.         int hash = str.length();   
  345.   
  346.        for(int i = 0; i < str.length(); i++)   
  347.        {   
  348.           hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);   
  349.        }   
  350.   
  351.        return (hash & 0x7FFFFFFF);   
  352.     }   
  353.     /* End Of DEK Hash Function */  
  354.   
  355.     /**  
  356.      * AP算法  
  357.      */  
  358.     public static int APHash(String str)   
  359.     {   
  360.         int hash = 0;   
  361.   
  362.        for(int i = 0; i < str.length(); i++)   
  363.        {   
  364.           hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str.charAt(i) ^ (hash >> 3)) :   
  365.                                    (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));   
  366.        }   
  367.   
  368. //       return (hash & 0x7FFFFFFF);   
  369.        return hash;   
  370.     }   
  371.     /* End Of AP Hash Function */  
  372.        
  373.     /**  
  374.      * JAVA自己带的算法  
  375.      */  
  376.     public static int java(String str)   
  377. {   
  378.    int h = 0;   
  379.    int off = 0;   
  380.    int len = str.length();   
  381.    for (int i = 0; i < len; i++)   
  382.    {   
  383.     h = 31 * h + str.charAt(off++);   
  384.    }   
  385.    return h;   
  386. }   
  387.        
  388.     /**  
  389.      * 混合hash算法，输出64位的值  
  390.      */  
  391.       public static long mixHash(String str)   
  392.      {   
  393.     long hash = str.hashCode();   
  394.      hash <<= 32;   
  395.      hash |= FNVHash1(str);   
  396.     return hash;   
  397.      } 
 
分享到：
| 跳出一致性Hash算法 打造更高效的分布式缓 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics