哈希表与哈希冲突（Hash表散列表）

lwy
基础算法
2024-08-23
328热度
0评论

一、哈希表是什么？

哈希表（Hash table 又叫散列表）是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。通常，我们把这个关键字称为Key值，对应的值称为Value值。关键值和Value值是一种一一对应的关系（也就是映射关系），这个映射表，也叫做哈希函数，存放记录的数组就是哈希表。哈希表也类似于离散化。

哈希表的作用：哈希表的作用就是能够通过Key值快速获取Key对应的Value值，它查询的时间复杂度几乎是O（1）的。

二、哈希冲突

我们要先了解一下：映射值和Key值

注意：

映射值：哈希函数下计算出来的值， Key值：Value一一对应的位置值
当在理想状况下（没有哈希冲突时，不存在这样的情况），哈希函数计算出来的映射值 == key值
在处理哈希冲突时，哈希函数计算出来的是映射值，key值是存放Value值的位置

哈希冲突：当两个不同的数（Value值）经过哈希函数运算得到同一个结果映射值时，就说明发生了哈希冲突。可以用一个例子来说：查询手机通讯录，你可以把通讯录的首字母查找（A~Z）比作映射值，名字比作Value值，假如你的通讯录有张三和张伟，那他们的映射值值都是Z，那么当你用Z（映射值）查找时，Value值却有两个，key值也有两个（Zhangsan和Zhangwei）。这就是哈希冲突

图解：

三、如何避免哈希冲突

我在写这篇文章的时候，我一开始写的是如何避免哈希冲突（× 错误的）。注意：哈希冲突是无法避免的，我们只能减少冲突，所以处理冲突是哈希表不可缺少的一部分。

处理冲突有很多方法，例如开放寻址法、再散列法、拉链法、建立公共溢出区等。在这我就主要讲一下开放寻址法和拉链法。

3.1.开放寻址法及代码

开放寻址法：哈希表是通过数组存储的，所以当我们用开放寻址法的时候就要创建一个足够大的数组（一般开数值数量的2~3倍）（开放），然后通过哈希函数计算得到映射值，找到能存放Value的位置（key值）。可以分为2个步骤：插入和查找。

插入：通过find函数来寻找一个地址（寻址）放置数值，若不为空，则查找下一个位置，直到找到个空位置或者这个数已经存在了。

查找：如果数组存在这个数值，就返回该值的地址，否则，返回NULL**;

int find(int x){    //返回位置值
    int k = (x % N + N) % N; ////哈希函数计算映射值
    //如果该位置的值不为空表示有其他的值已经将该位置占领了
    //如果该位置等于x值，说明x已经存在了，不需要在占位置了，直接返回存在的位置
    while(h[k] != null && h[k] != x) { 
        k ++;            //k ++表示一直向后查找
        if(k == N) k = 0; //如果查找到数组的尾部了，就从头部开始找。
    }
    return k;//现在k表示Key值。
}

完整代码：

///开放寻址法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 3, null = 0x3f3f3f3f;
int n, h[N];
int find(int x){
    int t = (x % N + N) % N;
    while(h[t] != null && h[t] != x) {
        t ++;
        if(t == N) t = 0;
    }
    return t;
}

int main(){
    cin >> n;
    memset(h, 0x3f3f3f3f, sizeof h);
    while(n --){
        char op;
        int x;
        cin >> op >> x;
        if(op == 'I') h[find(x)] = x; //插入操作
        else {
            if(h[find(x)] == null) puts("No");//查找操作
            else puts("Yes");
        }
    }
    return 0;
}

3.2.拉链法及代码

拉链法：这种方法的关键是把哈希函数运算的映射值都放到数组中，然后以映射值作头结点创建链表。利用链表来存储Value值，找到key值对应的位置（下面有图解）。分两个步骤：插入和查询

插入：利用单链表的形式插入以映射值为头结点的链表。

查找：也是单链表的查找方式

图解：

插入代码：

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;//找到返回True
    return  false;
}

完整代码：

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

//头插法 
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);//头结点赋值
    while(n--){
        string op;
        int x;
        cin>>op>>x;
        if( op== "I") insert(x);//插入
        else {
            if(find(x)) puts("Yes");//查找
            else puts("No"); 
        }
    }
    return 0;
}

哈希表与哈希冲突（Hash表 散列表）