乐趣区

关于php:PHP数据结构散列表查找

jiezi

上篇文章的查找是不是有意犹未尽的感觉呢？因为咱们是真真正正地接触到了工夫复杂度的优化。从线性查找的 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) 级别了。

当然，除了线性探测之外，还有二次探测（平方）、伪随机探测等算法。另外也能够应用链表来实现链地址法来解决哈希抵触的问题。这些内容大家能够本人查阅一下相干的文档或书籍。

总结

哈希散列最初的查找性能其实就和咱们下面生成那个哈希表的过程一样，发现有抵触的解决形式也是一样的，这里就不多说了。对于哈希这块来说，不论是教材还是各类学习材料，其实介绍的内容都并不是特地的多，所以，咱们也是以入门的心态来简略地理解一下哈希散列这块的常识，更多的内容大家能够本人钻研多多分享哈！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6. 查找 /source/6.2 散列表查找.php

参考文档：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

各自媒体平台均可搜寻【硬核项目经理】

退出移动版