PHP Core Technology and Best Practices Hash Algorithm_PHP Tutorial

PHP Core Technology and Best Practices Hash Algorithm

PHP Core Technology and Best Practices Hash Algorithm

Hash table, also known as hash table, accesses records by mapping the keyword Key to a position in the array to speed up search. This mapping function is called a Hash function, and the array storing records is called a Hash table.

1. Hash function

The function is to convert an input of any length into a fixed-length output through the Hash algorithm, and the output is the Hash value. This conversion is a compression mapping, that is, the hash value space is usually much smaller than the input space. If no input is made, the hashing may result in the same output, and it is impossible to uniquely determine the input value from the hash value.

A good hash function should meet the following conditions: each keyword can be evenly distributed to any position in the Hash table, and does not conflict with other keywords that have been hashed into the Hash table. This is the most difficult thing to implement for the Hash function.

2. Hash algorithm

1) Direct remainder method

The direct remainder method is relatively simple. Just divide the keyword k by the size m of the Hash table to get the remainder. The algorithm is as follows:

H(k) = k mod m

For example: the size of the Hash table is m=12, and the given keyword is k=100, then h(k) = 4. This algorithm is a remainder operation and is relatively fast.

2) Product rounding method

The product rounding method first uses the keyword k times a constant A (0

H(k) = floor (m*(kA mod 1))

Among them, kA mod1 represents the decimal part of kA, and floor is the rounding operation.

When the keyword is a string, the above Hash algorithm cannot be used. Because a string is composed of characters, you can add up the ASCII codes of all the characters in the string to get an integer, and then calculate it according to the Hash algorithm above.

The algorithm is as follows:

Function hash($key,$m){

$strlen= strlen($key);

$hashval= 0;

For($i=0;$i< $strlen;$i ){

$hashval =ord($key{$I});

}

Return $hashval % $m;

}

3) Classic Hash algorithm Times33

Unsigned int DJBHash(char *str){

Unsignedint hash = 5381;

While(*str){

Hash =(hash <<5) (*str );

}

Return (hash &0x7FFFFFFF)

}

The algorithm idea is to continuously multiply by 33. Its efficiency and randomness are very good, and it is widely used in many open source projects, such as Apache, Perl and PHP.

3. Hash table

The time complexity of the Hash table is O(1), and the Hash table structure can be represented by a diagram:

To construct a Hash table, you must create an array large enough to store data, and you also need a Hash function to map the keyword Key to a certain position in the array.

Hash table implementation steps:

1) Create a fixed-size array to store data.

2) Design Hash function.

3) Map the keyword to a certain position in the array through the Hash function, and perform data access at this position.

4. Use PHP to implement Hash table

First create a HashTable class with two attributes $buckets and $size. $buckets is an array used to store data, and $size is used to record the size of the $buckets array. Then allocate memory for the $buckets array in the constructor. The code is as follows:

ClassHashTable{

Private$buckets;

Private$size =10;

Publicfunction __construct(){

$this-> buckets =new SplFixedArray($this->size);

}

}

?>

In the constructor, an array of size 10 is allocated for the $buckets array. The SPL extended SplFixedArray array is used here, not an ordinary array

This is because the SplFixedArray array is closer to the C language array and more efficient. An initial size needs to be provided when creating its array.

Note: To use the SplFixedArray array, the SPl extension must be enabled. If it is not enabled, you can use a normal array instead.

Then specify a Hash function for the Hash table. For the sake of simplicity, the simplest Hash algorithm is used here. That is, as mentioned above, add all the characters of the string and take the remainder. The code is as follows:

Public Function hashfunc($key){

$strlen= strlen($key);

$hashval= 0;

For($i=0;$i< $strlen;$i ){

$hashval =ord($key{$I});

}

Return $hashval % $this->size;

}

With the Hash function, you can implement the insertion and search methods. When inserting data, first calculate the location of the keyword in the Hash table through the Hash function, and then save the data to this location. The code is as follows:

Public function insert($key,$val){

$index= $this -> hashfunc($key);

$this-> buckets[$index] = $val;

}

The method of finding data is similar to the method of inserting data. First, calculate the position of the keyword in the Hash table through the Hash function, and then return the data at this position. The code is as follows:

Public function find($key){

$index= $this -> hashfunc($key);

Return$this ->buckets[$index];

}

At this point, a simple Hash table has been written. Let’s test this Hash table. The code list is as follows:

$ht= new HashTable();

$ht->insert(‘key1’,’value1’);

$ht->insert(‘key2’,’value2’);

Echo$ht ->find(‘key1’);

Echo$ht ->find(‘key2’);

?>

Full code: #hash.php

<!--?PHP
             Class HashTable{
                    Private$buckets;
                    Private $size=10;
                    Public function__construct(){
                           $this---> buckets =new SplFixedArray($this->size);
                    }
                    PublicFunction hashfunc($key){
                           $strlen= strlen($key);
                           $hashval= 0;
                           For($i=0;$i< $strlen;$i++){
                                  $hashval+=ord($key{$i});
                           }
                           return$hashval % $this->size;
                    }
                    Publicfunction insert($key,$val){
                           $index= $this -> hashfunc($key);
                           $this-> buckets[$index] = $val;
                    }
                    Publicfunction find($key){
                           $index= $this -> hashfunc($key);
                           Return$this ->buckets[$index];
                    }
 
 
             }
             $ht = newHashTable();
             $ht->insert(&#39;key1&#39;,&#39;value1&#39;);
             $ht->insert(&#39;key2&#39;,&#39;value2&#39;);
             Echo $ht->find(&#39;key1&#39;);
             Echo $ht->find(&#39;key2&#39;);
 
?>