不晓得哪个

一些经典字符串哈希函数算法的 PHP 实现

记录一些经典字符串哈希函数算法,虽然是 PHP 的,但是很容易改为 C 的
转自:http://www.flyinghail.net/?p=65
注释:int ord ( string $string ) PHP中返回string字符串中首字母的ASCII码。

算法的一些说明:

  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。
   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.
      }


posted on 2009-12-24 17:36 缘分游走 阅读(1187) 评论(0)  编辑 收藏 引用 所属分类: 算法基础


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理