利用PHP实现Hash表功能

Hash算法我们多少会了解一点了，下面来介绍利用php实现Hash表的一个例子，希望这些例子可以给各位带来帮助。

Hash表作为最重要的数据结构之一，也叫做散列表。使用PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数，存放记录的数组称为Hash表。

Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。

Hash表的时间复杂度为O(1),代码如下:

1. <?php 
2.  
3. class HashTable{ 
4.     private $arr = array(); 
5.     private $size = 10; 
6.     public function __construct(){ 
7.         //SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。创建时需要指定尺寸 
8.         $this->arr = new SplFixedArray($this->size); 
9.     } 
10.  
11.     /** 
12.      * Description: 简单hash算法。输入key，输出hash后的整数 
13.      * @param $key 
14.      * @return int 
15.      */ 
16.     private function simpleHash($key){ 
17.         $len = strlen($key); 
18.         //key中每个字符所对应的ASCII的值 
19.         $asciiTotal = 0; 
20.         for($i=0; $i<$len; $i++){ 
21.             $asciiTotal += ord($key[$i]); 
22.         } 
23.         return $asciiTotal % $this->size; 
24.     } 
25.  
26.     /** 
27.      * Description: 赋值 
28.      * @param $key 
29.      * @param $value 
30.      * @return bool 
31.      */ 
32.     public function set($key, $value){ 
33.         $hash = $this->simpleHash($key); 
34.         $this->arr[$hash] = $value; 
35.         return true; 
36.     } 
37.  
38.     /** 
39.      * Description: 取值 
40.      * @param $key 
41.      * @return mixed 
42.      */ 
43.     public function get($key){ 
44.         $hash = $this->simpleHash($key); 
45.         return $this->arr[$hash]; 
46.     } 
47.  
48.     public function getList(){ 
49.         return $this->arr; 
50.     } 
51.  
52.     public function editSize($size){ 
53.         $this->size = $size; 
54.         $this->arr->setSize($size); 
55.     } 
56. } 
57. ?> 

下面对我们的HashTable进行测试,代码如下:

1. <?php 
2. //测试1 
3. $arr = new HashTable(); 
4. for($i=0; $i<15; $i++){ 
5.     $arr->set('key'.$i, 'value'.$i); 
6. } 
7. print_r($arr->getList()); 
8. //SplFixedArray Object 
9. //( 
10. //    [0] => value14 
11. //    [1] => value4 
12. //    [2] => value5 
13. //    [3] => value6 
14. //    [4] => value7 
15. //    [5] => value8 
16. //    [6] => value10 
17. //    [7] => value11 
18. //    [8] => value12 
19. //    [9] => value13 
20. //) 
21. //不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作。 
22.  
23. //测试2 
24. $arr->editSize(15); 
25. for($i=0; $i<15; $i++){ 
26.     $arr->set('key'.$i, 'value'.$i); 
27. } 
28. print_r($arr->getList()); 
29. //SplFixedArray Object 
30. //( 
31. //    [0] => value14 
32. //    [1] => value4 
33. //    [2] => value0 
34. //    [3] => value1 
35. //    [4] => value2 
36. //    [5] => value3 
37. //    [6] => value10 
38. //    [7] => value11 
39. //    [8] => value12 
40. //    [9] => value13 
41. //    [10] => value14 
42. //    [11] => value9 
43. //    [12] => 
44. //    [13] => 
45. //    [14] => 
46. //) 
47. ?> 

改变了值之后可以存放更多的元素。但是仍然存在不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作的问题。这种冲突的问题我们来用拉链法解决。

拉链法解决冲突。拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方存储这两个值，形式是链表。如果不能理解我的文字，请看下面的示例，看一下打印信息就明白了。拉链法是什么，就是链表。

创建一个HashNode类，用来存储key和value的值，并且存储相同hash的另一个元素。在同一条链上，查找越后的元素越费时。时间复杂度为O(n).代码如下:

1. <?php 
2. class HashNode{ 
3.     public $key; 
4.     public $value; 
5.     public $nextNode; 
6.     public function __construct($key, $value, $nextNode=Null){ 
7.         $this->key = $key; 
8.         $this->value = $value; 
9.         $this->nextNode = $nextNode; 
10.     } 
11. } 
12. class NewHashTable{ 
13.     private $arr; 
14.     private $size = 10; 
15.     public function __construct(){ 
16.         $this->arr = new SplFixedArray($this->size); 
17.     } 
18.     private function simpleHash($key){ 
19.         $asciiTotal = 0; 
20.         $len = strlen($key); 
21.         for($i=0; $i<$len; $i++){ 
22.             $asciiTotal += ord($key[$i]); 
23.         } 
24.         return $asciiTotal % $this->size; 
25.     } 
26.     public function set($key, $value){ 
27.         $hash = $this->simpleHash($key); 
28.         if(isset($this->arr[$hash])){ 
29.             $newNode = new HashNode($key, $value, $this->arr[$hash]); 
30.         }else{ 
31.             $newNode = new HashNode($key, $value, null); 
32.         } 
33.         $this->arr[$hash] = $newNode; 
34.         return true; 
35.     } 
36.     public function get($key){ 
37.         $hash = $this->simpleHash($key); 
38.         $current = $this->arr[$hash]; 
39.         while(!emptyempty($current)){ 
40.             if($current->key == $key){ 
41.                 return $current->value; 
42.             } 
43.             $current = $current->nextNode; 
44.         } 
45.         return NULL; 
46.     } 
47.     public function getList(){ 
48.         return $this->arr; 
49.     } 
50. } 
51. ?> 

对我们新的HashTable进行测试,代码如下:

1. <?php 
2. //测试1 
3. $newArr = new NewHashTable(); 
4. for($i=0; $i<30; $i++){ 
5.     $newArr->set('key'.$i, 'value'.$i); 
6. } 
7. print_r($newArr->getList()); 
8. var_dump($newArr->get('key3')); 
9. //SplFixedArray Object 
10. //( 
11. //    [0] => HashNode Object 
12. //( 
13. //    [key] => key23 
14. //            [value] => value23 
15. //            [nextNode] => HashNode Object 
16. //( 
17. //    [key] => key14 
18. //                    [value] => value14 
19. //                    [nextNode] => HashNode Object 
20. //( 
21. //    [key] => key3 
22. //                            [value] => value3 
23. //                            [nextNode] => 
24. //                        ) 
25. // 
26. //                ) 
27. // 
28. //        ) 
29. // 
30. //    [1] => HashNode Object 
31. //( 
32. //    [key] => key24 
33. //            [value] => value24 
34. //            [nextNode] => HashNode Object 
35. //( 
36. //    [key] => key15 
37. //                    [value] => value15 
38. //                    [nextNode] => HashNode Object 
39. //( 
40. //    [key] => key4 
41. //                            [value] => value4 
42. //                            [nextNode] => 
43. //                        ) 
44. // 
45. //                ) 
46. // 
47. //        ) 
48. // 
49. //    [2] => HashNode Object 
50. //( 
51. //    [key] => key25 
52. //            [value] => value25 
53. //            [nextNode] => HashNode Object 
54. //( 
55. //    [key] => key16 
56. //                    [value] => value16 
57. //                    [nextNode] => HashNode Object 
58. //( 
59. //    [key] => key5 
60. //                            [value] => value5 
61. //                            [nextNode] => 
62. //                        ) 
63. // 
64. //                ) 
65. // 
66. //        ) 
67. // 
68. //    [3] => HashNode Object 
69. //( 
70. //    [key] => key26 
71. //            [value] => value26 
72. //            [nextNode] => HashNode Object 
73. //( 
74. //    [key] => key17 
75. //                    [value] => value17 
76. //                    [nextNode] => HashNode Object 
77. //( 
78. //    [key] => key6 
79. //                            [value] => value6 
80. //                            [nextNode] => 
81. //                        ) 
82. // 
83. //                ) 
84. // 
85. //        ) 
86. // 
87. //    [4] => HashNode Object 
88. //( 
89. //    [key] => key27 
90. //            [value] => value27 
91. //            [nextNode] => HashNode Object 
92. //( 
93. //    [key] => key18 
94. //                    [value] => value18 
95. //                    [nextNode] => HashNode Object 
96. //( 
97. //    [key] => key7 
98. //                            [value] => value7 
99. //                            [nextNode] => 
100. //                        ) 
101. // 
102. //                ) 
103. // 
104. //        ) 
105. // 
106. //    [5] => HashNode Object 
107. //( 
108. //    [key] => key28 
109. //            [value] => value28 
110. //            [nextNode] => HashNode Object 
111. //( 
112. //    [key] => key19 
113. //                    [value] => value19 
114. //                    [nextNode] => HashNode Object 
115. //( 
116. //    [key] => key8 
117. //                            [value] => value8 
118. //                            [nextNode] => 
119. //                        ) 
120. // 
121. //                ) 
122. // 
123. //        ) 
124. // 
125. //    [6] => HashNode Object 
126. //( 
127. //    [key] => key29 
128. //            [value] => value29 
129. //            [nextNode] => HashNode Object 
130. //( 
131. //    [key] => key10 
132. //                    [value] => value10 
133. //                    [nextNode] => HashNode Object 
134. //( 
135. //    [key] => key9 
136. //                            [value] => value9 
137. //                            [nextNode] => 
138. //                        ) 
139. // 
140. //                ) 
141. // 
142. //        ) 
143. // 
144. //    [7] => HashNode Object 
145. //( 
146. //    [key] => key20 
147. //            [value] => value20 
148. //            [nextNode] => HashNode Object 
149. //( 
150. //    [key] => key11 
151. //                    [value] => value11 
152. //                    [nextNode] => HashNode Object 
153. //( 
154. //    [key] => key0 
155. //                            [value] => value0 
156. //                            [nextNode] => 
157. //                        ) 
158. // 
159. //                ) 
160. // 
161. //        ) 
162. // 
163. //    [8] => HashNode Object 
164. //( 
165. //    [key] => key21 
166. //            [value] => value21 
167. //            [nextNode] => HashNode Object 
168. //( 
169. //    [key] => key12 
170. //                    [value] => value12 
171. //                    [nextNode] => HashNode Object 
172. //( 
173. //    [key] => key1 
174. //                            [value] => value1 
175. //                            [nextNode] => 
176. //                        ) 
177. // 
178. //                ) 
179. // 
180. //        ) 
181. // 
182. //    [9] => HashNode Object 
183. //( 
184. //    [key] => key22 
185. //            [value] => value22 
186. //            [nextNode] => HashNode Object 
187. //( 
188. //    [key] => key13 
189. //                    [value] => value13 
190. //                    [nextNode] => HashNode Object 
191. //( 
192. //    [key] => key2 
193. //                            [value] => value2 
194. //                            [nextNode] => 
195. //                        ) //Vevb.com 
196. // 
197. //                ) 
198. // 
199. //        ) 
200. // 
201. //) 
202. //string(6) "value3" 
203. ?>