// N表示哈希表長(zhǎng)度，是一個(gè)素?cái)?shù)，M表示額外空間的大小，empty代表“沒(méi)有元素”。
const int N=9997, M=10000, empty=-1;
int a[N];
void init() // 初始化哈希表
{
memset(a,empty,sizeof(a)); // 注意，只有empty等于0或-1時(shí)才可以這樣做！
memset(bucket,empty,sizeof(bucket));
memset(first,0,sizeof(first));
}
inline int h(int); // 散列函數(shù)
int *locate(int, bool); // 用于存儲(chǔ)和查找的定位函數(shù)，并返回對(duì)應(yīng)位置。
// 如果用于存儲(chǔ)，則第二個(gè)參數(shù)為true，否則為false①。
void save(int x) // 存儲(chǔ)數(shù)據(jù)
{
int *p = locate(x, true);
if (p!=NULL) *p=x;
}
bool isexist(int x) // 查找數(shù)據(jù)
{
int *p = locate(x,false);
return (p!=NULL && *p==x);
}

散列函數(shù)

為了達(dá)到快速存儲(chǔ)和查找的目的，就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系 h。

這個(gè)關(guān)系 h 叫做哈希函數(shù)。

哈希表存取方便但存儲(chǔ)時(shí)容易沖突：即不同的關(guān)鍵字可以對(duì)應(yīng)同一哈希地址。如何確定哈希函數(shù)和解決沖突是關(guān)鍵。以下是幾種常見(jiàn)的哈希函數(shù)的構(gòu)造方法：

1. 取余數(shù)法：h(x) ＝ x％p（p≤N，且最好是素?cái)?shù)）

2. 直接定址法：h(x)＝x 或 h(x)＝a*x＋b

3. 數(shù)字分析法：取關(guān)鍵字的若干數(shù)位（如中間兩位數(shù)）組成哈希地址。

4. 平方取中法：關(guān)鍵字平方后取中間幾位數(shù)組成哈希地址。

5. 折疊法：將關(guān)鍵數(shù)字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）然后取幾部分的疊加和（舍去進(jìn)位）作為哈希地址。

6. 偽隨機(jī)數(shù)法：事先產(chǎn)生一個(gè)隨機(jī)數(shù)序列 r[]，然后令 h(x)＝r[x]。

設(shè)計(jì)哈希函數(shù)時(shí)，要注意

對(duì)關(guān)鍵碼值的分布并不了解——希望選擇的散列函數(shù)在關(guān)鍵碼范圍內(nèi)能夠產(chǎn)生一個(gè)大致平均的關(guān)鍵碼值隨機(jī)分布，同時(shí)避免明顯的聚集可能性，如對(duì)關(guān)鍵碼值的高位或低位敏感的散列函數(shù)。

對(duì)關(guān)鍵碼值的分布有所了解——應(yīng)該使用一個(gè)依賴于分布的散列函數(shù)，避免把一組相關(guān)的關(guān)鍵碼值映射到散列表的同一個(gè)槽中。

開(kāi)散列方法

哈希表中難免會(huì)發(fā)生沖突。使用開(kāi)散列方法可以解決這個(gè)問(wèn)題。常用操作方法是“拉鏈法”，即相同的地址的關(guān)鍵字值均鏈入對(duì)應(yīng)的鏈表中。

如果散列函數(shù)很差，就容易形成長(zhǎng)長(zhǎng)的鏈表，從而影響查找的效率。

下面是用“拉鏈法”處理沖突時(shí)的定位函數(shù)：

int size=-1;
struct node {int v; node * next;} *first[N], mem[M];
#define NEW(p) p=&mem[++size]; p->next=NULL
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) return &a[p];
// 處理沖突
node *q = first[p];
if (ins)
if (q==NULL)
{
NEW(q);
first[p]=q;
return &q->v;
}
else
{
while (q->next!=NULL) q=q->next;
node *r; NEW(r);
q->next=r;
return &r->v;
}
else
while (q!=NULL)
{
if (q->v == x) return &q->v;
q=q->next;
}
return NULL;
}

閉散列方法(開(kāi)地址方法)

處理沖突的另一種方法是為該關(guān)鍵字的記錄找到另一個(gè)“空”的哈希地址。在處理中可能得到一個(gè)地址序列 g(i)（i＝1，2，…，k；0≤g(i)≤n－1)，即在處理沖突時(shí)若得到的另一個(gè)哈希地址 g(1)仍發(fā)生沖突，再

求下一地址 g(2)，若仍沖突，再求 g(3)……怎樣得到 g(i)呢？

溢出桶法：設(shè)一個(gè)溢出桶，不管得到的哈希地址如何，一旦發(fā)生沖突，都填入溢出桶。

再哈希法：使用另外一種哈希函數(shù)來(lái)定位。

線性探查：g(i)＝(h(x)＋di) % N，其中 h(x)為哈希函數(shù)，N 為哈希表長(zhǎng)，di 為增量序列。

1. 線性探測(cè)再散列：di＝1，2，3，…，m－1

2. 二次探測(cè)再散列：

3. 偽隨機(jī)探測(cè)序列：事先產(chǎn)生一個(gè)隨機(jī)數(shù)序列 random[]，令 di＝random[i]。

下面是用溢出桶處理沖突時(shí)的定位函數(shù)：

int bucket[M], top=-1; // 用于閉散列方法（溢出桶）
int * locate(int x, bool ins=false)
{
int p=h(x);
if (a[p]==x && !ins) // 在查找模式下碰到了所需的元素
return &a[p];
else if (ins)
{
if (a[p]==empty) // 可以插入
return &a[p];
else // 處理沖突
return &bucket[++top];
}
else // 到溢出桶中尋找元素
for (int i=0; i<=top; i++)
if (bucket[i]==x) return &bucket[i];
return NULL;
}

下面是用線性探查處理沖突的定位函數(shù)，當(dāng)然，它也可以用于再哈希法處理沖突

inline int g(int p, int i) {return (p+i)%N;} // 根據(jù)需要來(lái)設(shè)計(jì)
int * locate(int x, bool ins=false)
{
int p=h(x);
int p2, c=0;
if (a[p]==x && !ins)
return &a[p];
else if (ins)
{
do
{
p2 = g(p, c++);
} while (a[p2]!=empty);
return &a[p2];
} else {
do
{
p2 = g(p, c++);
} while (a[p2]!=x && a[p2]!=empty);
if (a[p2]==x) return &a[p2];
}
return NULL;
}

閉散列方法的優(yōu)點(diǎn)是節(jié)省空間。不過(guò)，無(wú)論是溢出桶，還是線性探查，都會(huì)在尋址過(guò)程中浪費(fèi)時(shí)間。線性

探查的探查序列如果太長(zhǎng)，就會(huì)使一些其他元素被迫散列在其他位置，從而影響了其他元素的查找效率。