hash表的實現(xiàn)和hash桶的示例（c實現(xiàn)）

hash是以空間換時間的結(jié)構(gòu)围橡，現(xiàn)在空間越來越大暖混，而且對性能要求越來越高的年代，這絕對是值得的翁授。

hash含義就是散列拣播，就是把我們本來想?查找的一大群結(jié)構(gòu)體數(shù)據(jù)分散開，更容易查找收擦。一個好的hash函數(shù)應(yīng)該做到對所有元素平均分散排列贮配，盡量避免或者降低他們之間的沖突（Collision）。hash函數(shù)的選擇必須慎重塞赂，如果不幸所有的元素之間都產(chǎn)生了沖突泪勒，那么hash表將退化為鏈表，其性能會大打折扣宴猾，時間復(fù)雜度迅速降為O(n)圆存，絕對不要存在任何僥幸心理，因為那是相當(dāng)危險的仇哆。歷史上就出現(xiàn)過利用Linux內(nèi)核hash函數(shù)的漏洞沦辙，成功構(gòu)造出大量使hash表發(fā)生碰撞的元素，導(dǎo)致系統(tǒng)被DoS讹剔，所以目前內(nèi)核的大部分hash函數(shù)都有一個隨機(jī)數(shù)作為參數(shù)進(jìn)行摻雜油讯，以使其最后的值不能或者是不易被預(yù)測。這又對 hash函數(shù)提出了第二點安全方面的要求：hash函數(shù)最好是單向的辟拷，并且要用隨機(jī)數(shù)進(jìn)行摻雜撞羽。提到單向，你也許會想到單向散列函數(shù)md4和md5衫冻，很不幸地告訴你诀紊，他們是不適合的，因為hash函數(shù)需要有相當(dāng)好的性能隅俘。

散列函數(shù): 將字符串等傳入我們的散列函數(shù)邻奠，而散列函數(shù)的職責(zé)就是給我們返回一個value值笤喳，我們通過這個值引做hash表下標(biāo)去訪問我們想要查找的數(shù)據(jù)；例如這樣的函數(shù)：

int Hash(char *key, int TableSize)
{
     unsigned int HashVal = 0;
     while(*key != '\0')
             HashVal += *key++;
     return HashVal % TableSize;
}

這就是一個簡單的hash函數(shù)碌宴，就是把我們傳入過來的key（由我們的數(shù)據(jù)中一個或者多個結(jié)構(gòu)體成員的成員來作為key）來得到一個返回值杀狡，這個返回值就是我們的value值。

一個好的hash?函數(shù)就是把我們的說有數(shù)據(jù)盡可能均勻的分散在我們預(yù)設(shè)的TableSize大小的hash表中贰镣。哈希表的幾種方法：

1呜象、直接定址法：取關(guān)鍵字key的某個線性函數(shù)為散列地址，如Hash(key) = key 或 Hash(key) = A*key+B碑隆；A,B為常數(shù)

2恭陡、除留取余法：關(guān)鍵值除以比散列表長度小的素數(shù)所得的余數(shù)作為散列地址。Hash(key) = key % p;

3上煤、平均取中法：先計算構(gòu)成關(guān)鍵碼的標(biāo)識符的內(nèi)碼的平方休玩，然后按照散列表的大小取中間的若干位作為散列地址。

4劫狠、折疊法：把關(guān)鍵碼自左到右分為位數(shù)相等的幾部分拴疤，每一部分的位數(shù)應(yīng)與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些独泞。把這些部分的數(shù)據(jù)疊加起來呐矾，就可以得到具有關(guān)鍵碼的記錄的散列地址。分為移位法和分界法阐肤。

5凫佛、隨機(jī)數(shù)法：選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)作為它的哈希地址孕惜。

6愧薛、數(shù)學(xué)分析法：設(shè)有N個d位數(shù)，每一位可能有r種不同的符號衫画。這r種不同的符號在各位上出現(xiàn)的頻率不一定相同毫炉，可能在某些位上分布均勻些，每種符號出現(xiàn)的機(jī)會均等削罩；在某些位上分布不均勻瞄勾，只有某幾種符號經(jīng)常出現(xiàn)∶旨ぃ可根據(jù)散列表的大小进陡，選取其中各種符號分布均勻的若干位作為散列地址。

但是無論我們怎么樣去選擇這個函數(shù)微服，都不可能完全避免不同key值的hash[value]?指向會映射到同一散列地址上禀横。這樣就會造成哈希沖突/哈希碰撞纵顾。所以我們需要找到處理這種沖突的方法竟痰，大概分為這兩種：分離鏈接法和開放定址法滥玷。

分離鏈接法:其實就是我們說的hash桶的含義了妇蛀。哈希桶就是盛放不同key鏈表的容器（即是哈希表），在這里我們可以把每個key的位置看作是一個桶，桶里放了一個鏈表

image.png

相信大家可以看出來，使用一個數(shù)組來存放記錄方法的哈希沖突太多魄缚，基于載荷因子的束縛，空間利用率不高焚廊，在需要節(jié)省空間的情況下冶匹，我們可以用哈希桶來處理哈希沖突。

哈希桶是使用一個順序表來存放具有相同哈希值的key的鏈表的頭節(jié)點咆瘟，利用這個頭節(jié)點可以找到其它的key徙硅。

下面把完整的一套函數(shù)分開講：

1、首先是創(chuàng)建我們需要的結(jié)構(gòu)體：

數(shù)據(jù)的結(jié)構(gòu)體(也就是我們表中需要存放的數(shù)據(jù)):

 typedef struct node_s
{
        int key;    //這個值是我們得到我們的value值的依據(jù)搞疗，當(dāng)然也可以能使字符串等，看你的數(shù)據(jù)類型了须肆；

       struct node *next;

}NODE;

hash表的節(jié)點：?

typedef struct hash_s
{
        NODE **list;   //這個就是我們所有的hash桶的首個節(jié)點了匿乃，我們用它來查找到我們的桶的位置，為什么是**類型呢 豌汇，因為這是地址的地址幢炸，例如某個桶 i 的位置*list[i]；這樣就找到我們的桶了拒贱；然后再在桶下面看看有沒有我們要查找的NODE節(jié)點了

}HASH;

2宛徊、初始化hash表：

HashTable InitializeTable(int TableSize)
{
        Hash H;
        int i = 0;
        H = calloc(1, sizeof(HASH));
        if (H ==  NULL)
                return -1;

        H->TableSize = NextPrime();   //就是和TableSize最近的下一個素數(shù)；
        H->hlist = calloc(1, sizeof(&NODE) * H->TableSize);
        if (H->hlist == NULL)
                return -1;

        for (i = 0; i < H->TableSize; i ++)     
        {
                *(H->hlist[i)] = calloc(1, sizeof(NODE));
                if (*hlist[i] == NULL)
                        return -1;
                else
                        *(H->hlist[i])->next = NULL;
        }
}

3逻澳、查找NODE：

NODE *Find(int key, HASH H)
{
        NODE *p;
        NODE *list;

        list = H->hlist[Hash(key, H->TableSize)];
        p = list->next;
        while(p != NULL && p->key != key)
                p = p->next;
        return p;

}    //先找到這個桶的頭結(jié)點list,然后再往后面遍歷查找闸天，這時候基本是鏈表查找操作了；

4斜做、插入NODE：

void Insert(int key, HASH H)
{
        NODE *p;
        NODE *list;
        NODE *tmp;

        if (Find(key, H) == NULL)
        {
                tmp = calloc(1, sizeof(NODE));
                if (tmp == NULL)
                        return -1;

                list = H->hlist[Hash(key, H->TableSize)];
                tmp->key = key;
                tmp->next = list->next;//這里是直接把我們的節(jié)點插入到桶的首節(jié)點苞氮；
                list->next = tmp;
        }
        return;
}

以上基本完成以hash桶?為處理沖突的hash表的實現(xiàn)