PHP implements HASH table-PHP源码-php.cn

PHP implements HASH table

大家讲道理

Release： 2016-11-09 14:43:05

Original

1403 people have browsed it

Hash table is also called hash table. The key is mapped to a position in the array to access the record.

The function of the Hash function is to transform the input of any length into a fixed-length output through the HASH algorithm. The output is the HASH value

The time complexity of the HASH table is O(1)

The following uses the direct remainder method to implement

Create a hashtable

class HashTable{
     
    private $buckets;          //用于存储数据的数组
    private $size = 12;          //记录buckets 数组的大小
    public function __construct(){
         
        $this->buckets = new SplFixedArray($this->size);
        //SplFixedArray效率更高，也可以用一般的数组来代替
    }
     
    private function hashfunc($key){
        $strlen = strlen($key);  //返回字符串的长度
        $hashval = 0;     
        for($i = 0; $i<$strlen ; $i++){
            $hashval +=ord($key[$i]); //返回ASCII的值
        }
        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];
            echo "</br>";
            var_dump($current);
            while(isset($current)){    //遍历当前链表
                if($current->key==$key){    //比较当前结点关键字
                    return $current->value;
                }
                $current = $current->nextNode;
                //return $current->value;
            }
            return NULL;
        }
     
}

Copy after login

The above may have conflict problems, such as inserting two elements pointed to by the HASH table, second The HASH value of an element is the same as the first HASH value. Then the second element will overwrite the value of the first element. At this time, we use the zipper method to resolve the conflict: Byte points with the same HASH value are linked in the same in the linked list. When looking for this element, you must traverse the linked list.

Create HASHNODE

class HashNode{
            public $key;       //关键字
            public $value;     //数据
            public $nextNode;  //HASHNODE来存储信息
            public function __construct($key,$value,$nextNode = NULL){
                        $this->key = $key;
                        $this->value = $value;
                        $this->nextNode = $nextNode;
                         
            }
         
}

Copy after login

Implement

    $ht = new HashTable();
     $ht->insert(&#39;key1&#39;,&#39;value1&#39;);
     //$ht->insert(&#39;key12&#39;,&#39;value12&#39;);
        echo $ht->find(&#39;key1&#39;);

Copy after login