现在的位置: 首页 > 综合 > 正文

字符串哈希函数算法的PHP 实现

2013年11月23日 ⁄ 综合 ⁄ 共 2991字 ⁄ 字号 小 中 大 ⁄ 评论关闭

恩...或许还有朋友不清楚字符串的哈希函数到底有什么用，这个用处呢，就是将字符串转换成数字，同时让所得数字尽量平均的分布在容器中，换句话说就是让字符串得到相同数字这种情况尽可能少的出现。当然咯...容器太小，内容太多那么再好的算法也没法避免出现冲突 = =b

从网上找到的哈希函数基本上都是C算法的...最后只好从C and Java 算法中整理 and 测试了这些 PHP中的实现方法。有几个经典的算法在 PHP 下会有问题，字符串一长就会全部取 0，那些我就没有再列出来了。代码就看下面咯：

PLAIN TEXT
PHP:

  1. function DJBHash($str) // 0.22
  2. {
  3. $hash = 0;
  4. $n = strlen($str);
  5. for ($i = 0; $i <$n; $i++)
  6. {
  7. $hash += ($hash <<5 ) + ord($str[$i]);
  8. }
  9. return $hash % 701819;
  10. }
  11.  
  12. function ELFHash($str) // 0.35
  13. {
  14. $hash = $x = 0;
  15. $n = strlen($str);
  16.  
  17. for ($i = 0; $i <$n; $i++)
  18. {
  19. $hash = ($hash <<4) + ord($str[$i]);
  20. if(($x = $hash & 0xf0000000) != 0)
  21. {
  22. $hash ^= ($x>> 24);
  23. $hash &= ~$x;
  24. }
  25. }
  26. return $hash % 701819;
  27. }
  28.  
  29. function JSHash($str) // 0.23
  30. {
  31. $hash = 0;
  32. $n = strlen($str);
  33.  
  34. for ($i = 0; $i <$n; $i++)
  35. {
  36. $hash ^= (($hash <<5) + ord($str[$i]) + ($hash>> 2));
  37. }
  38. return $hash % 701819;
  39. }
  40.  
  41. function SDBMHash($str) // 0.23
  42. {
  43. $hash = 0 ;
  44. $n = strlen($str);
  45.  
  46. for ($i = 0; $i <$n; $i++)
  47. {
  48. $hash = ord($str[$i]) + ($hash <<6 ) + ($hash <<16 ) - $hash;
  49. }
  50. return $hash % 701819;
  51. }
  52.  
  53. function APHash($str) // 0.30
  54. {
  55. $hash = 0 ;
  56. $n = strlen($str);
  57.  
  58. for ($i = 0; $i <$n; $i++)
  59. {
  60. if (($i & 1 ) == 0 )
  61. {
  62. $hash ^= (($hash <<7 ) ^ ord($str[$i]) ^ ($hash>> 3 ));
  63. }
  64. else
  65. {
  66. $hash ^= ( ~ (($hash <<11 ) ^ ord($str[$i]) ^ ($hash>> 5)));
  67. }
  68. }
  69. return $hash % 701819;
  70. }
  71.  
  72. function DEKHash($str) // 0.23
  73. {
  74. $n = strlen($str);
  75. $hash = $n;
  76.  
  77. for ($i = 0; $i <$n; $i++)
  78. {
  79. $hash = (($hash <<5) ^ ($hash>> 27)) ^ ord($str[$i]);
  80. }
  81. return $hash % 701819;
  82. }
  83.  
  84. function FNVHash($str) // 0.31
  85. {
  86. $hash = 0;
  87. $n = strlen($str);
  88.  
  89. for ($i = 0; $i <$n; $i++)
  90. {
  91. $hash *= 0x811C9DC5;
  92. $hash ^= ord($str[$i]);
  93. }
  94.  
  95. return $hash % 701819;
  96. }
  97.  
  98. function PJWHash($str) // 0.33
  99. {
  100. $hash = $test = 0;
  101. $n = strlen($str);
  102.  
  103. for ($i = 0; $i <$n; $i++)
  104. {
  105. $hash = ($hash <<4) + ord($str[$i]);
  106.  
  107. if(($test = $hash & -268435456)  != 0)
  108. {
  109. $hash = (( $hash ^ ($test>> 24)) & (~-268435456));
  110. }
  111. }
  112.  
  113. return $hash % 701819;
  114. }
  115.  
  116. function PHPHash($str) // 0.34
  117. {
  118. $hash = 0;
  119. $n = strlen($str);
  120.  
  121. for ($i = 0; $i <$n; $i++)
  122. {
  123. $hash = ($hash <<4) + ord($str[$i]);
  124. if (($g = ($hash & 0xF0000000)))
  125. {
  126. $hash = $hash ^ ($g>> 24);
  127. $hash = $hash ^ $g;
  128. }
  129. }
  130. return $hash % 701819;
  131. }
  132.  
  133. function OpenSSLHash($str) // 0.22
  134. {
  135. $hash = 0;
  136. $n = strlen($str);
  137.  
  138. for ($i = 0; $i <$n; $i++)
  139. {
  140. $hash ^= (ord($str[$i]) <<($i & 0x0f));
  141. }
  142. return $hash % 701819;
  143. }
  144.  
  145. function MD5Hash($str) // 0.050
  146. {
  147. $hash = md5($str);
  148. $hash = $hash[0] | ($hash[1] <<8 ) | ($hash[2] <<16) | ($hash[3] <<24) | ($hash[4] <<32) | ($hash[5] <<40) | ($hash[6] <<48) | ($hash[7] <<56);
  149. return $hash % 701819;
  150. }

 

算法的一些说明：

  1. 函数后面注释中是我本地测试的执行1000次的速度（单位：s），可以看出来MD5Hash是最快的，而且要比其他函数快很多很多...但是从这个函数的算法也可以看出来，它仅仅是依赖于md5后字符串的前7个字符，也就是说如果前7个字符相同的话那么获得的hash值是完全一样的，所以实际来说它的分布情况是不太令人信任的....如果按照32个字符来计算的话速度那就远远的慢于其他算法了...
  2. 除了MD5Hash，其他算法都会受到字符串长度的影响，越长越慢，我测试用的是10个字符的英文。
  3. 每个函数最后的 return $hash % 701819; 中 701819 表示是哈希的最大容积，也就是说这些哈希函数最后得到的数字范围是0~701819，这个数字是可以改的一般认为使用一个大的质数结果的分布会是比较均匀的，在 701819 附近的几个建议的值是：175447, 350899, 1403641, 2807303, 5614657。

    或许你又问了，这个到底可以用来做什么呢...
    呵呵，我来解释一下我为什么要整理 and 测试这些哈希算法，我在写多用户 Blog，恩...之前的日志里面也有提过，多用户 Blog 一般都有一个功能，那就是使用一个英文和数字组合的用户名来作为 Blog 的地址（二级域名或者目录）。那么就有一个问题了，如何根据用户名来获取用户的 ID，多一次查询吗？有了哈希函数就不用了，使用哈希函数处理用户名，得到一个数字，再对数字做一定的处理（我是按照2位分割成层次的目录，目的是防止一个目录下有太多的文件而影响磁盘检索速度），然后就形成了一个路径，把对应的ID保存在这个路径下的文件内（我个人推荐用户名做文件名），这样就可以根据用户名来直接获得用户的ID，不需要查询，用户名做文件名，所以即使最后结果相同也是在不同的文件中，所以可以不用担心出现碰撞。

    当然...如果你的系统完全是根据用户名来操作那当我前面这些都没说 = =b，悄悄的非议一句 SELECT 也是数字比字符串要快一些地。

    我选择的是DJB算法，等以后上线后如果测试MD5分布还算可以接受的话再考虑换用。

    从这里也可以看出来其实哈希对于分布还是很有用地，呵呵，可以用来作缓存，静态或者其他需要分布存储的东西上面，这都要看你怎么用了。

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞