用PHP实现的HashTable及说明

下面是用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');
?>