zhangyue0503#Data-structure-and-algorithm#6.2散列表查找1

# 散列表查找 上篇文章的查找是不是有意犹未尽的感觉呢？因为我们是真真正正地接触到了时间复杂度的优化。从线性查找的 O(n) 直接优化到了折半查找的 O(logN) ，绝对是一个质的飞跃。但是，我们的折半查找最核心的一个要求是什么呢？那就是必须是原始数据是要有序的。这可是个麻烦事啊，毕竟如果数据量很庞大的话，排序又会变得很麻烦。不过别着急，今天我们要学习的散列表查找又是另一种形式的查找，它能做到什么程度呢？ O(1) ，是的，你没看错，散列表查找在最佳情况下是可以达到这种常数级别的查找效率的，是不是很神奇。 ## 哈希散列（除留余数法） 先通过实际的例子看一种非常简单的散列算法。在数据量比较大的情况下，我们往往要对数据表进行表操作，最简单的一种方案就是根据某一个字段，比如说 ID 来对它进行取模。也就是说，假如我们要分20张表，那么就用数据的 ID 来除以 20 ，然后获得它的余数。然后将这条数据添加到余数所对应的这张表中。我们通过代码来模拟这个操作。 ```php 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 的下标中。这样，我们就实现了最简单的一种数据分表的思想。当然，在实际的业务开发中要远比这个复杂。因为我们考虑各种不同的场景来确定到底是以什么形式进行分表，分多少张表，以及后续的扩展情况，也就是说，真实情况下要比我们这里写的这个复杂很多。 做为演示代码来说，这种分表的散列形式其实就是散列表查找中最经典也是使用最多的除留余数法。其实还有其它的一些方法，比如