IT培训机构|91免费精品视频|专注编程培训|91免费精品|软件开发培训_91免费国产视频_华清远见教育

數(shù)據(jù)結(jié)構(gòu)一直都是軟件工程師必備技能之一，也是難點(diǎn)之一。數(shù)據(jù)結(jié)構(gòu)其實(shí)是數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，它采用不同的存儲(chǔ)方式和邏輯思路，實(shí)現(xiàn)各種數(shù)據(jù)和數(shù)據(jù)之間的關(guān)聯(lián)，并且加上對(duì)應(yīng)的算法，來解決問題。哈希表(散列表)是數(shù)據(jù)結(jié)構(gòu)中一種散列存儲(chǔ)方式，優(yōu)點(diǎn)在于關(guān)鍵值key可以通過指定的算法直接得到數(shù)據(jù)的存儲(chǔ)位置hash(key)，這樣一來不需要輪詢，時(shí)間復(fù)雜度大大的降低。從而，哈希表滿足了對(duì)數(shù)據(jù)操作高效率的要求。但是，哈希表也不是全能的，它的使用有一定的局限性。下面我們來介紹一下哈希表的設(shè)計(jì)和實(shí)現(xiàn)。

哈希表的設(shè)計(jì)

哈希表主要是確認(rèn)關(guān)鍵值key和關(guān)鍵值存儲(chǔ)位置hash(key)之間的具體關(guān)聯(lián)算法。并且保證少的哈希沖突(多個(gè)不同數(shù)據(jù)通過算法得到存儲(chǔ)位置相同，這時(shí)就是哈希沖突)產(chǎn)生。常見的哈希表的設(shè)置方法如下：

（1）直接定址法：直接的構(gòu)造哈希表的方法，存儲(chǔ)位置是通過線性函數(shù)得到的：

hash(key) = a * key + b {a、b為常數(shù)}

特點(diǎn)：這樣得到的 hash(key) 和 key之間一一對(duì)應(yīng)，一般不會(huì)產(chǎn)生沖突;

空間：這的哈希表要求地址空間大小與key集合大小相同;

應(yīng)用：一般用于有序的key集合，例如各種編號(hào)。

（2）數(shù)字分析法： 分析已有數(shù)據(jù)的特點(diǎn)，選擇盡量沖突少的數(shù)字來構(gòu)造哈希表。

特點(diǎn)：數(shù)據(jù)是多位組成，數(shù)據(jù)和數(shù)據(jù)之間有相同的也有不同的，根據(jù)數(shù)據(jù)中每位的分布特點(diǎn)，選取若干位作為哈希表地址。

空間：根據(jù)選擇的位的個(gè)數(shù)而定;

應(yīng)用：數(shù)據(jù)位數(shù)多，且都相似， 例如生日，日期等等。

（3）除留余數(shù)法：n個(gè)數(shù)據(jù),選取一個(gè)接近于n的質(zhì)數(shù)p，這時(shí)哈希地址公式：

hash(key) = key % p 除法后得到的余數(shù)就是數(shù)據(jù)存儲(chǔ)位置

特點(diǎn)：余數(shù)的取值范圍 0 到 p-1 內(nèi)，這樣存儲(chǔ)數(shù)據(jù)空間大小是固定的 p 個(gè);

空間：p個(gè)存儲(chǔ)空間;

應(yīng)用： 數(shù)據(jù)值較大，數(shù)據(jù)個(gè)數(shù)較少。

(4)乘余取整法：先讓關(guān)鍵值key乘上一個(gè)常數(shù)A(0 <1),提取乘積的小數(shù)部分。然后再用整數(shù)n乘以這個(gè)值，對(duì)結(jié)果向下取整，這個(gè)結(jié)果就是存儲(chǔ)位置。<>

公式：hash(key) = (int)((((float)key*A) - (int)(key*A))*n)

應(yīng)用：數(shù)據(jù)是小數(shù)，并且相差很少。

(5)平方取中法：一般哈希地址位置數(shù)據(jù)2的某次冪，例如：哈希地址總數(shù)為 m = 2^r。哈希地址hash(key) = 2^key 值中間的r位。

(6)折疊法：數(shù)據(jù)信息很長(zhǎng)，可以將數(shù)據(jù)從左到有分成幾個(gè)部分，每部分位數(shù)應(yīng)與hash(key)存儲(chǔ)位置的位數(shù)相同，將每部分都疊加求和，這個(gè)和就是hash(key)存儲(chǔ)位置。

應(yīng)用：例如：圖書館中圖書的標(biāo)準(zhǔn)編號(hào)。

(7)隨機(jī)數(shù)法：獲取一個(gè)隨機(jī)數(shù)，作為存儲(chǔ)位置，公式：hash(key) = random(key);

應(yīng)用：key關(guān)鍵字長(zhǎng)度不等時(shí)使用。

哈希表的實(shí)現(xiàn)

這里我們以第三種方式除留余數(shù)法舉例。

例子：已知存在以下數(shù)據(jù) ： 23 , 26 ， 29 ，30，34 ，40

利用哈希表存儲(chǔ)上面數(shù)據(jù)，并寫出查找方法。

第一步：確認(rèn)hash(key)和key之間的關(guān)聯(lián)公式

數(shù)據(jù)有6個(gè)，先選取一個(gè)質(zhì)數(shù)p = 7 或 11或 13

為盡量減少哈希沖突，當(dāng)選擇p=7時(shí)：余數(shù)2 5 1 2 6 5有沖突

當(dāng)選擇p=11時(shí)：余數(shù)1 4 7 8 1 6有沖突

當(dāng)選擇p=13時(shí)：余數(shù)10 0 3 4 8 1無沖突

所以公式：hash(key) = key % 13;

實(shí)現(xiàn)代碼：
#include<stdio.h>
typedef int data_t;
#define M 13
int emptyHash(data_t *p)  // 判斷哈希地址中是否空閑
{
         return *p == 0 ? 1:0;
}
int setHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(emptyHash(&hp[i]))      // 判讀指定位置是否空閑
                   hp[i] = key;                  // 存儲(chǔ)到哈希表中
         else 
return 0;       // 失敗
         return 1;           // 成功
}
int getHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(hp[i] != key)    
         {
                   printf("數(shù)據(jù)沒有存儲(chǔ)到哈希表中\(zhòng)n");
                   return 0;
         }
         else
                   printf("數(shù)據(jù)在哈希表中,位置%d --> %d\n",i, hp[i]);
         return 1;
}
int main()
{
         data_t hash[13] = {0};          // 定義一個(gè)哈希表（數(shù)組）存儲(chǔ)數(shù)據(jù)空間
         setHash(hash,23);
         setHash(hash,26);
         setHash(hash,29);           // 哈希表中存入數(shù)據(jù)
         setHash(hash,30);
         setHash(hash,34);
         setHash(hash,40);
         getHash(hash,34);           // 查找哈希表
         getHash(hash,32);                    
         return 0;
}