散列表查找

上篇文章的查找是不是有意犹未尽的感觉呢？因为我们是真真正正地接触到了时间复杂度的优化。从线性查找的 O(n) 直接优化到了折半查找的 O(logN) ，绝对是一个质的飞跃。但是，我们的折半查找最核心的一个要求是什么呢？那就是必须是原始数据是要有序的。这可是个麻烦事啊，毕竟如果数据量很庞大的话，排序又会变得很麻烦。不过别着急，今天我们要学习的散列表查找又是另一种形式的查找，它能做到什么程度呢？

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 的下标中。这样，我们就实现了最简单的一种数据分表的思想。当然，在实际的业务开发中要远比这个复杂。因为我们考虑各种不同的场景来确定到底是以什么形式进行分表，分多少张表，以及后续的扩展情况，也就是说，真实情况下要比我们这里写的这个复杂很多。

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

类似的思想其实最典型的就是 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) 级别了。

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