哈希表

哈希表

散列表，也称哈希表，是根据关键字而进行访问的数据结构，它通过将关键字（key value）映射到表中，来提高访问速度，其中的映射函数叫做哈希函数，这种表称为哈希表，映像过程叫做哈希造表或散列。

冲突：对不同的关键字可能得到同一哈希地址，即key1!=key2，而f(key1)等于f(key2).

按处理冲突方法的不同，主要分成两类：1.开放寻址法、2.拉链法

拉链法

如果有两个关键字在进行映射后得到同一哈希地址，那么将这两个关键字存储到一个单链表中，并且使映射后的哈希地址(k表示哈希地址，h[k]存储其指向的单链表的头节点的下标)指向由发生冲突的关键字构成的单链表，这样，在哈希造表完成后，每次进行查询操作时，通过遍历每个h[k]下所指的单链表，即可完成查询操作。

图示：

拉链法创建的哈希表

例题：AcWing 840.模拟散列表：https://www.acwing.com/activity/content/problem/content/890/1/
代码：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 100003;

int h[N],e[N],ne[N],idx;

//e[]表示数据域，ne[]表示指针域，-1代表空结点
void Insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;  //将数据存储到结点中
    ne[idx] = h[k];
    h[k] = idx++;
}

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()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof(h));
    char s;
    int a;
    while(n--)  
    {
        cin>>s>>a;
        if(s == 'I')
            Insert(a);
        else
        {
            if(find(a))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
            
    }
    return  0;
}

开放寻址法

当要添加的关键字映射后的理论哈希地址与已映射的哈希地址发生冲突时，将当前的哈希地址向后移动，直到找到有效位置，并返回。

#include <iostream>
#include <cstring>

using namespace std;
const int N = 200003;
const int null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    int k = (x % N + N) % N;
    while( h[k] != null && h[k] != x)
    {
        k++;
        if(k == N)
            k = 0;
    }
    return k;
}

int main()
{
    int n;
    cin>>n;
    //memset按字节对内存进行初始化
    memset(h,0x3f,sizeof(h));
    char s[2];
    int a;
    while(n--)
    {
        cin>>s>>a;
        int k = find(a);
        if(s[0] == 'I')
            h[k] = a;
        else
        {
            if(h[k] != null)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return  0;
}