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;          //用于存儲(chǔ)數(shù)據(jù)的數(shù)組
    private $size = 12;          //記錄buckets 數(shù)組的大小
    public function __construct(){
         
        $this->buckets = new SplFixedArray($this->size);
        //SplFixedArray效率更高，也可以用一般的數(shù)組來(lái)代替
    }
     
    private function hashfunc($key){
        $strlen = strlen($key);  //返回字符串的長(zhǎng)度
        $hashval = 0;     
        for($i = 0; $i<$strlen ; $i++){
            $hashval +=ord($key[$i]); //返回ASCII的值
        }
        return $hashval%$this->size;    //    返回取余數(shù)后的值
    }
    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)){    //遍歷當(dāng)前鏈表
                if($current->key==$key){    //比較當(dāng)前結(jié)點(diǎn)關(guān)鍵字
                    return $current->value;
                }
                $current = $current->nextNode;
                //return $current->value;
            }
            return NULL;
        }
     
}

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;       //關(guān)鍵字
            public $value;     //數(shù)據(jù)
            public $nextNode;  //HASHNODE來(lái)存儲(chǔ)信息
            public function __construct($key,$value,$nextNode = NULL){
                        $this->key = $key;
                        $this->value = $value;
                        $this->nextNode = $nextNode;
                         
            }
         
}

Implement

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