哈希表存儲(chǔ)結(jié)構(gòu)：
1.開(kāi)放尋址法
2.拉鏈法

哈希表的主要作用：
把一個(gè)較大(0-10^9 )的數(shù)據(jù)映射到較小(0-N(N一般為10^5 到 10^6))的數(shù)據(jù)

哈希函數(shù)：可以把一個(gè)從-10^19 到10^19 的中的一個(gè)數(shù)映射到0-10^5之間的一個(gè)數(shù)

1.哈希函數(shù)怎么寫？
一般情況下，直接取模，x%10^5，我們一般模的數(shù)，一般取為質(zhì)數(shù)，并且離2的整次冪盡可能的遠(yuǎn)，這樣取，沖突的概率最小

2.沖突：把2個(gè)不一樣的數(shù)映射成同一個(gè)數(shù)怎么辦？
我們可以用開(kāi)放尋址法或者拉鏈法來(lái)解決這個(gè)問(wèn)題

首先我們先定義哈希函數(shù)：h(a) = b，指我們將a映射成b
這里我們只介紹拉鏈法。
拉鏈法：
參考文獻(xiàn)：
圖示算法

舉個(gè)例子：

維護(hù)一個(gè)集合，支持如下幾種操作：
“I x”，插入一個(gè)數(shù)x；
“Q x”，詢問(wèn)數(shù)x是否在集合中出現(xiàn)過(guò)；
現(xiàn)在要進(jìn)行N次操作，對(duì)于每個(gè)詢問(wèn)操作輸出對(duì)應(yīng)的結(jié)果。

輸入格式
第一行包含整數(shù)N，表示操作數(shù)量。
接下來(lái)N行，每行包含一個(gè)操作指令，操作指令為”I x”，”Q x”中的一種。

輸出格式
對(duì)于每個(gè)詢問(wèn)指令“Q x”，輸出一個(gè)詢問(wèn)結(jié)果，如果x在集合中出現(xiàn)過(guò)，則輸出“Yes”，否則輸出“No”。

每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍
1≤N≤105
?109≤x≤109
輸入樣例：
5
I 1
I 2
I 3
Q 2
Q 5
輸出樣例：
Yes
No

代碼如下:

#include <iostream> #include <cstring> using namespace std; const int N = 1e5+3; int h[N],e[N],ne[N],idx; void Insert(int x) {int t = (x%N+N)%N;e[idx] = x;ne[idx] = h[t];h[t] = idx++;}bool find(int x) {int t = (x%N+N)%N;for (int i = h[t];i!=-1;i = ne[i]){if (e[i]==x){return true;}}return false; }int main() {int cnt;cin>>cnt;memset(h,-1,sizeof(h));while(cnt--){string a;int b;cin>>a>>b;if (a[0]=='I') Insert(b);else{if (find(b)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的哈希表-拉链法及应用举例的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。