一、定義
散列技術(shù)是記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f抄沮，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)范舀。查找時(shí)，根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定值key的映射f(key)聪全。若查找集合中存在這個(gè)記錄辅辩，則必定在f(key)的位置上娃圆。
存儲(chǔ)位置 = f (關(guān)鍵字)
我們把這種對(duì)應(yīng)關(guān)系f稱為散列函數(shù)讼呢，又稱為哈希（Hash）函數(shù)谦炬。
采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中键思，這塊連續(xù)的存儲(chǔ)空間稱為散列表或者哈希表。
關(guān)鍵字對(duì)應(yīng)的記錄存儲(chǔ)位置我們稱為散列地址看蚜。
二赔桌、散列查找步驟
- 在存儲(chǔ)時(shí)，通過散列函數(shù)計(jì)算記錄的散列地址音诫，并按此散列地址存儲(chǔ)該記錄仿贬。
- 當(dāng)查找記錄時(shí)纽竣，我們通過同樣的散列函數(shù)計(jì)算記錄的散列地址墓贿，按此散列地址訪問該記錄茧泪。
散列技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法聋袋。
與線性表队伟、樹、圖等結(jié)構(gòu)不同的是幽勒，線性表嗜侮、樹、圖數(shù)據(jù)元素之間存在某種邏輯關(guān)系，可以用連線圖表示出來，而散列技術(shù)記錄的數(shù)據(jù)元素之間不存在什么邏輯關(guān)系颓遏，它只與關(guān)鍵字有關(guān)聯(lián)。
我們時(shí)常會(huì)碰到兩個(gè)關(guān)鍵字key1不等于key2凹蜂，但是卻有f(key1)=f(key2)，這種現(xiàn)象我們稱為沖突，并把key1和key2稱為這個(gè)散列函數(shù)的同義詞覆醇。
三朵纷、散列函數(shù)的構(gòu)造方法
1. 直接定址法
我們可以取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址：
f(key) = a*key+b（a、b為常數(shù)）
優(yōu)點(diǎn)：簡(jiǎn)單永脓、均勻袍辞、也不會(huì)產(chǎn)生沖突。
缺點(diǎn)：需要事先知道關(guān)鍵字的分布情況常摧。
適用范圍：查找表較小且連續(xù)的情況搅吁。
2. 數(shù)字分析法
使用關(guān)鍵字的一部分來計(jì)算散列存儲(chǔ)位置的方法，如電話號(hào)碼存儲(chǔ)落午，可抽取電話號(hào)碼的中間幾位進(jìn)行反轉(zhuǎn)/右移/左移等操作似芝，然后將關(guān)鍵字分配到散列表的各位置。
適用范圍：通常用于處理關(guān)鍵字位數(shù)比較大的情況板甘。
3. 平方取中法
這個(gè)方法計(jì)算比較簡(jiǎn)單党瓮，假設(shè)關(guān)鍵字1234，那么它的平方為1522756盐类，再抽取中間3位就是227寞奸，用做散列地址。再比如4321在跳，那么它的平方為18671041枪萄，抽取中間3位就可以是671，也可以是710用做散列地址猫妙。
適用范圍：不知道關(guān)鍵字分布情況瓷翻，而且位數(shù)又不是很大的情況。
折疊法
將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（最后一部分位數(shù)不夠時(shí)可以短些）割坠，然后將這幾部分疊加求和齐帚，并按散列表表長(zhǎng)，取后幾位做為散列地址彼哼。
適用范圍：事先不需要知道關(guān)鍵字的分布对妄，適合關(guān)鍵字位數(shù)較多的情況。
4. 除留余數(shù)法
對(duì)于散列表長(zhǎng)為m的散列函數(shù)公式為：
f(key) = key mod p(p<=m)
其中mod是取模的意思敢朱。
事實(shí)上剪菱，這個(gè)方法不僅可以對(duì)關(guān)鍵字取模，也可以在折疊拴签、平方取中后再取模孝常。
此方法的關(guān)鍵在于如何選擇p，p如果選不好蚓哩，則可能很容易產(chǎn)生同義詞构灸。通常p為小于或等于表長(zhǎng)的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。
5. 隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)數(shù)杖剪，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址冻押。
f(key) = random(key)
適用范圍：關(guān)鍵字長(zhǎng)度不等時(shí)驰贷，可采用此方法。
四洛巢、處理散列沖突的辦法
1. 開放定址法
開放定址法是一旦發(fā)生了沖突括袒，就去尋找下一個(gè)空的散列地址，只要散列表足夠大稿茉，空的散表地址總能被找到锹锰，并將記錄存入。
f(key) = (f(key)+d) mod m (d=1,2,3...m-1)
這種解決沖突的開放定址法稱為線性探測(cè)法漓库。
2. 再散列函數(shù)法
每當(dāng)發(fā)生散列沖突的時(shí)候恃慧，就換一個(gè)散列函數(shù)計(jì)算，相信總有一個(gè)會(huì)把沖突解決掉渺蒿。
f(key) = RH(key)
其中RH是另一個(gè)散列函數(shù)痢士。
3. 鏈地址法
將所有關(guān)鍵字的同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，我們稱這種表為同義詞子表茂装，在散列表中只存儲(chǔ)所有同義詞子表的頭指針怠蹂。
此時(shí)已經(jīng)完全不存在沖突問題，無論有多少個(gè)沖突少态，都只是在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)而已城侧。
鏈地址法對(duì)于可能會(huì)造成很多沖突的散列函數(shù)來說，提供了絕對(duì)不會(huì)出現(xiàn)找不到地址的保障彼妻，但是查找時(shí)需要遍歷單鏈表嫌佑，增加了性能損耗。
五侨歉、散列表查找實(shí)現(xiàn)
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存儲(chǔ)空間初始分配量
#define SUCCESS 1
#define UNSUCCESS 0
//定義散列表長(zhǎng)為數(shù)組的長(zhǎng)度
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct
{
//數(shù)據(jù)元素存儲(chǔ)基址屋摇，動(dòng)態(tài)分配數(shù)組
int *elem;
//當(dāng)前數(shù)據(jù)元素個(gè)數(shù)
int count;
}HashTable;
int m=0; /* 散列表表長(zhǎng)，全局變量 */
//1.初始化散列表
Status InitHashTable(HashTable *H)
{
int i;
//① 設(shè)置H.count初始值; 并且開辟m個(gè)空間
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
//② 為H.elem[i] 動(dòng)態(tài)數(shù)組中的數(shù)據(jù)置空(-32768)
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
}
//2. 散列函數(shù)
int Hash(int key)
{
//除留余數(shù)法
return key % m;
}
//3. 插入關(guān)鍵字進(jìn)散列表
void InsertHash(HashTable *H,int key)
{
//① 求散列地址
int addr = Hash(key);
//② 如果不為空为肮，則沖突
while (H->elem[addr] != NULLKEY)
{
//開放定址法的線性探測(cè)
addr = (addr+1) % m;
}
//③ 直到有空位后插入關(guān)鍵字
H->elem[addr] = key;
}
//4. 散列表查找關(guān)鍵字
Status SearchHash(HashTable H,int key,int *addr)
{
//① 求散列地址
*addr = Hash(key);
//② 如果不為空摊册，則沖突
while(H.elem[*addr] != key)
{
//③ 開放定址法的線性探測(cè)
*addr = (*addr+1) % m;
//④H.elem[*addr] 等于初始值或者循環(huán)有回到了原點(diǎn).則表示關(guān)鍵字不存在;
if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
//則說明關(guān)鍵字不存在
return UNSUCCESS;
}
return SUCCESS;
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
int i,p,key,result;
HashTable H;
//1.初始化散列表
InitHashTable(&H);
//2.向散列表中插入數(shù)據(jù)
for(i=0;i<m;i++)
InsertHash(&H,arr[i]);
//3.在散列表查找key=39
key=39;
result=SearchHash(H,key,&p);
if (result)
printf("查找 %d 的地址為：%d \n",key,p);
else
printf("查找 %d 失敗肤京。\n",key);
//4.將數(shù)組中的key,打印出所有在散列表的存儲(chǔ)地址
for(i=0;i<m;i++)
{
key=arr[i];
SearchHash(H,key,&p);
printf("查找 %d 的地址為：%d \n",key,p);
}
return 0;
}
