哈希表詳解

来源:https://www.cnblogs.com/zhonglongbo/archive/2018/02/28/8485869.html
-Advertisement-
Play Games

哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。 順序搜索以及二叉樹搜索樹中，元素存儲位置和元素各關鍵碼之間沒有對應 ...


哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

順序搜索以及二叉樹搜索樹中，元素存儲位置和元素各關鍵碼之間沒有對應的關係，因此在查找一個元素時，必須要經過關鍵碼的多次比較。搜索的效率取決於搜索過程中元素的比較次數。

理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素。
如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關係，那麼在查找時通過該函數可以很快找到該元素。

當向該結構中：
插入元素時：根據待插入元素的關鍵碼，以此函數計算出該元素的存儲位置並按此位置進行存放
搜索元素時：對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功
該方式即為哈希(散列)方法，哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者
稱散列表)
例如：數據集合{180，750，600，430，541，900，460}
這裡寫圖片描述
用該方法進行搜索不必進行多次關鍵碼的比較，因此搜索的速度比較快
問題：按照上述哈希方式，向集合中插入元素443，會出現什麼問題？
這回就要引出一個概念叫哈希衝突：對於兩個數據元素的關鍵字 和 （i !=j），有 ！= ，但有：HashFun(Ki) == HashFun(Kj)即不同關鍵字通過相同哈希哈數計算出相同的哈希地址，該種現象稱為哈希衝突或哈希碰撞。把具有不同關鍵碼而具有相同哈希地址的數據元素稱為“同義詞”。

解決哈希衝突兩種常見的方法是：閉散列和開散列
閉散列：
閉散列：也叫開放地址法，當發生哈希衝突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那麼可以把key存放到表中“下一個” 空位中去
那如何尋找下一個空餘位置？ 這裡就要用到兩種方法：線性探測和二次探測
線性探測
設關鍵碼集合為{37, 25, 14, 36, 49, 68, 57, 11}，散列表為HT[12]，表的大小m = 12，假設哈希函數為：Hash(x) = x %p（p = 11，是最接近m的質數），就有：
Hash(37) = 4
Hash(25) = 3
Hash(14) = 3
Hash(36) = 3
Hash(49) = 5
Hash(68) = 2
Hash(57) = 2
Hash(11) = 0
其中25，14，36以及68，57發生哈希衝突，一旦衝突必須要找出下一個空餘位置
線性探測找的處理為：從發生衝突的位置開始，依次繼續向後探測，直到找到空位置為止
【插入】
1）. 使用哈希函數找到待插入元素在哈希表中的位置
2）. 如果該位置中沒有元素則直接插入新元素；如果該位置中有元素且和待插入元素相同，則不用插入；如果該位置中有元素但不是待插入元素則發生哈希衝突，使用線性探測找到下一個空位置，插入新元素；
採用線性探測，實現起來非常簡單，缺陷是：
一旦發生哈希衝突，所有的衝突連在一起，容易產生數據“堆積”，即：不同關鍵碼占據了可利用的空位置，使得尋找某關鍵碼的位置需要許多次比較，導致搜索效率降低。 如何緩解呢？ 引入新概念負載因數（負載因數的應用在下一篇博文）和二次探測
負載因數
二次探測
發生哈希衝突時，二次探查法在表中尋找“下一個”空位置的公式為：
Hi= (Ho + i^2) % m,Hi = (Ho -i^2 ) % m, i = 1,2,3…，(m-1)/Ho. 是通過散列函數Hash(x)對元素的關鍵碼 key 進行計算得到的位置，m是表的大小假設數組的關鍵碼為37, 25, 14, 36, 49, 68, 57, 11，取m = 19，這樣可設定為HT[19]，採用散列函數Hash(x) = x % 19，則：
Hash(37)=18
Hash(25)=6
Hash(14)=14
Hash(36)=17
Hash(49)=11
Hash(68)=11
Hash(57)=0
Hash(11)=11
採用二次探測處理哈希衝突：
二次探測
研究表明：當表的長度為質數且表裝載因數a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情況，但在插入時必須確保表的裝載因數a不超過0.5；如果超出必須考慮增容

開散列法又叫鏈地址法(開鏈法)。（將在下一篇博文中寫出）
開散列法：首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼歸於同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈錶鏈接起來，各鏈表的頭結點存儲在哈希表中。

設元素的關鍵碼為37, 25, 14, 36, 49, 68, 57, 11, 散列表為HT[12]，表的大小為12，散列函數為Hash(x) = x % 11
Hash(37)=4
Hash(25)=3
Hash(14)=3
Hash(36)=3
Hash(49)=5
Hash(68)=2
Hash(57)=2
Hash(11)=0
使用哈希函數計算出每個元素所在的桶號，同一個桶的鏈表中存放哈希衝突的元素。
開散列
通常，每個桶對應的鏈表結點都很少，將n個關鍵碼通過某一個散列函數，存放到散列表中的m個桶中，那麼每一個桶中鏈表的平均長度為。以搜索平均長度為的鏈表代替了搜索長度為 n 的順序表，搜索效率快的多。
應用鏈地址法處理溢出，需要增設鏈接指針，似乎增加了存儲開銷。事實上：
由於開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因數a <= 0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節省存儲空間。

引起哈希衝突的一個原因可能是：哈希函數設計不夠合理。
哈希函數設計原則：
.哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間
.哈希函數計算出來的地址能均勻分佈在整個空間中
.哈希函數應該比較簡單
下麵簡單介紹了一些哈希函數：
1.直接定址法
取關鍵字的某個線性函數為散列地址：Hash（Key）= A*Key + B
優點：簡單、均勻
缺點：需要事先知道關鍵字的分佈情況
適合查找比較小且連續的情況
2.除留餘數法
設散列表中允許的地址數為m，取一個不大於m，但最接近或者等於m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m),將關鍵碼轉換成哈希地址3.平方取中法
假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址；
再比如關鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希地址
平方取中法比較適合：不知道關鍵字的分佈，而位數又不是很大的情況
4.摺疊法
摺疊法是將關鍵字從左到右分割成位數相等的幾部分(最後一部分位數可以短些)，然後將這幾部分疊加求和，並按散列表表長，取後幾位作為散列地址摺疊法適合事先不需要知道關鍵字的分佈，適合關鍵字位數比較多的情況
5.隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即H(key) = random(key),其中random為隨機數函數通常應用於關鍵字長度不等時採用此法
6.數學分析法
設有n個d位數，每一位可能有r種不同的符號，這r種不同的符號在各位上出現的頻率不一定相同，可能在某些位上分佈比較均勻，每種符號出現的機會均等，在某些位上分佈不均勻只有某幾種符號經常出現。可根據散列表的大小，選擇其中各種符號分佈均勻的若幹位作為散列地址。
例如：假設要存儲某家公司員工登記表，如果用手機號作為關鍵字，那麼極有可能前7位都是 相同的，那麼我們可以選擇後面的四位作為散列地址，如果這樣的抽取工作還容易出現 衝突，還可以對抽取出來的數字進行反轉(如1234改成4321)、右環位移(如1234改成4123)、左環移位、前兩數與後兩數疊加(如1234改成12+34=46)等方法
說了這麼多概念，來看看代碼。
哈希表的結構定義：

typedef int KeyType;
typedef int ValueType;

typedef enum Status
{
    EMPTY,
    EXIST,
    DELETE,
}Status;

typedef struct HashNode 
{
    KeyType _key;
    ValueType _value;
    Status _status;
}HashNode;

typedef struct HashTable
{
    HashNode *_table;
    size_t _size;
    size_t _N;
}HashTable;

哈希表的初始化：

void HashTableInit(HashTable* ht) //初始化
{
     size_t i = 0;
     assert(ht);
     
     ht->_size = 0;
     ht->_N = HashTablePrime(0);
     ht->_table = (HashNode *)malloc(sizeof(HashNode)*ht->_N);
     assert(ht->_table);

     for (i=0; i<ht->_N; i++)
         ht->_table[i]._status = EMPTY;
}

哈希函數：

KeyType HashFunc(KeyType key,size_t n)
{
    return key%n;
}

看看哈希表的插入：（這裡處理哈希衝突時採用線性探測，二次探測將在下一次博客中寫出）
擴容時要特別註意，不能簡單的用malloc和realloc開出空間後直接付給哈希表，一定記得擴容之後需要重新映射原表的所有值。

int HashTableInsert(HashTable* ht, KeyType key, ValueType value) //插入
{
    KeyType index = key;
    assert(ht);
    **if (ht->_N == ht->_size) //擴容
    {
        KeyType index;
        size_t newN = HashTablePrime(ht->_N);
        HashNode *tmp = (HashNode *)malloc(sizeof(HashNode)*newN);
        size_t i = 0;
        assert(tmp);
        //HashTablePrint(ht); //擴容調試使用
        for (i=0; i<newN; i++)
            tmp[i]._status = EMPTY;
        for (i=0; i<ht->_N; i++)  //擴容之後把以前的表中元素重新映射
        {
            if (ht->_table[i]._status == EXIST) //原表存在時
            {
                index = HashFunc(ht->_table[i]._key,newN);
                if (tmp[index]._status == EXIST) //發生哈希衝突時
                {
                    while (1)
                    {
                        index +=1;
                        if ((size_t)index > newN)
                            index %= newN;
                        if (tmp[index]._status != EXIST)
                            break;
                    }
                }
                
                tmp[index]._key = ht->_table[i]._key;
                tmp[index]._value = ht->_table[i]._value;
                tmp[index]._status = EXIST;
            }
            else
                tmp[i]._status = ht->_table[i]._status;
        }
        ht->_table = tmp;
        ht->_N = newN;
    }**
    
    index = HashFunc(key,ht->_N);
    
    if (ht->_table[index]._status == EXIST) //發生哈希衝突
    {
        size_t i = 0;
        for (i=0; i<ht->_N;i++ )
        {
            if (ht->_table[index]._key == key)
                return -1;
            index +=i;
            if ((size_t)index >ht->_N)
                index %= ht->_N;
            if (ht->_table[index]._status != EXIST)
                break;
        }
    }

    ht->_table[index]._key = key;
    ht->_table[index]._value = value;
    ht->_table[index]._status = EXIST;
    ht->_size++;

    return 0;
}

哈希表的查找：

HashNode* HashTableFind(HashTable* ht, KeyType key) //查找
{
    size_t i = 0;
    KeyType index = key;
    assert(ht);
    index = HashFunc(key,ht->_N);
    if (ht->_table[index]._key == key)
        return &(ht->_table[index]);
    else 
    {
        for (i=0; i<ht->_N; i++)
        {
            index += i;
            if (ht->_table[index]._key == key)
                return &(ht->_table[index]);
            if (ht->_table[index]._status == EMPTY)
                return NULL;
        }
    }
   
   return NULL;
}

哈希表的刪除：

int HashTableRemove(HashTable* ht, KeyType key) //刪除
{
    assert(ht);
    if(HashTableFind(ht,key))
    {
        HashTableFind(ht,key)->_status = DELETE;
        return 0;
    }
    else
        return -1;
    
}

哈希表的銷毀：（使用了malloc開闢空間必須手動銷毀）

void HashTableDestory(HashTable* ht)//銷毀
{
    free(ht->_table);
    ht->_table = NULL;
    ht->_size = 0;
    ht->_N = 0;
}

哈希表的列印：

void HashTablePrint(HashTable *ht) //列印hash表
{
    size_t i = 0;
    assert(ht);
    for (i=0; i<ht->_N; i++)
    {
        if (ht->_table[i]._status == EXIST)
            printf("[%d]%d ",i,ht->_table[i]._key);
        else if (ht->_table[i]._status == EMPTY)
            printf("[%d]E ",i);
        else
            printf("[%d]D ",i);
    }
    printf("\n\n");
}

哈希表整個在插入這塊會比較ran，要仔細理解，特別是擴容那塊。

測試案例：

void TestHashTable()
{
    HashTable ht;
    HashTableInit(&ht);

    HashTableInsert(&ht,53,0);
    HashTableInsert(&ht,54,0);
    HashTableInsert(&ht,55,0);
    HashTableInsert(&ht,106,0);
    HashTableInsert(&ht,1,0);
    HashTableInsert(&ht,15,0);
    HashTableInsert(&ht,10,0);


    HashTablePrint(&ht);
    printf("%d ",HashTableFind(&ht,53)->_key);
    printf("%d ",HashTableFind(&ht,54)->_key);
    printf("%d ",HashTableFind(&ht,10)->_key);
    printf("%d ",HashTableFind(&ht,15)->_key);
    printf("%p ",HashTableFind(&ht,3));
    printf("\n\n");

    HashTableRemove(&ht,53);
    HashTableRemove(&ht,54);
    HashTableRemove(&ht,106);
    HashTableRemove(&ht,10);
    HashTableRemove(&ht,5);
    HashTablePrint(&ht);

    HashTableInsert(&ht,53,0);
    HashTableInsert(&ht,54,0);
    HashTableInsert(&ht,106,0);
    HashTablePrint(&ht);
    
    HashTableDestory(&ht);
    HashTablePrint(&ht);
}

測試結果：
哈希表測試案例

更多內容請關註本文博客：請戳關註鏈接
如需轉載和翻譯請聯繫本人。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 解決Pycharm無法顯示matplotlib繪圖問題
    最近開始接觸matplotlib, 1.首先安裝matplotlib庫和其依賴的一些其他庫,例如:numpy,scipy和pandas等 2.開始進行簡單的編碼工作,併在PyCharm中運行,出現如下錯誤: 解決步驟如下: 前提: 1.導入正確版本的matplotlib庫 2.代碼最後調用matpl ...
  • 解決8080埠占用問題
    因為啟動tomcat有時候操作不當會出現8080被占用的情況 之前一直按百度經驗來,很麻煩 然而2條命令就可以解決 netstat ano|findstr 8080 說明：查看占用8080埠的進程 //pid 是10776 taskkill /pid 10776 /f 說明，運行windows自帶 ...
  • ubuntu16.04編譯安裝mysql-boost-5.7.21並編譯成php擴展測試與使用
    我之前的文章已經改造了自定義MVC框架中的工具類（驗證碼，圖片上傳，圖像處理，分頁）4個類，接下來，就要改造模型類，模型類肯定要連接資料庫，由於我的Ubuntu Linux是裸裝的php(目前只編譯了一個gd擴展），所以需要編譯安裝mysql，並把它編譯成擴展，這裡，我選用5.7版本帶boost的源 ...
  • 02 Java類的載入機制
    1、什麼是類的載入 類的載入指的是將類的.class文件中的二進位數據讀入到記憶體中，將其放在運行時數據區的方法區內，然後在堆區創建一個java.lang.Class對象，用來封裝類在方法區內的數據結構。類的載入的最終產品是位於堆區中的Class對象，Class對象封裝了類在方法區內的數據結構，並向程 ...
  • 【JavaWeb】圖書管理系統【總結】
    感想 該項目是目前為止，我寫過代碼量最多的項目了.....雖然清楚是沒有含金量的【跟著視頻來寫的】，但感覺自己也在進步中...... 寫的過程中，出了不少的問題.....非常多的Servlet，JSP看得眼花..... 現在，想把該項目好好梳理一下要點，於是有了這篇博文.... E R圖 該項目涉及 ...
  • Verilog_Day2
    Verilog_Day1 在CSDN博客上。http://blog.csdn.net/m0_38073085 第三章： 書上基本知識 每個Verilog程式包括4個主要部分：埠定義，I/O說明，內部信號聲明和功能定義。 input/output/inout都預設是wire型而不是reg型變數。 1 ...
  • python 垃圾回收機制的思考
    一、前言 Python 是一門高級語言，使用起來類似於自然語言，開發的時候自然十分方便快捷，原因是Python在背後為我們默默做了很多事情，其中一件就是垃圾回收，來解決記憶體管理，記憶體泄漏的問題。 記憶體泄漏：當程式不停運行，有一部分對象沒有作用，但所占記憶體沒有被釋放，伺服器記憶體隨時間越來越少，最終導致 ...
  • [Lua] 迭代器 閉合函數 與 泛型for
    首先看看一下閉合函數(closure)，見如下代碼： 閉合函數可以用來實現迭代器(iterator)（迭代器用來遍歷集合，每調用一次函數，即返回集合中的下一個元素）。 例如：遍歷一個table的時候，我們經常使用如下方式。 我們可以用while遍歷集合，也可以用for，並且用for會容易很多，下麵看 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類