天天看點
傳回

音視訊開發之旅（29) 算法序列 - 散清單目錄

目錄

  1. 基本概念
  2. 散清單的構造
  3. 散清單的碰撞處理
  4. 代碼實作
  5. 資料
  6. 收獲

前面兩篇我們學習實踐的二叉查找樹和平衡二叉樹以及有序數組的二分查找、單連結清單的逐個查找，都需要進行比較和遞歸。那麼有沒有其他的查詢技術呢？通過下圖可以看到散清單我們還沒有涉及，今天我們就來對散清單（哈希表）進行學習實踐。

音視訊開發之旅（29) 算法序列 - 散清單目錄

圖檔來源于《算法》

一、基本概念

散列技術，不需要比較和遞歸。通過記錄存儲位置和它的關鍵字之間建立一個确定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)

把這種對應關系f稱為散列函數，或者哈希函數。

采用散列技術将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或者哈希表（Hash table）

散清單的适用範圍，針對一對一，有映射關系 查找效率比較高。一旦出現key重複的情況，查找效率就變低了。

散清單的查找步驟

  1. 存儲時，通過散列函數計算出要存儲的值對應的散列位址
  2. 當查找時，通過同樣的散列函數要查找值的散列位址，并按照散列位址通路

二、散清單的構造方式

散清單的構造過程是 根據散列函數，把對應的key映射到對應的存儲位址

散列函數的好壞直接影響散清單插入和查詢的效率。

好的散列函數衡量的兩個名額是 計算簡單、分布均勻。

常見散列函數：有直接定值法、數字分析法、平法取中法、折疊法以及除留餘數法等。除留餘數法的效率一般情況下優于其他幾種類型的散列函數，也是最常用的散列函數。這篇來學習實踐通過除留餘數法的方式構造散清單

對于散清單長度為m，其對應的除留餘數法散列函數計算公式如下：

f(key) = key mod p. (p<=m)

這裡的key就是要插入或者查詢的值，mod是除留運算，p是取模的分母，一般p的值小于等于散清單的長度m。

a={12,25,38,15,16,29,78,67,56,21,22,47}
對于這個長為12數組，我們通過除留餘數法進行散清單的構造
12 % 12 = 0
25 % 12 = 1
38 % 12 = 2
15 % 12 = 3
16 % 12 = 4
29 % 12 = 5
78 % 12 = 6
67 % 12 = 7
56 % 12 = 8
21 % 12 = 9
22 % 12 = 10 
47 % 12 = 11

上述數組是比較理想的情況，除留運算後沒有出現沖突，但是如果把數組改成如下值就會出現碰撞的情況

a={12,24,38,15,16,29,78,67,50,21,22,47}
對于這個長為12數組，我們通過除留餘數法進行散清單的構造
12 % 12 = 0
24 % 12 = 0 --》出現了碰撞
38 % 12 = 2
15 % 12 = 3
16 % 12 = 4
29 % 12 = 5
78 % 12 = 6
67 % 12 = 7
50 % 12 = 2 --》出現了碰撞
21 % 12 = 9
22 % 12 = 10 
47 % 12 = 11

這針對這種情況，我們該怎麼處理呐？

三、散清單碰撞處理

一個散列函數能夠将鍵轉為數組索引，但是會出現兩個或多個鍵的散列值相同的情況，即發生碰撞，處理碰撞的兩種常用的方法是線性探測法和拉鍊法，下面我們一一學習實踐。

3.1 線性探測(LinearProbingHashST)

用大小為M的數組儲存N個鍵值對，其中M>N, 然後發生碰撞時，利用空位置進行處理。這類政策稱為開放位址散清單，開放位址散清單最常見的方法就是線性探索法。

當碰撞發生時【當一個鍵的散列值f(k1),被另外一個不同的鍵k2占用】, 采用直接檢查散清單中下一個位置，如果該位置沒有被占用，則把k1存儲在f(k1)+1的位置，否則繼續+1探測，他對應的公式如下：

f(key) = (f(key)+d) MOD m. (D = 1,2,…,m-1)

我們來看下如何解決上一小節的碰撞問題

a={12,24,38,15,16,29,78,67,50,21,22,47}
對于這個長為12數組，我們通過除留餘數法進行散清單的構造
12 % 12 = 0
24 % 12 = 0 --》出現了碰撞 （（24 % 12）+1）% 12 = 1
38 % 12 = 2
15 % 12 = 3
16 % 12 = 4
29 % 12 = 5
78 % 12 = 6
67 % 12 = 7
50 % 12 = 2 --》出現了碰撞 （（50 % 12）+1）% 12 = 3，但是散列值為3的位置已經被15占用了，我們繼續+1 探測，一直加到6時 （（50 % 12）+6）% 12 = 8
21 % 12 = 9
22 % 12 = 10 
47 % 12 = 11

3.2 拉鍊法 (SeparateChainingHashST)

解決沖突的方式，處理上面介紹的開放尋址線形探測法外，還有一種比較常用的方式是拉鍊法：将大小為M的數組中的每個元素都指向一條連結清單，連結清單中的每個結點都存儲了散列值為該元素索引的鍵值對。

這種方式的基本思想就是 選擇足夠大的數組M，使得所有連結清單都盡可能短，以保證高效的查詢。

使用拉鍊法存儲解決沖突，對應的查找分為兩步

  1. 根據散列值找到對應的連結清單，
  2. 沿着連結清單順序查找相應的鍵。
    音視訊開發之旅（29) 算法序列 - 散清單目錄

四、散清單代碼實作

下面我們實作開放尋址線形探索方式解決碰撞，詳見代碼注釋

#include<iostream>

const int DefaultSize = 128;
using std::cout;
using std::endl;
 
enum NodeInfo { Empty, Active };//記錄節點的狀态
 
template<typename T>
class HashTable
{
public:
    HashTable(int d,int sz= DefaultSize);
    ~HashTable();
    void printValue();
 
    bool search(const T& k);//檢視鍵k是否存在
    bool insert(const T& k);//插入鍵k

 
private:
 
    //尋找鍵k在哈希表的存儲數組中對應的位置

    int findPosByLinearProbing(const T& k)const;  //使用線性探查法

 
    int curSize; //curSize存儲目前哈希表存儲節點的數量
    int maxSize; //maxSize為哈希表最多存儲的節點的數量

    NodeInfo* info;//存儲每個節點的狀态數組，作為輔助數組

    int mod;//散列函數的MOD

    T* value;//哈希表的存儲節點的數組
};
 
 
template<typename K>
HashTable<K>::HashTable(int d, int sz)
{
    mod = d;
    maxSize = sz;
    curSize = 0;
    value = new K[maxSize];
    info = new NodeInfo[maxSize];

    for (int i = 0; i < maxSize; i++)//所有節點狀态都設為空
        info[i] = Empty;
}
 
 template<typename K>
HashTable<K>::~HashTable()
{
    if (value) delete[] value;
    if (info) delete[] info;
}

template<typename K>
void HashTable<K>::printValue()
{
    for (int i = 0; i < maxSize; i++)
    {
        if (info[i] == Active) cout << value[i] << " ";
        else cout << 0 << " ";
    }
    cout << endl;
}
 
//檢視鍵碼k是否存在
template<typename K>
bool HashTable<K>::search(const K& k)
{

    
    if (findPosByLinearProbing(k) >= 0)
    {
        return true;
    }
        
    return false;
}
 
template<typename K>
bool HashTable<K>::insert(const K& k)
{
    if (findPosByLinearProbing(k) >= 0) return false;

    int i = k % mod;
    int j = i;//j作為移動的指針
    do
    {
        if (info[j] == Empty) {//當節點狀态為空時，進行插入，否則j将一直移動下去
            value[j] = k;
            info[j] = Active;
            curSize++;
            return true;
        }
        else
            j = (j + 1) % maxSize;
    } while (j != i);
    return false;
}
 
 
//尋找鍵k在哈希表的存儲數組中對應的位置，使用線性探測法
template<typename K>
int HashTable<K>::findPosByLinearProbing(const K& k) const
{
    int i = k % mod;
    if (info[i] == Empty) return -1;//如果info狀态為空，那麼該鍵碼不存在哈希表中
    int j = i;//j作為移動的指針
    do
    {
        if (info[j] == Active && value[j] == k) return j;//如果節點轉态為Active，且value數組在j處值為k
        j = (j + 1) % maxSize;//位移
    } while (j != i);
    return -1;
}
 

int main()
{
    HashTable<int> myhash(12, 12);
    int a[] = { 12,38,24,15,16,29,78,47,67,50,21,22};
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        myhash.insert(a[i]);
    }
        
    myhash.printValue();
    return 1;
}

我們可以看到散清單的代碼相比二叉查找樹、平衡二叉樹更簡單，當然相比二叉樹，散清單需要設計散列函數。性能對比如下

音視訊開發之旅（29) 算法序列 - 散清單目錄

圖檔來源于《算法》

關于查找算法我們就先學習實踐到這裡，從下一片我們繼續CPP的其他學習，歡迎關注公衆号“音視訊開發之旅”，一起學習成長。

五、 資料

《算法》

[【C語言描述】《資料結構和算法》（小甲魚）] : https://www.bilibili.com/video/BV1jW411K7yg?p=84

[5分鐘學會最經典的資料結構哈希表，C語言手寫實作，不要錯過呀]

https://www.bilibili.com/video/BV1cX4y1K7Tk?from=search&seid=7155283358352562628

[資料結構與算法基礎--第13周10--7.4散清單的查找6--7.4.4散清單的查找及性能分析] : https://www.bilibili.com/video/BV1ot411q7SM?from=search&seid=7155283358352562628

[散清單C++實作] : https://blog.csdn.net/candand_python/article/details/107505740

六、收獲

  1. 了解了散清單的實作和原理
  2. 散清單解決沖突的常用方法
  3. 代碼實作散清單查詢

感謝你的閱讀

算法系列到這篇就結束了，從下一篇開始我們繼續CPP檔案操作、異常處理、線程等相關知識的學習，歡迎關注公衆号“音視訊開發之旅”，一起學習成長。

另外從今天開始2周的假期，做個挑戰的事情，每天寫一篇公衆号文章，主題會分為兩塊，“音視訊開發之旅”相關的cpp和ffmpeg，以及android的一些開源項目源碼解析系列。

歡迎交流

音視訊開發之旅 android c++ 算法
上一篇: 十大創業名人的成功語錄（組圖）
下一篇: laravel | hyperf 數組鍵值駝峰和下劃線轉換

繼續閱讀