哈希表

                     

贡献者: 有机物

   哈希表又称散列表,哈希通常是把一些值域较大的数映射成值域较小的数。比如把 $10^8$ 映射成 $1$,$10^8 + 100$ 映射成 $2$。来看一道具体问题:

   维护一个集合,支持如下几种操作:

  1. 插入一个数 $x$;
  2. 询问数 $x$ 是否在集合中出现过;

   现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。

   数据范围:$ 1 \le N \le 10^5$,$\ -10^9 \le x \le 10^9$

   因为 $x$ 的值域非常大,所以我们需要设计一个哈希函数,能把一个值域比较大的数映射到从 $0 \sim 10^5$ 之间的一个数。

   一般哈希函数设计为 Hash(x) = (x mod P)

   因为因为值域变小了,很有可能把原始值不同的两个数映射到同一个位置,所以我们需要处理这种冲突情况。处理冲突的两种方式:拉链法开放寻址法

   拉链法:

   先开一个一维数组来保存每个数的哈希值,如果有数映射到了某个位置,我们就在那个位置开一个链表用于记录每个数。查询每个数是否存在的的时候,就在对应的哈希位置遍历一下整个链表,对其中的每个数比较其值与查询的值是否一致。

   拉链法的时间复杂度为 $O(N)$

图
图 1:拉链法

   一般来说,设计哈希算法取模的数要设置为一个质数,数学上可以证明这么取冲突的概率是最小的。

const int N = 1e5 + 3;

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

// 头插法
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void insert(int x)
{
    int k = (x % N + N) % N;   // 哈希位置
    add(k, x);
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; ~i; i = ne[i])  // 遍历整个链表
        if (e[i] == x)
            return true;
    return false;
}

   开放寻址法:

   开放寻址法只需要开一个一维数组,一般数组大小要开到题目要求的 $2 \sim 3$ 倍。开放寻址法的基本思路为:如果一个位置 $k$ 不是 $x$ 的话,那么就去 $k + 1$、$k + 2$ ... 找,添加一个数为:先从第一个位置找,如果为空的话就插入 $x$。查找一个数:从第 $k$ 个位置开始找,如果当前位置为空的话说明 $x$ 不存在。

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int n, h[N];

int find(int x)
{
    int k = (x % N + N) % N;
    while (h[k] != INF && h[k] != x)    // INF = 0x3f3f3f3f
    {
        k ++ ;  // 看完了 
        if (k == N) k = 0;  // 就循环看第一个位置
    }
    
    return k;  //1、如果在哈希表内就返回 k 就是 x 的下标  2、如果不在哈希表内就返回应该存储的位置
}

memset(h, 0x3f, sizeof h);  // 表示每个数最开始都是空的

   以上就是处理 $\mathtt{Hash}$ 冲突的两个方式。

                     

© 小时科技 保留一切权利