大家好，這里是物聯(lián)網(wǎng)心球。

談到Linux高性能編程，我們繞不開(kāi)高效數(shù)據(jù)結(jié)構(gòu)，今天我們來(lái)講解哈希表，哈希表是使用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，很多開(kāi)源項(xiàng)目都會(huì)用到哈希表，Linux內(nèi)核也大量使用了哈希表。

1.什么是哈希表？

  在介紹哈希表之前，我們先來(lái)思考一個(gè)問(wèn)題：我們?nèi)绾瓮ㄟ^(guò)學(xué)生名從學(xué)生信息表中快速查找出學(xué)生信息？

圖片

為了從學(xué)生信息表中快速查找學(xué)生信息，我們需要借助一種高效數(shù)據(jù)結(jié)構(gòu)哈希表來(lái)完成。

 哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵字（Key）直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。它通過(guò)把關(guān)鍵字映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做哈希函數(shù)（也叫散列函數(shù)），存放記錄的數(shù)組叫做哈希表。

圖片

    哈希表最大的特點(diǎn)就是可以快速實(shí)現(xiàn)查找、插入和刪除操作，由于哈希表直接通過(guò)關(guān)鍵字映射查找，時(shí)間復(fù)雜度接近于O(1)。

    哈希表廣泛應(yīng)用于數(shù)據(jù)庫(kù)索引、緩存系統(tǒng)、字典實(shí)現(xiàn)、計(jì)數(shù)器等多種場(chǎng)景。

2.哈希表重要概念

學(xué)習(xí)哈希表我們需要掌握幾個(gè)重要概念：哈希函數(shù)，哈希沖突，哈希擴(kuò)容。

2.1 哈希函數(shù)

哈希函數(shù)是將任意長(zhǎng)度的輸入消息映射為固定長(zhǎng)度輸出的函數(shù)，哈希函數(shù)有很多種構(gòu)造方法：

• 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址，形式為H(key)=key或H(key)=a*key+b（a、b為常數(shù)）。
• 數(shù)字分析法：適用于關(guān)鍵字位數(shù)多且某些位分布不均的情況，通過(guò)抽取關(guān)鍵字中分布均勻的若干位作為哈希地址。
• 平方取中法：當(dāng)關(guān)鍵字中各位分布不均時(shí)，可求其平方值并取中間的幾位作為哈希地址。
• 除留余數(shù)法：最常用的方法，形式為H(key)=key mod p（p<m，m為哈希表長(zhǎng)）。
• 折疊法：適用于關(guān)鍵字位數(shù)多且分布均勻的情況，將關(guān)鍵字分割后疊加求和作為哈希地址。
• 隨機(jī)數(shù)法：取關(guān)鍵字的隨機(jī)函數(shù)值作為哈希地址，適用于關(guān)鍵字長(zhǎng)度不等的情況。

2.2 哈希沖突

哈希沖突是指不同輸入經(jīng)哈希函數(shù)得到相同輸出。

具體來(lái)說(shuō)，在使用哈希函數(shù)時(shí)，可能會(huì)出現(xiàn)兩個(gè)或更多的輸入值被映射到同一哈希值的情況，這就是哈希沖突。在哈希表中，這種現(xiàn)象會(huì)導(dǎo)致不同的鍵被映射到同一個(gè)位置，從而可能引發(fā)數(shù)據(jù)丟失或檢索效率下降的問(wèn)題，因?yàn)樾枰~外的操作來(lái)處理這種沖突。

圖片

 哈希沖突的發(fā)生是由于哈希函數(shù)將任意長(zhǎng)度的輸入轉(zhuǎn)換為固定長(zhǎng)度的輸出，而輸出空間通常遠(yuǎn)小于輸入空間，因此不同的輸入可能會(huì)映射到相同的輸出地址上。

解決哈希沖突的方法包括開(kāi)放尋址法、鏈表法等。

1）開(kāi)放尋址法

    當(dāng)哈希表中的一個(gè)位置被占用時(shí)，此方法會(huì)尋找下一個(gè)可用的位置來(lái)存放數(shù)據(jù)。此方法避免了使用額外的數(shù)據(jù)結(jié)構(gòu)，如鏈表，來(lái)存儲(chǔ)具有相同哈希值的鍵值對(duì)。

圖片

2）鏈表法

    鏈表法通過(guò)維護(hù)一個(gè)鏈表數(shù)組來(lái)解決哈希沖突。

    每個(gè)鏈表頭指針存儲(chǔ)在數(shù)組的一個(gè)槽位中，具有相同哈希值的所有元素都將存儲(chǔ)在同一個(gè)鏈表中。

    這種方法允許哈希表有更高的裝載因子，因?yàn)樗皇芫奂瘑?wèn)題的影響。

圖片

2.3 哈希擴(kuò)容

哈希擴(kuò)容是哈希表在數(shù)據(jù)量達(dá)到一定閾值時(shí)增加其容量的過(guò)程。

這里需要引入一個(gè)概念裝載因子。

哈希表裝載因子 = 插入表中的元素個(gè)數(shù) / 哈希表長(zhǎng)度

當(dāng)哈希表中的元素?cái)?shù)量超過(guò)設(shè)定的裝載因子與表長(zhǎng)度的乘積時(shí)，會(huì)觸發(fā)擴(kuò)容操作。哈希擴(kuò)容的目的是減少哈希沖突，提高查詢(xún)和插入效率。

圖片

3.哈希表編程

Linux內(nèi)核很多模塊使用了哈希表，我們參考Linux內(nèi)核哈希表（hlist）來(lái)設(shè)計(jì)我們自己的哈希表。

 哈希表重要數(shù)據(jù)結(jié)構(gòu)如下：

struct hlist_node {            //哈希節(jié)點(diǎn)
    struct hlist_node *next, **pprev; //后驅(qū)指針，前驅(qū)指針
};

struct hlist_head {         //哈希鏈表頭
    struct hlist_node *first;  //first指針
};

typedef struct pack {
    struct hlist_node node; //哈希節(jié)點(diǎn)
    int seq;            //關(guān)鍵字
} pack_t;

typedef struct hash_table {
    char name[24];     //哈希表名稱(chēng)
    int num;         //哈希表元素?cái)?shù)量
    int size;        //哈希表大小
    struct hlist_head htable[0]; //哈希表
}hash_table_t;

1） 創(chuàng)建哈希表

hash_table_t *hash_table_create(int size) {
    hash_table_t *t = (hash_table_t *)malloc(sizeof(hash_table_t) + size * sizeof(struct hlist_head));
    if (!t) return NULL;

    t->num = 0;
    t->size = size;
    sprintf(t->name, "%d hash table", size);
    for (int i = 0; i < size; i++) {
        hlist_head_init(&t->htable[i]);
    }

    return t;
}

哈希表采用柔性數(shù)組htable[0]表示，malloc申請(qǐng)內(nèi)存時(shí)，除了申請(qǐng)hash_table_t結(jié)構(gòu)大小內(nèi)存外，還要申請(qǐng)哈希表數(shù)組大小內(nèi)存。

圖片

    申請(qǐng)完哈希表數(shù)組后，需通過(guò)hlist_head_init函數(shù)對(duì)哈希表數(shù)組每個(gè)鏈表進(jìn)行初始化。

2）插入節(jié)點(diǎn)

void hash_table_insert(struct hlist_node *node, int key, hash_table_t *t) {
    int index = key & (t->size - 1); //哈希函數(shù)，計(jì)算索引值
    hlist_add_head(node, &t->htable[index]); //插入節(jié)點(diǎn)
    t->num++; //鍵值對(duì)加1
    printf("%s num/size:%d/%d insert key:%d\n", t->name, t->num, t->size, key);
}

pack_t *pkt = malloc(sizeof(pack_t)); //創(chuàng)建數(shù)據(jù)包節(jié)點(diǎn)
hlist_node_init(&pkt->node); //初始化節(jié)點(diǎn)
pkt->seq = seq; //設(shè)置關(guān)鍵字
hash_table_insert(&pkt->node, pkt->seq, t); //插入哈希表

    哈希表插入節(jié)點(diǎn)步驟：

• 通過(guò)關(guān)鍵字計(jì)算出哈希表數(shù)組索引值，通過(guò)索引值找到鏈表頭。
• 將節(jié)點(diǎn)插入鏈表頭。

圖片

    為了保證哈希表通用性，Linux內(nèi)核通常會(huì)把節(jié)點(diǎn)域和數(shù)據(jù)域進(jìn)行解耦，節(jié)點(diǎn)域只負(fù)責(zé)完成節(jié)點(diǎn)的插入，查找，刪除，數(shù)據(jù)域可以根據(jù)業(yè)務(wù)需求自行定義。

    測(cè)試程序中的struct pack結(jié)構(gòu)的node成員為節(jié)點(diǎn)域，seq為數(shù)據(jù)域。

3） 查詢(xún)節(jié)點(diǎn)

#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
         pos = n)

hlist_for_each_safe(pos, n, &t->htable[index]) {
        if (pos) {
    //查詢(xún)成功
        }
}

    哈希表查詢(xún)節(jié)點(diǎn)步驟：

• 通過(guò)關(guān)鍵字計(jì)算出哈希表數(shù)組索引值，通過(guò)索引值找到鏈表頭。
• 通過(guò)for循環(huán)輪詢(xún)鏈表，直到找到關(guān)鍵字匹配成功的節(jié)點(diǎn)。

4） 刪除節(jié)點(diǎn)

void hlist_del_node(struct hlist_node *node) {
    struct hlist_node *next = node->next;
    struct hlist_node **pprev = node->pprev;
    WRITE_ONCE(*pprev, next);
    if (next) 
          WRITE_ONCE(next->pprev, pprev);
}

void hash_table_del(int key, hash_table_t *t, do_del del) {
    int index = key & (t->size - 1);
    struct hlist_node *pos, *n;
    //查詢(xún)鏈表
    hlist_for_each_safe(pos, n, &t->htable[index]) {
        if (pos) {
            hlist_del_node(pos); //從鏈表刪除節(jié)點(diǎn)
            del(pos); //釋放節(jié)點(diǎn)內(nèi)存
            t->num--;
            printf("%s num/size:%d/%d del key:%d\n", t->name, t->num, t->size, key);
        }
    }
}

    哈希表刪除節(jié)點(diǎn)步驟：

• 通過(guò)關(guān)鍵字計(jì)算出哈希表數(shù)組索引值，通過(guò)索引值找到鏈表頭。
• 通過(guò)for循環(huán)輪詢(xún)鏈表，通過(guò)關(guān)鍵字找到匹配的節(jié)點(diǎn)并刪除節(jié)點(diǎn)。

    刪除節(jié)點(diǎn)的步驟和插入節(jié)點(diǎn)的步驟相反。

圖片

5）哈希擴(kuò)容

void hash_table_resize(hash_table_t *t1, hash_table_t *t2, do_move move) {
    printf("%s num/size:%d/%d move to %s num/size:%d/%d\n",
            t1->name, t1->num, t1->size,
            t2->name, t2->num, t2->size);
    struct hlist_node *pos, *n;
    for (int i = 0; i < t1->size; i++) { //輪詢(xún)舊哈希表每個(gè)鏈表
        hlist_for_each_safe(pos, n, &t1->htable[i]) {
            if (pos) { //查找到生效節(jié)點(diǎn)
                hlist_del_node(pos); //刪除節(jié)點(diǎn)
                move(pos, t2); //將節(jié)點(diǎn)移至新哈希表
                t2->num++;
            }
        }
    }
}

if (t->num > t->size) { //判斷負(fù)載因子，觸發(fā)哈希擴(kuò)容
    t2 = hash_table_create(t->size << 1); //新哈希表擴(kuò)容至2倍
    if (!t2) {
       printf("hash table create error\n");
       return -1;
    }
    hash_table_resize(t, t2, pack_move); //開(kāi)始擴(kuò)容
    hash_table_destroy(t, pack_del); //釋放就哈希表
    t = t2;
}

    當(dāng)哈希表元素越來(lái)越多時(shí)，此時(shí)整個(gè)哈希表的插入，查詢(xún)，刪除效率會(huì)越來(lái)越低，通過(guò)裝載因子判斷是否需要進(jìn)行哈希擴(kuò)容。

    哈希擴(kuò)容步驟：

• 創(chuàng)建新哈希表，新哈希表的大小為舊哈希表的2倍。
• 將舊哈希表的所有節(jié)點(diǎn)通過(guò)新哈希函數(shù)移至新哈希表。
• 刪除舊哈希表。

6） 釋放哈希表

void hash_table_destroy(hash_table_t *t, do_del del) {
    struct hlist_node *pos, *n;
    for (int i = 0; i < t->size; i++) { //刪除哈希表生效節(jié)點(diǎn)
        hash_table_del(i, t, del);
    }
    free(t); //釋放哈希表內(nèi)存
}

    釋放哈希表需要清空哈希表數(shù)組每個(gè)鏈表中的節(jié)點(diǎn)，防止內(nèi)存泄露，最后釋放哈希表。