實現

哈希表，即散列表，可以快速地存儲和查詢記錄。理想哈希表的存儲和查詢時間都是 O(1)。

本《資料》中哈希表分以下幾部分：散列函數、存儲和查找時的元素定位、存儲、查找。刪除操作因為不常用，所以只給出思想，不給出代碼。

根據實際情況，可選擇不同的散列方法。

以下代碼假設哈希表不會溢出。

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

散列函數

為了達到快速存儲和查找的目的，就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系 h。

這個關系 h 叫做哈希函數。

哈希表存取方便但存儲時容易沖突：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數和解決沖突是關鍵。以下是幾種常見的哈希函數的構造方法：

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

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

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

4. 平方取中法：關鍵字平方后取中間幾位數組成哈希地址。

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

6. 偽隨機數法：事先產生一個隨機數序列 r[]，然后令 h(x)＝r[x]。

設計哈希函數時，要注意

對關鍵碼值的分布并不了解——希望選擇的散列函數在關鍵碼范圍內能夠產生一個大致平均的關鍵碼值隨機分布，同時避免明顯的聚集可能性，如對關鍵碼值的高位或低位敏感的散列函數。

對關鍵碼值的分布有所了解——應該使用一個依賴于分布的散列函數，避免把一組相關的關鍵碼值映射到散列表的同一個槽中。

開散列方法

哈希表中難免會發生沖突。使用開散列方法可以解決這個問題。常用操作方法是“拉鏈法”，即相同的地址的關鍵字值均鏈入對應的鏈表中。

如果散列函數很差，就容易形成長長的鏈表，從而影響查找的效率。

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

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;
}

閉散列方法(開地址方法)

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

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

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

再哈希法：使用另外一種哈希函數來定位。

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

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

2. 二次探測再散列：

3. 偽隨機探測序列：事先產生一個隨機數序列 random[]，令 di＝random[i]。

下面是用溢出桶處理沖突時的定位函數：

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;
}

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

inline int g(int p, int i) {return (p+i)%N;} // 根據需要來設計
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;
}

閉散列方法的優點是節省空間。不過，無論是溢出桶，還是線性探查，都會在尋址過程中浪費時間。線性

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

刪除*

如果使用開散列方法，那么可以直接刪除元素。然而，使用閉散列方法，是不可以直接刪除元素的。假如

直接刪除，很有可能會影響其他元素的查找。

在這種情況下，有兩種刪除方法：一種是交換法，另一種是標記法。

交換法：在刪除某元素時，不要立刻把它清除。按照線性探查函數繼續尋找，直到沒有數值為止。將遇到

的最后一個數值與它交換。當然，交換之前還要進行類似的操作，可謂“牽一發而動全身”。

標記法：開一個標記數組 flag[]。如果第 i 個元素被刪除了，就將 flag[i]設為 true。

1. 插入元素時，如果所在位置有標記，就把元素放到這里，并把標記清除。

2. 查找元素時，如果經過標記，就跳過去繼續查找。

3. 為了哈希表的效率，應該定期清理表中的標記（或重新散列所有元素）。