PHP实现哈希表和快速排序

介绍：

本文用PHP封装了一个哈希表结构，通过拉链法解决哈希冲突，封装的快速排序与本哈希表相适应，可通过不同的键值进行排序。

代码如下：

<?php
class hashNode{
    public $key;
    public $val;
    public $nextNode;

    /**
     * Description:构造函数
     * @param $key
     * @param $value
     * @param $nextNode
     */
    public function __construct($key,$val,$nextNode=null){
        $this->key = $key;
        $this->val = $val;
        $this->nextNode = $nextNode;
    }
}
class hashTable{
    private $collection;
    public $size = 20;

    /**
     * Description:初始化哈希表
     * @param $size
     */
    public function __construct($size=''){
        if(is_int($size)){
            $bucketsSize = $size;
            $this->size = $size;
        }else{
            $bucketsSize = $this->size;
        }
        $this->collection = new SplFixedArray($bucketsSize);
    }

    /**
     * Description:哈希算法，生成散列值，作为存储数据的下标
     * @param $key
     * @return int
    */
    private function  _hashAlgorithm($key){
        $length = strlen($key);
        $hashValue = 0;
        for($i=0;$i<$length;$i++){
            $hashValue += ord($key[$i]);//ord函数获得字符的ASCII码
        }
        return ($hashValue%($this->size));
    }

    /**
     * Description:在相应的位置存储对应的值
     * @param $key
     * @param $val
     */
    public function set($key,$val){
        $index = $this->_hashAlgorithm($key);
        if(isset($this->collection[$index])){
            $newNode = new hashNode($key,$val,$this->collection[$index]);
        }else{
            $newNode = new hashNode($key,$val,null);
        }
        $this->collection[$index] = $newNode;
    }

    /**
     * Description:根据key生成的散列值，找到对应的值
     * @param $key
     * @return hashNode
     */
    public function get($key){
        $index = $this->_hashAlgorithm($key);
        $current = $this->collection[$index];
        while(!empty($current)){
            if($current->key == $key){
                return $current->val;
            }
            $current = $current->nextNode;
        }
        return null;
    }

    /**
     * Description:设置哈希表的大小
     * @param $size
     */
    public function editSize($size){
        $this->size = $size;
        $this->collection->setSize($size);
    }

    /**
     * Description:删除某个值，成功返回1，失败返回0
     * @param $key
     * @return bool
     */
    public function del($key)
    {
        return 0;
    }

    /**
     * Description:判断某个值是否存在，存在则返回1，不存在返回0
     * @param $key
     * @return bool
     */
    public function exist($key){
        $index = $this->_hashAlgorithm($key);
        $current = $this->collection[$index];
        while(!empty($current)){
            if($current->key == $key){
                return 1;
            }
        }
        return 0;
    }

    /**
     * Description:返回存储元素的个数
     * @return int
     */
    public function size(){
        $size = 0;
        $length = $this->size;
        for($i=0;$i<$length;$i++){
            $current = $this->collection[$i];
            while(!empty($current)){
                $size++;
                $current = $current->nextNode;
            }
        }
        return $size;
    }

    /**
     * Description:列出哈希表内保存的值
     * @return SplFixedArray
     */
    public function getList(){
        return $this->collection;
    }

    /**
     * Description：根据hashTable数组的某一个key进行排序
     * @param $hashArr
     * @param $key
     * @return array：排序后的数组
     */
    public static function qsort($hashArr,$key){
        //先判断是否需要继续进行
        $length = count($hashArr);
        if($length <= 1) {
            return $hashArr;
        }
        $base_num = $hashArr[0]; //选择标尺
        //遍历 除了标尺外的所有元素，按照大小关系放入两个数组内
        $left_array = array();//小于标尺的
        $right_array = array();//大于标尺的
        for($i=1; $i<$length; $i++) {
            if($base_num->get($key) > $hashArr[$i]->get($key)) {
                $left_array[] = $hashArr[$i];//放入左边数组
            } else {
                $right_array[] = $hashArr[$i];//放入右边数组
            }
        }
        /*再分别对左边和右边的数组进行相同的排序处理方式
        递归调用这个函数,并记录结果*/
        $left_array = self::qsort($left_array,$key);
        $right_array = self::qsort($right_array,$key);
        //合并左边 标尺 右边

        return array_merge($left_array, array($base_num), $right_array);
    }
}

后记：

PHP自带的数组array就有哈希表的功能，所以本文其实并没有什么实用价值，但是可以较容易的理解哈希表结构和快速排序算法。至于我为什么要自己封装……课程所逼 = =。