php数据列表PHP数据构造散列表查找

O(1) ，是的，你没看错，散列表查找在最佳情形下是可以达到这种常数级别的查找效率的，是不是很神奇。

哈希散列（除留余数法）

先通过实际的例子看一种非常大略的散列算法。
在数据量比较大的情形下，我们每每要对数据表进行表操作，最大略的一种方案便是根据某一个字段，比如说 ID 来对它进行取模。
也便是说，如果我们要分20张表，那么就用数据的 ID 来除以 20 ，然后得到它的余数。
然后将这条数据添加到余数所对应的这张表中。
我们通过代码来仿照这个操作。

or($i=0;$i<100;$i++){ $arr[] = $i+1;}$hashKey = 7;$hashTable = [];for($i=0;$i<100;$i++){ $hashTable[$arr[$i]%$hashKey][] = $arr[$i];}print_r($hashTable);

在这里，我们假设是将 100 条数据放到 7 张表中，便是直策应用取模运算符 % 来获取余数就行了，接着就将数据放入到对应的数组下标中。
这 100 个数据就被分别放置在了数组中 0-6 的下标中。
这样，我们就实现了最大略的一种数据分表的思想。
当然，在实际的业务开拓中要远比这个繁芜。
由于我们考虑各种不同的场景来确定到底因此什么形式进行分表，分多少张表，以及后续的扩展情形，也便是说，真实情形下要比我们这里写的这个繁芜很多。

php数据列表PHP数据构造散列表查找 Bootstrap

做为演示代码来说，这种分表的散列形式实在便是散列表查找中最经典也是利用最多的除留余数法。
实在还有其它的一些方法，比如平方取中法、折叠法、数字剖析法之类的方法。
它们的核心思想都是作为一个散列的哈希算法，让原始数据对应到一个新的值（位置）上。

类似的思想实在最范例的便是 md5() 的散列运算，不同的内容都会产生不同的值。
其余便是 Redis 、 Memcached 这类的键值对缓存数据库，它们实在也会将我们设置的 Key 值进行哈希后保存在内存中以实现快速的查找能力。

散列冲突问题（线性探测法）

上面的例子实在我们会创造一个问题，那便是哈希算法的这个值如果很小的话，就会有很多的重复冲突的数据。
如果是真实的一个存储数据的散列表，这样的存储实在并不能帮我们快速准确的找到所须要的数据。
查找查找，它核心的能力实在还是在查找上。
那么如果我们随机给定一些数据，然后在同样长度的范围内如何保存它们并且避免冲突呢？这便是我们接下来要学习的散列冲突要办理的问题。

$arr = [];$hashTable = [];for($i=0;$i<$hashKey;$i++){ $r = rand(1,20); if(!in_array($r, $arr)){ $arr[] = $r; }else{ $i--; }}print_r($arr);for($i=0;$i<$hashKey;$i++){ if(!$hashTable[$arr[$i]%$hashKey]){ $hashTable[$arr[$i]%$hashKey] = $arr[$i]; }else{ $c = 0; echo '冲突位置：', $arr[$i]%$hashKey, '，值：',$arr[$i], PHP_EOL; $j=$arr[$i]%$hashKey+1; while(1){ if($j>=$hashKey){ $j = 0; } if(!$hashTable[$j]){ $hashTable[$j] = $arr[$i]; break; } $c++; $j++; if($c >= $hashKey){ break; } } }}print_r($hashTable);

这回我们只天生 7 个随机数据，让他们依然以 7 为模进行除留取余。
同时，我们还须要将它们以哈希后的结果保存到另一个数组中，可以将这个新的数组看做是内存中的空间。
如果有哈希相同的数据，那当然就不能放在同一个空间了，要不同一个空间中有两条数据我们就不知道真正要取的是哪个数据了。

在这段代码中，我们利用的是开放地址法中的线性探测法。
这是最大略的一种处理哈希冲突的办法。
我们先看一下输出的结果，然后再剖析冲突的时候都做了什么。

// Array// (// [0] => 17 // 3// [1] => 13 // 6// [2] => 9 // 2// [3] => 19 // 5// [4] => 2 // 2 -> 3 -> 4// [5] => 20 // 6 -> 0// [6] => 12 // 5 -> 6 -> 0 -> 1// )// 冲突位置：2，值：2// 冲突位置：6，值：20// 冲突位置：5，值：12// Array// (// [3] => 17// [6] => 13// [2] => 9// [5] => 19// [4] => 2// [0] => 20// [1] => 12// )

首先，我们天生的数字是 17、13、9、19、2、20、12 这七个数字。

17%7=3，17 保存到下标 3 中。

13%7=6，13 保存到下标 6 中。

9%7=2，9 保存到下标 2 中。

19%7=5，19 保存到下标 5 中。

2%7=2，好了，冲突出现了，2%7 的结果也是 2 ，但是 2 的下标已经有人了，这时我们就从 2 开始今后再看 3 的下标有没有人，同样 3 也被占了，于是到 4 ，这时 4 是空的，就把 2 保存到了下标 4 中。

20%7=6，和上面一样，6 已经被占了，于是我们回到开始的 0 下标，创造 0 还没有被占，于是 20 保存到下标 0 中。

末了的 12%7=5，它将依次经由下标 5 、6 、0、1 末了放不才标 1 处。

末了天生的结果便是我们末了数组输出的结果。
可以看出，线性探测实在便是如果创造位置被人占了，就一个一个的向下查找。
以是它的韶光繁芜度实在并不是太好，当然，最佳情形是数据的总长度和哈希键值的长度相吻合，这样就能达到 O(1) 级别了。

当然，除了线性探测之外，还有二次探测（平方）、伪随机探测等算法。
其余也可以利用链表来实现链地址法来办理哈希冲突的问题。
这些内容大家可以自己查阅一下干系的文档或书本。

总结

哈希散列末了的查找功能实在就和我们上面天生那个哈希表的过程一样，创造有冲突的办理办法也是一样的，这里就不多说了。
对付哈希这块来说，不管是教材还是各种学习资料，实在先容的内容都并不是特殊的多，以是，我们也因此入门的心态来大略地理解一下哈希散列这块的知识，更多的内容大家可以自己研究多多分享哈！