用PHP实现的HashTable及说明

用PHP实现的HashTable及说明

最近在看凹凸曼和白菜写的书，500多页，其实我真正想看的是PHP扩展部分以及缓存部分。下面是凹凸曼用PHP实现的HashTable代码，其中需要说明的有两点：
1)代码中使用了 SplFixedArray ，这是一个更接近C语言的数组[Array]，而且效率更高。使用之前需要开启SPL扩展，PHP5.3+默认开启。
2)代码中使用拉链法解决冲突，即将所有相同的Hash值的关键字节点链接在同一个链表中。

	
	

		php
		

			class HashNode {
			

				 public $key;
				

					 public $value;
					

						 public $nextNode;
						

							 
							

								 public function __construct($key, $value, $nextNode = NULL) {
								

									 $this->key = $key;
									

										 $this->value = $value;
										

											 $this->nextNode = $nextNode;
											

												 }
												

													}
													

														//天涯PHP博客 http://blog.phpha.com
														

															class HashTable {
															

																 private $buckets;
																

																	 private $size = 10;
																	

																		 
																		

																			 public function __construct() {
																			

																				 $this->buckets = new SplFixedArray($this->size);
																				

																					 }
																					

																						 
																						

																							 private function hashfunc($key) {
																							

																								 $strlen = strlen($key);
																								

																									 $hashval = 0;
																									

																										 for ($i = 0; $i < $strlen; $i++) {
																										

																											 $hashval += ord($key{$i});
																											

																												 }
																												

																													 return $hashval % $this->size;
																													

																														 }
																														

																															 
																															

																																 public function insert($key, $value) {
																																

																																	 $index = $this->hashfunc($key);
																																	

																																		 /* 新创建一个节点 */
																																		

																																			 if (isset($this->buckets[$index])) {
																																			

																																				 $newNode = new HashNode($key, $value, $this->buckets[$index]);
																																				

																																					 } else {
																																					

																																						 $newNode = new HashNode($key, $value, NULL);
																																						

																																							 }
																																							

																																								 $this->buckets[$index] = $newNode; /* 保存新节点 */
																																								

																																									 }
																																									

																																										 
																																										

																																											 public function find($key) {
																																											

																																												 $index = $this->hashfunc($key);
																																												

																																													 $current = $this->buckets[$index];
																																													

																																														 while (isset($current)) { /* 遍历当前链表 */
																																														

																																															 if ($current->key == $key) { /* 比较当前节点的关键字 */
																																															

																																																 return $current->value; /* 查找成功 */
																																																

																																																	 }
																																																	

																																																		 $current = $current->nextNode; /* 比较下一个节点 */
																																																		

																																																			 }
																																																			

																																																				 return NULL; /* 查找失败 */
																																																				

																																																					 }
																																																					

																																																						}
																																																						

																																																							//天涯PHP博客 http://blog.phpha.com
																																																							

																																																								//******* 下面是测试代码 *******
																																																								

																																																									$ht = new HashTable();
																																																									

																																																										$ht->insert('key1', 'value1');
																																																										

																																																											$ht->insert('key12', 'value12');
																																																											

																																																												echo $ht->find('key1');
																																																												

																																																													echo $ht->find('key12');
																																																													

																																																														?>