優缺點
哈希表是種數據結構，它可以提供快速的插入操作和查找操作。第一次接觸哈希表時，它的優點多得讓人難以置信。不論哈希表中有多少數據，插入和刪除（有時包括側除）只需要接近常量的時間即0(1）的時間級。實際上，這只需要幾條機器指令。
對哈希表的使用者——人來說，這是一瞬間的事。哈希表運算得非常快，在電腦程式中，如果需要在一秒種內查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時間級。哈希表不僅速度快，編程實現也相對容易。
哈希表也有一些缺點它是基於數組的，數組創建後難於擴展某些哈希表被基本填滿時，性能下降得非常嚴重，所以程式雖必須要清楚表中將要存儲多少數據（或者準備好定期地把數據轉移到更大的哈希表中，這是個費時的過程）。
而且，也沒有一種簡便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數據項。如果需要這種能力，就只能選擇其他數據結構。
然而如果不需要有序遍歷數據，並且可以提前預測數據量的大小。那么哈希表在速度和易用性方面是無與倫比的。
概念及作用
一般的線性表，樹中，記錄在結構中的相對位置是隨機的，即和記錄的關鍵字之間不存在確定的關係，因此，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較“的基礎上，查找的效率依賴於查找過程中所進行的比較次數。
理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係f，使每個關鍵字和結構中一個唯一的存儲位置相對應。
哈希表最常見的例子是以學生學號為關鍵字的成績表，1號學生的記錄位置在第一條，10號學生的記錄位置在第10條...
如果我們以學生姓名為關鍵字，如何建立查找表，使得根據姓名可以直接找到相應記錄呢？
用上述得到的數值作為對應記錄在表中的位置，得到下表：
上面這張表即哈希表。
如果將來要查李秋梅的成績，可以用上述方法求出該記錄所在位置：
李秋梅:lqm 12+17+13=42 取表中第42條記錄即可。
問題：如果兩個同學分別叫 劉麗 劉蘭 該如何處理這兩條記錄？
這個問題是哈希表不可避免的，即衝突現象：對不同的關鍵字可能得到同一哈希地址。
構造方法
1、直接定址法
例如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函式取關鍵字自身。
但這種方法效率不高,時間複雜度是O(1),空間複雜度是O(n),n是關鍵字的個數
2、數字分析法
有學生的生日數據如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
經分析,第一位，第二位，第三位重複的可能性大，取這三位造成衝突的機會增加，所以儘量不取前三位，取後三位比較好。
3、平方取中法
取關鍵字平方後的中間幾位為哈希地址。
4、摺疊法
將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址，這方法稱為摺疊法。
例如：每一種西文圖書都有一個國際標準圖書編號，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10,000時，可採用此法構造一個四位數的哈希函式。如果一本書的編號為0-442-20586-4,則：
5、除留餘數法
取關鍵字被某個不大於哈希表表長m的數p除後所得餘數為哈希地址。
H(key)=key MOD p (p
處理衝突方法
如果兩個同學分別叫 劉麗 劉蘭，當加入劉蘭時，地址24發生了衝突，我們可以以某種規律使用其它的存儲位置，如果選擇的一個其它位置仍有衝突，則再選下一個，直到找到沒有衝突的位置。選擇其它位置的方法有：
1、開放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k
查找C代碼
//開放定址哈希表的存儲結構
int hashsize[]=
{
997,...
}
;
typedef struct
{
elemtype*elem ;
int count ;
int sizeindex ;
}
HashTable ;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE-1
Status SearchHash(HashTable H,KeyTypeK,int&p,int&c)
{
p=Hash(K);
while(H.elem
.key!=NULLKEY&&!EQ(K,H.elem
.key))
collision(p,++c);
if(EQ(K,H.elem
.key)
return SUCCESS ;
else return UNSUCCESS ;
}
Status InsertHash(HashTable&H,EleType e)
{
c=0 ;
if(SearchHash(H,e.key,p,c))
return DUPLICATE ;
else if(c
{
H.elem
=e ;
++H.count ;
return OK ;
}
else RecreateHashTable(H);
}
經典計算機算法介紹
| 算法是計算機科學中一門古老而常新的學科，就像一個人的思維能力一樣，其重要性對於計算機性能的分析、套用與改進有著至不言而喻的地位。而隨著計算機科學技術的發展，新的算法也隨著新的套用漸漸出現，但總有一些算法由於其本身具有的特點以及對計算機科學發展做出的卓越貢獻而成為經典，本任務就是要介紹這些經典算法。 |
