用PHP实现的HashTable及说明

分类:PHP / 时间:2015-11-15 17:08


下面是用PHP实现的HashTable代码,其中需要说明的有两点: 1)代码中使用了 SplFixedArray ,这是一个更接近C语言的数组[Array],而且效率更高。使用之前需要开启SPL扩展,PHP5.3+默认开启。 2)代码中使用拉链法解决冲突,即将所有相同的Hash值的关键字节点链接在同一个链表中。

<?php
/**
 * Memcached常规应用演示
 * 天涯PHP博客
 * http://blog.phpha.com
 */
class HashNode {
	public $key;
	public $value;
	public $nextNode;

	public function __construct($key, $value, $nextNode = NULL) {
		$this->key = $key;
		$this->value = $value;
		$this->nextNode = $nextNode;
	}
}

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; /* 查找失败 */
	}
}

// 测试代码
$ht = new HashTable();
$ht->insert('key1', 'value1');
$ht->insert('key12', 'value12');
echo $ht->find('key1');
echo $ht->find('key12');
?>