PHP实现hash表

常用HASH函数

·直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。

<?php
/*/PHP实现hash表,步骤
1，创建一个固定大小的数组用于存放数据
2，设计hash函数
3，通过hash函数把关键字映射到数组的某个位置

*/
class HashTable{
	private $buckets;
	private $size=10;

	public function __construct(){
		$this->buckets=array();//创建一个数组存放数据
	}
	private function hashFunc($key){
		$strlen=strlen($key);
		$hashval=0;
		for($i=0;$i<$strlen;$i++){
			$hashval+=ord($key{$i});//取得$key字符串第$i个字符的ASCII值，然后累加
		}
		return $hashval%$this->size;
	}
	//有了hash函数，就可以实现插入和查找，插入数据时先通过hash函数计算关键字所在hash表的位置
	//然后把数据保存在此位置即可
	public function insert($key,$value){
		$index=$this->hashFunc($key);
		$this->buckets[$index]=$value;

	}
	//查找数据方法与插入数据类似，先通过hash函数计算关键字所在hash表的位置
	//然后返回此位置的数据即可
	public function find($key){
		$index=$this->hashFunc($key);
		return $this->buckets[$index];	
	}
}
//至此，一个简单的hash表编写完成，下面测试
$ht=new HashTable();
$ht->insert('key1','value1');//插入key1=>value1
$ht->insert('key2','value2');//插入key2=>value2
echo $ht->find('key1'),"<br />";//查找key1对应的数据
echo $ht->find('key2');//查找key2对应的数据

?>