亚洲精品一二区_国产黄色片网站_99久久久成人国产精品_蜜臀网_国产精品一区二区三区免费_成人av中文字幕_91精品国产欧美一区二区成人

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

哈希表的設計

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

（1）直接定址法：直接的構造哈希表的方法，存儲位置是通過線性函數得到的：

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

特點：這樣得到的 hash(key) 和 key之間一一對應，一般不會產生沖突;

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

應用：一般用于有序的key集合，例如各種編號。

（2）數字分析法： 分析已有數據的特點，選擇盡量沖突少的數字來構造哈希表。

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

空間：根據選擇的位的個數而定;

應用：數據位數多，且都相似， 例如生日，日期等等。

（3）除留余數法：n個數據,選取一個接近于n的質數p，這時哈希地址公式：

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

特點：余數的取值范圍 0 到 p-1 內，這樣存儲數據空間大小是固定的 p 個;

空間：p個存儲空間;

應用： 數據值較大，數據個數較少。

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

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

應用：數據是小數，并且相差很少。

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

(6)折疊法：數據信息很長，可以將數據從左到有分成幾個部分，每部分位數應與hash(key)存儲位置的位數相同，將每部分都疊加求和，這個和就是hash(key)存儲位置。

應用：例如：圖書館中圖書的標準編號。

(7)隨機數法：獲取一個隨機數，作為存儲位置，公式：hash(key) = random(key);

應用：key關鍵字長度不等時使用。

哈希表的實現

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

例子：已知存在以下數據 ： 23 , 26 ， 29 ，30，34 ，40

利用哈希表存儲上面數據，并寫出查找方法。

第一步：確認hash(key)和key之間的關聯公式

數據有6個，先選取一個質數p = 7 或 11或 13

為盡量減少哈希沖突，當選擇p=7時：余數2 5 1 2 6 5有沖突

當選擇p=11時：余數1 4 7 8 1 6有沖突

當選擇p=13時：余數10 0 3 4 8 1無沖突

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

實現代碼：
#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;                  // 存儲到哈希表中
         else 
return 0;       // 失敗
         return 1;           // 成功
}
int getHash(data_t *hp,data_t key)
{
         int i = key % M;
         if(hp[i] != key)    
         {
                   printf("數據沒有存儲到哈希表中\n");
                   return 0;
         }
         else
                   printf("數據在哈希表中,位置%d --> %d\n",i, hp[i]);
         return 1;
}
int main()
{
         data_t hash[13] = {0};          // 定義一個哈希表（數組）存儲數據空間
         setHash(hash,23);
         setHash(hash,26);
         setHash(hash,29);           // 哈希表中存入數據
         setHash(hash,30);
         setHash(hash,34);
         setHash(hash,40);
         getHash(hash,34);           // 查找哈希表
         getHash(hash,32);                    
         return 0;
}