PHP Core Technology and Best Practices Hash Table Conflict_PHP Tutorial

Hash table conflict between PHP core technology and best practices

Hash table conflict between PHP core technology and best practices

Following the previous article, after testing, output value1value2. When

$ht->insert(‘key12’,’value12’);

Echo $ht ->find(‘key12’);,

Found the output value12value12. What is the reason for this?

This problem is called a Hash table conflict. Since the insert is a string, the algorithm used is to add the ASIIC codes of the string. According to this method, a conflict occurs. By printing the Hash values ​​of key12 and key1, we find that they are both 8. In other words, value1 and value12 are stored at the 9th position of the Hash table at the same time (the index starts from 0), so the value of value1 is overwritten by value12. .

Commonly used methods to resolve conflicts are: open addressing method and zipper method. Because zippers are easy to understand, this article uses the zipper method to solve conflict problems.

Zipper method to resolve conflicts:

The approach is to link all key nodes with the same Hash value in the same linked list.

The zipper method connects key nodes with the same hash value in a linked list. Then when looking for elements, you must traverse the linked list and compare whether the keyword of each element in the linked list is equal to the searched keyword. If they are equal, This is the element we are looking for.

Because nodes need to save keywords (key) and data (value), and also record nodes with the same hash value. So create a HashNode class to store this information.

The structure of HashNode is as follows:

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

HashNode has 3 attributes: $key, $value, and $nextNode. $key is the key of the node, $value is the value of the node, and $nextNode is the pointer to the node with the same Hash value. Now modify the insertion method as follows:

Public function insert($key,$value){
                            $index= $this -> hashfunc($key);
                            //新建一个节点
       if(isset($this->buckets[$index])){
              $newNode = new HashNode($key,$value,$this->buckets[$index])
              }else{
                            $newNode = newHashNode($key,$value,null);
                            }
                            $this -> buckets[$index] = $newNode;//保存新节点
                     }

The modified insertion algorithm flow is as follows:

1) Use the Hash function to calculate the Hash value of the keyword, and locate the specified position in the Hash table through the Hash value.

2) If this position is already occupied by other nodes, point the new node's $nextNode to this node, otherwise set the new node's $nextNode to null.

3) Save the new node to the current location of the Hash table.

After these three steps, nodes with the same Hash value will be connected to the same linked list.

The search algorithm is correspondingly modified into the following format:

Public functionfind($key){
                           $index = $this ->hashfunc($key);
                           $current =$this->buckets[$index];
                           while(isset($current)){//遍历当前链表
                                  if($current->key== $key){  //比较当前节点的关键字
                                         return$current -> value;//查找成功
                                  }
                                  $current =$current ->nextNode;  //比较下一个节点
                           }
                           Return null;  //查找失败
               }

The modified search algorithm process is as follows:

1) Use the Hash function to calculate the Hash value of the keyword, and locate the specified position in the Hash table through the Hash value.

2) Traverse the current linked list and compare whether the key of each node in the linked list is equal to the search key. If they are equal, the search is successful.

3) If there is no keyword to be found in the entire linked list, the search fails.

After testing, the conflict problem was solved using the zipper method.

http://www.bkjia.com/PHPjc/984758.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/984758.htmlTechArticleHash table conflict between PHP core technology and best practices. Hash table conflict between PHP core technology and best practices continues. An article, after testing, output value1value2. When $ht-insert(key12,value12); Ech...