攻克哈希的基本概念与实现

基本定义

哈希表的定义简介：：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

当然哈希表也有缺点，哈希表是基于数组的，我们知道数组创建后扩容成本比较高，所以当哈希表被填满时，性能下降的比较严重。

例子：：例如大家在上学的时候，大家都会有一个学号「1-n号」中的一个号码，如果我们用哈希表来存放班级里面学生信息的话，我们利用学号作为「键」或者「关键字」，这个「键」或者「关键字」就可以直接作为数据的下标，不需要通过哈希函数进行转化。如果我们需要安装学生姓名作为「键」或者「关键字」，这时候我们就需要哈希函数来帮我们转换成数组的下标。

几个关键点：：

1 冲突 ： 如果要实现一个简单的哈希，例如将一个很大的数映射到一定范围内的数值上，那将不可避免的存在冲突的现象，于是为了解决这种冲突，可以使用一些处理冲突的方法，介绍如下俩种处理冲突的方法：

2 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。。

---

存储方法

法一：：开放寻址法：

百度百科上是这样定义的：：1. 开放寻址法：Hi=（H（key）+ di） MOD m,i=1,2，…，k（k≤m-1），其中H（key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

1.1. di=1,2,3，…，m-1，称线性探测再散列；

1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k）^2,（km/2）称二次探测再散列；

1.3. di=伪随机数序列，称伪随机探测再散列。

2. 再散列法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

3. 链地址法（拉链法）

4. 建立一个公共溢出区。。

哈哈，反正我不是很能看得懂，对于初学者，我这样理解就行：：

对于开放寻址法： 通常用到的是查找 ， 插入 操作，删除一般在算法题中很是少见。。

之余开放寻址法 ， 可以通俗的将之看成是一个例子：：一个人去上厕所  ， 他需要找一个坑位， 他于是来到了第一个位置，若是这个位置空的，他就使用这个位置，若是这个位置已经被人占用 或是被损坏（即为读取到了所定义的空值），他只能就去下一个位置寻找坑位了，直到找遍每一个坑位，当然，在使用开放寻址法时，一般为了避免冲突的出现，都会多开所需数据范围的俩倍以上，这样就不可能存在同一个坑位的情况了

（特点总结： 以空间换来了时间）

时间复杂度只需要O（1） 只用开一个一维数组。。。。

所以发现，使用开放寻址法的时候只要写一个函数即可实现，

因为他返回的值如果存在就是他所在的位置，要不h（t）就是空值。。（因为足够大的数据空间保证了肯定存在，除非输入的就是所定义之外的“空值”）

 以下如图

 （来自acwing平台的算法基础课截图）

 

由此可以解决题目；；

 

注意：：开放寻址法这里查询和插入操作均用以下的find函数即可实现，因为它返回的值要么是空，要不就是他存储的位置。。。。

#include <cstring>
#include <iostream>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3f

int 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 n;

int main() {
    cin >> n;

    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f

    while (n--) {
        string 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;
}

这里的0x3f就是定义的空值，他一定小于-10的-9次方。。

法2：：：

拉链法：：

首先是定义：：

拉链法：也叫做链地址法。拉链发就是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。

也是为了处理冲突：拉链法采取就是这种类似邻接表的格式，

这种结构大体就是：：

 

它使用数组模拟链表的方式，如果很大的值域中的俩个不同的数映射的结果是一个值的话 ， 就建立一个链表使用链表的方法进行插入操作，虽然看似插了很多个链表，但是这些链表的长度都是一个常数，因此时间复杂度还可以看成是近似于O（1）的。。

                                               （来自acwing平台算法基础课的上课截图）

例题：

（还是刚刚那个）

根据题目意思

直接上代码：：

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度

//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    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 n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示

    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;
}

一个应用实践例子

哈希函数的实现：

哈希在算法中算是非常非常常用，这里针对于出现过的题目实现几种基本的算法。 。 。

字符串哈希的解决：：  （解决字串问题）

  在盲目刷题之前一定要先了解通透基础算法的使用，字符串哈希这个例子算是给了我一个教训，在解决这类问题时候竟然可以如此方便，当然之前的方法或是kmp确实也对锻炼思维能力有很大的帮助。

另外

字典与集合都是通过哈希表来实现的
a = {'name':'Alex', 'age':18, 'gender':'Man'}
使用哈希表存储字典, 通过哈希函数将字典映射为下标。假设h('name') =3， h('age')=1, h('gender')=4, 则哈希表存储为[None, 18,None, 'Alex', 'Man']
如果发生哈希冲突,则通过以上的拉链法或开发寻址方法尝试解决。

于是引出几个算法中常用的技巧：：

字符串哈希

首先还是定义：：字符串Hash，其实就是：构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应，也就是，一个字符串对应一个数字，那么一个数字也对应一个字符串。

目的：我们如果要比较一个字符串，我们不直接比较字符串，而是比较它对应映射的数字，这样子就知道两个“子串”是否相等。从而达到，子串的Hash值的时间为 O(1)，

进而可以利用“空间换时间”来节省时间复杂的。

需要用到的几个公式

1映射公式：(X1×Pn−1+X2×Pn−2+⋯+Xn−1×P1+Xn×P0)modQ

2 h[l,r]=h[r]−h[l−1]×Pr−l+1

这是处理区间和的公式

如果不理解的话代入一个例子即可清晰领悟（见图）

                                          （来自acwing算法平台基础课的上课图）

例：12345  （十进制）

345 = 12345 - 12*（10的3次方）

如此便可以得到一个数的后缀

注：这些式子中：P值和Q值是一个经验值，分别为131（或者1331）  和2的64次方。。

大体思路就是把一个字符串转化为一个p进制的数来进行子串的计算，时间复杂度当然只有O（1）.。

首先还要预处理出字符串的哈希值，利用前缀和的思想，

这个应该难不倒我们

所以看看例题;

 用字符串哈希的方法做做，发现非常清晰而且好做。。

直接上代码解决过程：：

#include<iostream>
using namespace std;
#include<cstring>
const int N= 100010 , P= 131;
typedef unsigned long long ULL;

int n , m ;
char str[N];
ULL h[N] ,p[N] ;

ULL get(int l ,int r)
{
    return  h[r] - h[l-1]*p[r-l+1] ;
}

int main()
{
    scanf("%d%d%s" , &n , &m , str+1);
    p[0] = 1;
    for(int i=1; i<=n ;i++)
    {
        p[i] = p[i-1] * P;                                   //important
        h[i] = h[i-1] *P +str[i];                    //预处理部分
    }
    
    while(m--)
    {
        int l1 , l2 ,r1 ,r2;
        cin>>l1>>r1>>l2>>r2;
        
        if(get(l1 , r1) == get(l2 , r2))   puts("Yes");
        else  puts("No");
    }
    
    return 0;
}

总结：以上大体来自与acwing算法基础课的听课总结和百度百科和一些书记资料，加以总结缕一缕学习的思路。

         还是不能急于求成，要多想多练，模板要了然于胸，才能一步一步攻克算法这个难关！！！