Hash table can be a very efficient data structure when it comes to search operations. Since hash tables store data in an associative manner, if we know where to look for the data, we can easily get the data quickly. In the hash table, each data has a unique index associated with it. If we know which index to look at, we can find the key very easily. Usually, in other programming languages, we have to use a separate hash function to calculate the hash index to store the value. The hash function is designed to generate the same index for the same key and also avoid collision. However, one of the great features of PHP is that PHP array itself is a hash table, in its underlying C implementation. Since an array is dynamic, we do not have to worry about the size of array or overflow array with many values. We need to store the values in an associative array so that we can associate the value with a key. The key can be the value itself if it is a string or an integer. Let's run an example to understand searching with a hash table:

$arr = [];
$count = rand(10, 30); 

for($i = 0; $i<$count;$i++) {     
    $val = rand(1,500);     
    $arr[$val] = $val;     
} 

$number = 100; 
if(isset($arr[$number])) { 
    echo "$number found "; 
} else { 
    echo "$number not found"; 
}

We have just built a simple random associative array where value and key are the same. Since we are using PHP array, though value can have a range of 1 to 500, the actual array size is anything from 10 to 30. If it were in any other language, we would have constructed an array with a size of 501 to accommodate this value to be a key. That is why the hash function is used to calculate the index. If we want, we can also use the PHP's built-in function for hashing:

string hash(string $algo ,string $data [,bool $raw_output = false ])

The first parameter takes the type of algorithm we want to use for hashing. We can choose from md5, sha1, sha256, crc32, and so on. Each of the algorithms produces a fixed length hash output, which we can use as key for our hash table.

If we look at our searching part, we can see that we are actually checking the associated index directly. This makes our searching in complexity O(1). In PHP, it might be beneficial to use the hash table for quick searching even without using the hash function. However, we can always use the hash function if we want.

So far, we have covered searching based on arrays and linear structures. We will now shift our focus to hierarchical data structure searching such as searching trees and graphs. Though we have not discussed graphs yet (we will discuss them in the next chapter), we will keep our focus on tree searching, which can also be applied in graph searching.