- 服务端开发/管理
- 用PHP实现的HashTable及说明
PHP实现的HashTable代码，其中需要说明的有两点：
1)代码中使用了 SplFixedArray ，这是一个更接近C语言的数组[Array]，而且效率更高。使用之前需要开启SPL扩展，PHP5.3+默认开启。
2)代码中使用拉链法解决冲突，即将所有相同的Hash值的关键字节点链接在同一个链表中。
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');
