php 实现Hash表功能实例详解

php 实现Hash表功能

Hash表作为最重要的数据结构之一，也叫做散列表。使用PHP实现Hash表的功能。PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数，存放记录的数组称为Hash表。

Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的hash。
Hash表的时间复杂度为O(1)

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

下面对我们的HashTable进行测试。

    <?php
    //测试1
    $arr = new HashTable();
    for($i=0; $i<15; $i++){
      $arr->set('key'.$i, 'value'.$i);
    }
    print_r($arr->getList());

    //测试2
    $arr->editSize(15);
    for($i=0; $i<15; $i++){
      $arr->set('key'.$i, 'value'.$i);
    }
    print_r($arr->getList());
    ?>

改变了值之后可以存放更多的元素。但是仍然存在不同的key可能产生相同的hash值，那么赋值的时候后操作会覆盖前操作的问题。这种冲突的问题我们来用拉链法解决。

拉链法解决冲突。拉链法解决冲突的做法是将所有的相同Hash值的key放在一个链表中，比如key3和key14在hash之后都是0，那么在数组的键为0的地方存储这两个值，形式是链表。如果不能理解我的文字，请看下面的示例，看一下打印信息就明白了。拉链法是什么，就是链表。

创建一个HashNode类，用来存储key和value的值，并且存储相同hash的另一个元素。在同一条链上，查找越后的元素越费时。时间复杂度为O(n).

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

对我们新的HashTable进行测试

    <?php
    //测试1
    $newArr = new NewHashTable();
    for($i=0; $i<30; $i++){
      $newArr->set('key'.$i, 'value'.$i);
    }
    print_r($newArr->getList());
    var_dump($newArr->get('key3'));
    ?>

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！