PHP实现的HashTable及说明

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

<?phphtml' target='_blank'>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.comclass 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);		/* 新创建一个节点 www.it165.net */		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');?>

原文地址: http://blog.phpha.com

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。