目錄

一：介紹

一：什么是哈希表

二、哈希表的應(yīng)用

二：存儲結(jié)構(gòu)

a.拉鏈法：

b.開放尋址法：

三：擴(kuò)展

a.字符串哈希：

例題：?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-425080.html

?

一：介紹

一：什么是哈希表

1、哈希表也叫散列表，哈希表是一種數(shù)據(jù)結(jié)構(gòu)，它提供了快速的插入操作和查找操作，無論哈希表總中有多少條數(shù)據(jù)，插入和查找的時間復(fù)雜度都是為O(1)，因?yàn)楣１淼牟檎宜俣确浅？?，所以在很多程序中都有使用哈希表，例如拼音檢查器。

2、哈希表也有自己的缺點(diǎn)，哈希表是基于數(shù)組的，我們知道數(shù)組創(chuàng)建后擴(kuò)容成本比較高，所以當(dāng)哈希表被填滿時，性能下降的比較嚴(yán)重。

3、哈希表是由鏈表和數(shù)組組成的：

? ? ? ? 鏈表：增刪的效率極高，但是查詢的效率極低。

? ? ? ? 數(shù)組：查詢效率極高，增刪效率低

? ? ? ? 所以哈希表中繼承了鏈表和數(shù)組的優(yōu)缺點(diǎn)，不僅查詢效率高，增刪效率也高

4、哈希表通過鍵值對的方式存儲數(shù)據(jù)，【key，value】，哈希表會通過散列函數(shù)/哈希函數(shù)將key轉(zhuǎn)換成對應(yīng)的數(shù)組下標(biāo)?！静捎?先絕對值再% 的方式】

二、哈希表的應(yīng)用

? ? 通常數(shù)據(jù)都是放在數(shù)據(jù)庫中的，但是有一些數(shù)據(jù)不需要存放在數(shù)據(jù)庫中 ，太麻煩，那么就需要我們使用緩存層
? ? ? ? 緩存層一般有倆種：

? ? ? ? ? ? 緩存產(chǎn)品或者自己寫一個緩存層(也就是哈希表)

通過一個列子自己構(gòu)建出哈希表：

看一個實(shí)際需求，google公司的一個上機(jī)題:

有一個公司,當(dāng)有新的員工來報(bào)道時,要求將該員工的信息加入(id,性別,年齡,住址..),當(dāng)輸入該員工的id時,要求查找到該員工的 所有信息.

要求: 不使用數(shù)據(jù)庫,盡量節(jié)省內(nèi)存,速度越快越好

思路：

? ? ? ? 1、首先要求不使用數(shù)據(jù)庫，那么是能用一些緩存產(chǎn)品用來存儲數(shù)據(jù)，所以需要構(gòu)建一個哈希表

? ? ? ? 2、哈希表有數(shù)組，鏈表組成。在鏈表中保存員工數(shù)據(jù)信息，數(shù)組中保存鏈表
?

二：存儲結(jié)構(gòu)

哈希表的最主要作用是將一個比較大的范圍（如10^9）映射到一個比較小的空間（0 ~ N，其中N一般為10^5 - 10^6），通過一個哈希函數(shù)h(x)完成上述操作。

這里很容易產(chǎn)生哈希沖突，可能會把若干不同的數(shù)映射為同一個數(shù)。處理沖突的方法有兩種：開放尋址法和拉鏈法。

a.拉鏈法：

開辟一個10^5大小的空間，每個空間相當(dāng)于一個槽，每次映射到某個位置就在下面連接一條鏈。

其實(shí)就是單鏈表的存儲方式。

拉鏈法是把所有的同義詞用單鏈表鏈接起來的方法。在這種方法中，哈希表的每個單元存儲的不再是元素本身，而是相應(yīng)同義詞單鏈表的頭指針（注意是頭指針而不是頭節(jié)點(diǎn)）。

對于單鏈表，我們算法比賽可以采用數(shù)組的方式進(jìn)行實(shí)現(xiàn)。
?

(1) 拉鏈法

    #include <iostream>
    #include <cstring>
 
    using namespace std;
 
    const int N = 100003;
    int n;
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一個數(shù)
    void insert(int x)
    {
        int k = (x % N + N) % N;   //哈希函數(shù)。這里防止k為負(fù)數(shù)且映射到小范圍
        e[idx] = x;                //單鏈表的插入
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查詢某個數(shù)是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])  //遍歷
            if (e[i] == x)
                return true;

        return false;
    }

    

    int main(){
    scanf("%d", &n);
    // 初始化鏈表（鏈表中-1代表NULL）
    memset(h, -1, sizeof h);
    
    while(n--){
        char op[2];
        int x;
        scanf("%s %d", op, &x);
        if(*op == 'I'){
            insert(x);
        }
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
}

?

b.開放尋址法：

找?guī)游?/p>

?

(2) 開放尋址法
#include <iostream>
#include <cstring>
 
using namespace std;
 
// 約定一個null值作為標(biāo)準(zhǔn)，如果h數(shù)組上的某個位置等于這個標(biāo)準(zhǔn)的話，就說明這個位置是空的
// 要求這個數(shù)不在 -10^9 <= x <= 10^9 范圍內(nèi)即可
const int N = 200003, null = 0x3f3f3f3f;
int n;
int h[N];
 
int find(int x){
    int k = (x % N + N) % N;
    // 該位置有人且值不為x，就要向后看
    while(h[k] != null && h[k] != x){
        k++;
        if(k == N) k = 0;
    }
    return k;
}
 
int main(){
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    
    while(n--){
        char op[2];
        int x;
        scanf("%s %d", op, &x);
        if(*op == 'I') h[find(x)] = x;
        else{
            if(h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

memset函數(shù)解釋

三：擴(kuò)展

a.字符串哈希：

當(dāng)key為字符串時，h(key)稱為字符串哈希。

將字符串看成一個p進(jìn)制的數(shù)，將它轉(zhuǎn)化為十進(jìn)制數(shù)再對Q取模，即可得到一個映射到0-Q范圍內(nèi)的數(shù)

1. 不能將字符映射成0：例如將"A"映射成0，則"AA"，"AAA"的值均為零。所以應(yīng)當(dāng)從1開始。

2. 經(jīng)驗(yàn)值：p=131 ||? ?13331，Q=2^64時幾乎沒有沖突? //利用?unsigned long long，它的大小就是2^64，這樣我們就無需進(jìn)行取模的操作了，因?yàn)樗绯龊缶拖喈?dāng)于幫我們?nèi)∧Ａ恕?/p>

?

我們可以通過求前綴哈希，通過某一個公式求出任意子串的哈希值：

string: ? ? ?_______|__________|__________
? ? ? ? ? ?高位 ? ? ?L ? ? ? ? ?R ? ? ? ?低位
現(xiàn)在已知h[R]和h[L - 1]
我們有：
h[R] ? ?= ?p^R-1 * "_" + p^R-2 * "_" + ... + p^0 * "_"
h[L - 1] = p^L-2 * "_" + p^L-3 * "_" + ... + p^0 * "_"
容易知道只需：h[R] - h[L - 1]*p^(R - L + 1)
就能求得L-R間子串的哈希值
同時由上面的字符串哈希的定義，有：
h[i] = h[i - 1]*p + str[i];

?

例題：?

AcWing 841.字符串哈希?

給定一個長度為n的字符串，再給定m個詢問，每個詢問包含四個整數(shù)l1,r1,l2,r2，請你判斷[l1,r1]和[l2,r2]這兩個區(qū)間所包含的字符串子串是否完全相同。

字符串中只包含大小寫英文字母和數(shù)字。

輸入格式
第一行包含整數(shù)n和m，表示字符串長度和詢問次數(shù)。

第二行包含一個長度為n的字符串，字符串中只包含大小寫英文字母和數(shù)字。

接下來m行，每行包含四個整數(shù)l1,r1,l2,r2，表示一次詢問所涉及的兩個區(qū)間。

注意，字符串的位置從1開始編號。

輸出格式
對于每個詢問輸出一個結(jié)果，如果兩個字符串子串完全相同則輸出“Yes”，否則輸出“No”。

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

數(shù)據(jù)范圍
1≤n,m≤105
輸入樣例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
輸出樣例：
Yes
No
Yes

#include <iostream>
 
using namespace std;
 
typedef unsigned long long ULL;
 
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL p[N], h[N];
 
ULL find(int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
 
int main(){
    scanf("%d %d", &n, &m);
    // str從str[1]開始填入數(shù)據(jù)，因?yàn)閔[i] = h[i - 1]*p + str[i]、h[0] = 0
    scanf("%s", str + 1);
    
    p[0] = 1;
    for(int i = 1; i <= n; i++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    
    while(m--){
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        if(find(l1, r1) == find(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

?

?

?

?

?

?

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】哈希表（算法比賽向）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！