【原】PHP數(shù)據(jù)結(jié)構(gòu)-散列表查找

硬核項目經(jīng)理 2021-05-31

展開全文

散列表查找

上篇文章的查找是不是有意猶未盡的感覺呢？因為我們是真真正正地接觸到了時間復雜度的優(yōu)化。從線性查找的 O(n) 直接優(yōu)化到了折半查找的 O(logN) ，絕對是一個質(zhì)的飛躍。但是，我們的折半查找最核心的一個要求是什么呢？那就是必須是原始數(shù)據(jù)是要有序的。這可是個麻煩事啊，畢竟如果數(shù)據(jù)量很龐大的話，排序又會變得很麻煩。不過別著急，今天我們要學習的散列表查找又是另一種形式的查找，它能做到什么程度呢？

O(1) ，是的，你沒看錯，散列表查找在最佳情況下是可以達到這種常數(shù)級別的查找效率的，是不是很神奇。

哈希散列（除留余數(shù)法）

先通過實際的例子看一種非常簡單的散列算法。在數(shù)據(jù)量比較大的情況下，我們往往要對數(shù)據(jù)表進行表操作，最簡單的一種方案就是根據(jù)某一個字段，比如說 ID 來對它進行取模。也就是說，假如我們要分20張表，那么就用數(shù)據(jù)的 ID 來除以 20 ，然后獲得它的余數(shù)。然后將這條數(shù)據(jù)添加到余數(shù)所對應(yīng)的這張表中。我們通過代碼來模擬這個操作。

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);

在這里，我們假設(shè)是將 100 條數(shù)據(jù)放到 7 張表中，就是直接使用取模運算符 % 來獲取余數(shù)就行了，接著就將數(shù)據(jù)放入到對應(yīng)的數(shù)組下標中。這 100 個數(shù)據(jù)就被分別放置在了數(shù)組中 0-6 的下標中。這樣，我們就實現(xiàn)了最簡單的一種數(shù)據(jù)分表的思想。當然，在實際的業(yè)務(wù)開發(fā)中要遠比這個復雜。因為我們考慮各種不同的場景來確定到底是以什么形式進行分表，分多少張表，以及后續(xù)的擴展情況，也就是說，真實情況下要比我們這里寫的這個復雜很多。

做為演示代碼來說，這種分表的散列形式其實就是散列表查找中最經(jīng)典也是使用最多的除留余數(shù)法。其實還有其它的一些方法，比如平方取中法、折疊法、數(shù)字分析法之類的方法。它們的核心思想都是作為一個散列的哈希算法，讓原始數(shù)據(jù)對應(yīng)到一個新的值（位置）上。

類似的思想其實最典型的就是 md5() 的散列運算，不同的內(nèi)容都會產(chǎn)生不同的值。另外就是 Redis 、 Memcached 這類的鍵值對緩存數(shù)據(jù)庫，它們其實也會將我們設(shè)置的 Key 值進行哈希后保存在內(nèi)存中以實現(xiàn)快速的查找能力。

散列沖突問題（線性探測法）

上面的例子其實我們會發(fā)現(xiàn)一個問題，那就是哈希算法的這個值如果很小的話，就會有很多的重復沖突的數(shù)據(jù)。如果是真實的一個存儲數(shù)據(jù)的散列表，這樣的存儲其實并不能幫我們快速準確的找到所需要的數(shù)據(jù)。查找查找，它核心的能力其實還是在查找上。那么如果我們隨機給定一些數(shù)據(jù)，然后在同樣長度的范圍內(nèi)如何保存它們并且避免沖突呢？這就是我們接下來要學習的散列沖突要解決的問題。

$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 個隨機數(shù)據(jù)，讓他們依然以 7 為模進行除留取余。同時，我們還需要將它們以哈希后的結(jié)果保存到另一個數(shù)組中，可以將這個新的數(shù)組看做是內(nèi)存中的空間。如果有哈希相同的數(shù)據(jù)，那當然就不能放在同一個空間了，要不同一個空間中有兩條數(shù)據(jù)我們就不知道真正要取的是哪個數(shù)據(jù)了。

在這段代碼中，我們使用的是開放地址法中的線性探測法。這是最簡單的一種處理哈希沖突的方式。我們先看一下輸出的結(jié)果，然后再分析沖突的時候都做了什么。

// 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
// )

首先，我們生成的數(shù)字是 17、13、9、19、2、20、12 這七個數(shù)字。
17%7=3，17 保存到下標 3 中。
13%7=6，13 保存到下標 6 中。
9%7=2，9 保存到下標 2 中。
19%7=5，19 保存到下標 5 中。
2%7=2，好了，沖突出現(xiàn)了，2%7 的結(jié)果也是 2 ，但是 2 的下標已經(jīng)有人了，這時我們就從 2 開始往后再看 3 的下標有沒有人，同樣 3 也被占了，于是到 4 ，這時 4 是空的，就把 2 保存到了下標 4 中。
20%7=6，和上面一樣，6 已經(jīng)被占了，于是我們回到開始的 0 下標，發(fā)現(xiàn) 0 還沒有被占，于是 20 保存到下標 0 中。
最后的 12%7=5，它將依次經(jīng)過下標 5 、6 、0、1 最后放在下標 1 處。

最后生成的結(jié)果就是我們最后數(shù)組輸出的結(jié)果。可以看出，線性探測其實就是如果發(fā)現(xiàn)位置被人占了，就一個一個的向下查找。所以它的時間復雜度其實并不是太好，當然，最佳情況是數(shù)據(jù)的總長度和哈希鍵值的長度相吻合，這樣就能達到 O(1) 級別了。

當然，除了線性探測之外，還有二次探測（平方）、偽隨機探測等算法。另外也可以使用鏈表來實現(xiàn)鏈地址法來解決哈希沖突的問題。這些內(nèi)容大家可以自己查閱一下相關(guān)的文檔或書籍。

總結(jié)

哈希散列最后的查找功能其實就和我們上面生成那個哈希表的過程一樣，發(fā)現(xiàn)有沖突的解決方式也是一樣的，這里就不多說了。對于哈希這塊來說，不管是教材還是各類學習資料，其實介紹的內(nèi)容都并不是特別的多，所以，我們也是以入門的心態(tài)來簡單地了解一下哈希散列這塊的知識，更多的內(nèi)容大家可以自己研究多多分享哈！

測試代碼：

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

參考文檔：

《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴蔚敏

《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越