上一篇的搜索是不是感觉没完没了？因为我们真的接触到了时间复杂度的优化。从线性搜索的O(n)到半搜索的O(logN)绝对是质的飞跃。然而，我们二分查找的核心需求是什么？也就是说，原始数据必须是有序的。这是一件很麻烦的事情。毕竟如果数据量巨大的话，排序就会变得很麻烦。不过不用担心，我们今天要学习的哈希表查找是另一种形式的查找。它能做到什么程度？O(1)，是的，你没看错，哈希表搜索在最好的情况下能达到这种恒定的搜索效率，是不是很神奇？Hash哈希（取余法除外）下面通过一个实际的例子来看一个非常简单的哈希算法。在数据量比较大的情况下，我们往往需要对数据表进行表操作。最简单的方案就是根据某个字段取模，比如ID。也就是说，如果我们要划分20张表，那么就用数据的ID除以20，然后得到它的余数。然后将这条数据添加到余数对应的表中。我们通过代码来模拟这个操作。或($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。这样，我们就实现了最简单的数据分表的思路。当然，在实际的业务开发中，远比这复杂。因为我们考虑各种场景来确定分表的形式，分多少张表，以及后续的扩容。也就是说，真实情况比我们这里写的要复杂得多。作为演示代码，这个分表的哈希形式其实是哈希表查找中最经典最常用的除余留余法。其实还有其他的方法，比如取正方形中间的方法、折叠法、数字分析法等。他们的核心思想是通过哈希算法让原始数据对应一个新的值（位置）。类似的思路其实就是md5()最典型的hash操作，不同的内容会产生不同的值。另外，Redis、Memcached等键值对缓存数据库，其实就是将我们设置的Key值进行哈希处理，存储在内存中，实现快速查找的能力。哈希冲突问题（线性检测法）在上面的例子中，我们其实会发现一个问题，就是如果哈希算法的值很小，会出现很多重复的冲突数据。如果是真正的哈希表来存储数据，这样的存储其实并不能帮助我们快速准确的找到我们需要的数据。Search搜索，它的核心能力其实就是搜索。那么如果我们随机给一些数据，如何将它们保存在相同的长度内，避免冲突呢？这就是我们接下来要学习的哈希碰撞要解决的问题。$arr=[];$hashTable=[];for($i=0;$i<$hashKey;$i++){$r=rand(1,20);如果(!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,',value:',$arr[$i],PHP_EOL;$j=$arr[$i]%$hashKey+1;while(1){如果($j>=$hashKey){$j=0;}if(!$hashTable[$j]){$hashTable[$j]=$arr[$i];休息;$c++;$j++;如果($c>=$hashKey){中断;}}}}print_r($hashTable);这次我们只生成7个随机数据，让它们仍然以7为模除以余数。同时，我们还需要将他们的散列结果保存到另一个数组中，这个数组可以看作是内存中的一个空间。如果有相同hash的数据，当然不能放在同一个空间。如果同一个空间里有两份数据，我们就不知道到底要取哪份数据。在这段代码中，我们使用开放地址法中的线性探测法。这是处理散列冲突的最简单方法。我们先看一下输出，再分析一下冲突发生时我们做了什么。//数组//(//[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//数组//(//[3]=>17//[6]=>13//[2]=>9//[5]=>19//[4]=>2//[0]=>20//[1]=>12//)首先，我们生成的数是7个数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，找到that0没有被占用，所以20保存在下标0。最后12%7=5，会依次经过下标5、6、0、1，最后放到下标1处。最终generatedresult就是我们最终数组输出的结果。可见，线性检测其实就是发现位置被人占用，就一个一个向下搜索。所以它的时间复杂度其实不是很好。当然，最好的情况是数据的总长度与hashkey的长度相匹配，这样可以达到O(1)的级别。当然，除了线性检测，还有二次检测（平方）、伪随机检测等算法。另外，也可以用链表实现链地址法来解决哈希冲突的问题.这些内容可以参考相关文献或书籍。总结hash最终的查找作用其实和上面生成hash表的过程是一样的，解决冲突的方法也是一样的，这里就不多说了。对于哈希，无论是教材还是各种学习资料，介绍的内容都不是特别特别。因此，我们也以入门的心态简单了解一下哈希的知识。更多内容可以自行研究分享！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6。搜索/source/6.2Hashtablesearch.php参考文档：《数据结构》第二版，闫伟民《数据结构》第二版，陈越各自媒体平台可以搜索【硬核项目经理】
