利用PHP实现Hash表功能

<?php

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);
    }
}
?>

<?php
//测试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] =>
//)
?>

<?php
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;
    }
}
?>

<?php
//Hash表中的元素指针个数，每个指针都是int，存储hash链表的文件偏移量
define('DB_BUCKET_SIZE', 262144);
//每条记录的key的长度
define('DB_KEY_SIZE', 128);
//一条索引记录的长度
define('DB_INDEX_SIZE', DB_KEY_SIZE + 12);

//成功-返回码
define('DB_SUCCESS', 1);
//失败-返回码
define('DB_FAILURE', -1);
//key重复-返回码
define('DB_KEY_EXISTS', -2);

class DB{
    private $idx_fp;
    private $dat_fp;
    private $closed;

    /**
     * Description: 打开数据库
     * @param $pathName 数据文件的存放路径
     * @return mixed
     */
    public function open($pathName){
        $idx_path = $pathName . '.idx';
        $dat_path = $pathName . '.dat';
        if(!file_exists($idx_path)){
            $init = true;
            $mode = "w+b";
        }else{
            $init = false;
            $mode = 'r+b';
        }
        $this->idx_fp = fopen($idx_path, $mode);
        if(!$this->idx_fp){
            return DB_FAILURE;
        }
        if($init){
            //把0x00000000转换成无符号长整型的二进制
            $elem = pack('L', 0x00000000);
            for($i=0; $i< DB_BUCKET_SIZE; $i++){
                fwrite($this->idx_fp, $elem, 4);
            }
        }
        $this->dat_fp = fopen($dat_path, $mode);
        if(!$this->dat_fp){
            return DB_FAILURE;
        }

        return DB_SUCCESS;
    }

    /**
     * Description: Times33 Hash算法
     * @param $key
     * @return int
     */
    private function times33Hash($key){
        $len = 8;
        $key = substr(md5($key), 0, $len);
        $hash = 0;
        for($i=0; $i<$len; $i++){
            $hash += 33 * $hash + ord($key[$i]);
        }
        //0x7FFFFFFF：一个十六进制的数是4bit，8个就是32位，就是4字节，和一个int一样大。而F是1111，7是0111，那么这个十六进制的数就是头为0，其余为1的，首位是符号位，也就是说7fffffff是最大的整数。
        //& 0x7fffffff 可以保证返回的数是正整数
        return $hash & 0x7FFFFFFF;
    }

    /**
     * Description: 插入记录
     * @param $key
     * @param $value
     */
    public function add($key, $value){
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;

        $idxoff = fstat($this->idx_fp);
        $idxoff = intval($idxoff['size']);

        $datoff = fstat($this->dat_fp);
        $datoff = intval($datoff['size']);

        $keylen = strlen($key);
        $vallen = strlen($value);
        if($keylen > DB_KEY_SIZE){
            return DB_FAILURE;
        }
        //0表示这是最后一个记录，该链再无其他记录。
        $block = pack('L', 0x00000000);
        //键值
        $block .= $key;
        //如果键值的长度没有达到最大长度，则用0填充
        $space = DB_KEY_SIZE - $keylen;
        for($i=0; $i<$space; $i++){
            $block .= pack('C', 0x00);
        }
        //数据所在文件的偏移量
        $block .= pack('L', $datoff);
        //数据记录的长度
        $block .= pack('L', $vallen);
        //尽管SEEK_SET是默认值，但是显式声明了就不怕以后官方会改变了-.-
        fseek($this->idx_fp, $offset, SEEK_SET);
        //检测该key所对应的hash值是否存在了
        $pos = @unpack('L', fread($this->idx_fp, 4));
        $pos = $pos[1];
        //如果key不存在
        if($pos == 0){
            fseek($this->idx_fp, $offset, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $idxoff), 4);

            fseek($this->idx_fp, 0, SEEK_END);
            fwrite($this->idx_fp, $block, DB_INDEX_SIZE);

            fseek($this->dat_fp, 0, SEEK_END);
            fwrite($this->dat_fp, $value, $vallen);

            return DB_SUCCESS;
        }
        //如果key存在
        $found = false;
        while($pos){
            fseek($this->idx_fp, $pos, SEEK_SET);
            $tmp_block = fread($this->idx_fp, DB_INDEX_SIZE);
            $cpkey = substr($tmp_block, 4, DB_KEY_SIZE);
            //$cpkey==$key时返回0，小于返回负数，大于返回正数
            if(!strncmp($cpkey, $key, $keylen)){
                $dataoff = unpack('L', substr($tmp_block, DB_KEY_SIZE + 4, 4));
                $dataoff = $dataoff[1];
                $datalen = unpack('L', substr($tmp_block, DB_KEY_SIZE + 8, 4));
                $datalen = $datalen[1];
                $found = true;
                break;
            }
            $prev = $pos;
            $pos = @unpack('L', substr($tmp_block, 0, 4));
            $pos = $pos[1];
        }

        if($found){
            return DB_KEY_EXISTS;
        }
        fseek($this->idx_fp, $prev, SEEK_SET);
        fwrite($this->idx_fp, pack('L', $idxoff), 4);
        fseek($this->idx_fp, 0, SEEK_END);
        fwrite($this->idx_fp, $block, DB_INDEX_SIZE);
        fseek($this->dat_fp, 0, SEEK_END);
        fwrite($this->dat_fp, $value, $vallen);
        return DB_SUCCESS;
    }

    /**
     * Description: 查询一条记录
     * @param $key
     */
    public function get($key){
        //计算偏移量，key的hash值对索引文件的大小求模，再乘4。因为每个链表指针大小为4
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        //SEEK_SET是默认的
        fseek($this->idx_fp, $offset, SEEK_SET);
        $pos = unpack('L', fread($this->idx_fp, 4));
        $pos = $pos[1];

        $found = false;
        while($pos){
            fseek($this->idx_fp, $pos, SEEK_SET);
            $block = fread($this->idx_fp, DB_INDEX_SIZE);
            $cpkey = substr($block, 4, DB_KEY_SIZE);

            if(!strncmp($key, $cpkey, strlen($key))){
                $dataoff = unpack('L', substr($block, DB_KEY_SIZE + 4, 4));
                $dataoff = $dataoff[1];

                $datalen = unpack('L', substr($block, DB_KEY_SIZE + 8, 4));
                $datalen = $datalen[1];

                $found = true;
                break;
            }
            $pos = unpack('L', substr($block, 0, 4));
            $pos = $pos[1];
        }
        if(!$found){
            return null;
        }
        fseek($this->dat_fp, $dataoff, SEEK_SET);
        $data = fread($this->dat_fp, $datalen);
        return $data;
    }

    /**
     * Description: 删除
     * @param $key
     */
    public function delete($key){
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        fseek($this->idx_fp, $offset, SEEK_SET);
        $head = unpack('L', fread($this->idx_fp, 4));
        $head = $head[1];
        $curr = $head;
        $prev = 0;
        $found = false;
        while($curr){
            fseek($this->idx_fp, $curr, SEEK_SET);
            $block = fread($this->idx_fp, DB_INDEX_SIZE);

            $next = unpack('L', substr($block, 0, 4));
            $next = $next[1];

            $cpkey = substr($block, 4, DB_KEY_SIZE);
            if(!strncmp($key, $cpkey, strlen($key))){
                $found = true;
                break;
            }
            $prev = $curr;
            $curr = $next;
        }
        if(!$found){
            return DB_FAILURE;
        }
        //删除索引文件。
        if($prev == 0){
            fseek($this->idx_fp, $offset, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $next), 4);
        }else{
            fseek($this->idx_fp, $prev, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $next), 4);
        }
        return DB_SUCCESS;
    }

    public function close(){
        if(!$this->closed){
            fclose($this->idx_fp);
            fclose($this->dat_fp);
            $this->closed = true;
        }
    }
}
?>

<?php
//先include上面的类。。如果在同一个文件中就不用了。
//测试
$db = new DB();
$db->open('/var/www/data/');

$startTime = microtime(true);

//插入测试...插入10000条：成功，耗时： 793.48206520081ms
//for($i=0; $i<10000; $i++){
//    $db->add('key'.$i, 'value'.$i);
//}

//查找测试...查找10000条：成功，耗时： 149.08313751221ms
for($i=0; $i<10000; $i++){
    $db->get('key'.$i);
}

$endTime = microtime(true);
echo '成功，耗时： ' . (($endTime - $startTime)*1000) . 'ms';
$db->close();
?>