当前位置：首页 > PHP教程 > php应用 > 列表

利用PHP实现Hash表功能

发布:smiling　来源: PHP粉丝网 　添加日期：2015-12-12 15:00:45　浏览: 评论：0　

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. //                        ) //phpfensi.com 
  196. // 
  197. //                ) 
  198. // 
  199. //        ) 
  200. // 
  201. //) 
  202. //string(6) "value3" 
  203. ?>

Tags: Hash函数 Hash表功能

分享到：

推荐文章

热门文章

最新评论文章