利用PHP实现Hash表功能

class HashTable{
    private $arr = array();
    private $size = 10;
    public function __construct(){
        //SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。创建时需要指定尺寸
        $this->arr = new SplFixedArray($this->size);
    }

    /**
     * Description: 简单hash算法。输入key，输出hash后的整数
     * @param $key
     * @return int
     */
    private function simpleHash($key){
        $len = strlen($key);
        //key中每个字符所对应的ASCII的值
        $asciiTotal = 0;
        for($i=0; $i<$len; $i++){
            $asciiTotal += ord($key[$i]);
        }
        return $asciiTotal % $this->size;
    }

    /**
     * Description: 赋值
     * @param $key
     * @param $value
     * @return bool
     */
    public function set($key, $value){
        $hash = $this->simpleHash($key);
        $this->arr[$hash] = $value;
        return true;
    }

    /**
     * Description: 取值
     * @param $key
     * @return mixed
     */
    public function get($key){
        $hash = $this->simpleHash($key);
        return $this->arr[$hash];
    }

    public function getList(){
        return $this->arr;
    }

    public function editSize($size){
        $this->size = $size;
        $this->arr->setSize($size);
    }
}
?>

//测试1
$arr = new HashTable();
for($i=0; $i<15; $i++){
    $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
//SplFixedArray Object
//(
//    [0] => value14
//    [1] => value4
//    [2] => value5
//    [3] => value6
//    [4] => value7
//    [5] => value8
//    [6] => value10
//    [7] => value11
//    [8] => value12
//    [9] => value13
//)
//不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作。

//测试2
$arr->editSize(15);
for($i=0; $i<15; $i++){
    $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
//SplFixedArray Object
//(
//    [0] => value14
//    [1] => value4
//    [2] => value0
//    [3] => value1
//    [4] => value2
//    [5] => value3
//    [6] => value10
//    [7] => value11
//    [8] => value12
//    [9] => value13
//    [10] => value14
//    [11] => value9
//    [12] =>
//    [13] =>
//    [14] =>
//)
?>

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 NewHashTable{
    private $arr;
    private $size = 10;
    public function __construct(){
        $this->arr = new SplFixedArray($this->size);
    }
    private function simpleHash($key){
        $asciiTotal = 0;
        $len = strlen($key);
        for($i=0; $i<$len; $i++){
            $asciiTotal += ord($key[$i]);
        }
        return $asciiTotal % $this->size;
    }
    public function set($key, $value){
        $hash = $this->simpleHash($key);
        if(isset($this->arr[$hash])){
            $newNode = new HashNode($key, $value, $this->arr[$hash]);
        }else{
            $newNode = new HashNode($key, $value, null);
        }
        $this->arr[$hash] = $newNode;
        return true;
    }
    public function get($key){
        $hash = $this->simpleHash($key);
        $current = $this->arr[$hash];
        while(!empty($current)){
            if($current->key == $key){
                return $current->value;
            }
            $current = $current->nextNode;
        }
        return NULL;
    }
    public function getList(){
        return $this->arr;
    }
}
?>