哈希

哈希表就是集查找、插入和删除于一身的一种数据结构（算法题里一般只有插入和删除操作）。哈希的过程就是把一个大的数据范围映射到一个较小的数据范围内的过程，这一点跟离散化很像，可以把离散化看成极其特殊的哈希方式。

因为数据量很大，哈希表难免会出现碰撞，就是把两个不一样的数映射成一样的数，key1 ！= key2 ，hash（key1） == hash（key2）这种情况，所以我们要避免冲突。

处理冲突的方法

以下题为例：

维护一个集合，支持如下几种操作：

I x，插入一个数 x（−109 ≤ x ≤ 109）；
Q x，询问数 x 是否在集合中出现过；
现在要进行 N （1 ≤ N ≤ 105）次操作，对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出Yes，否则输出 No。

1.拉链法——数组与链表的结合

假设我们刚开始将11映射到3的位置上，我们就在3的位置处拉出一个链，将11加进去；倘若第二次映射，23也映射到了3的位置，我们就继续把23加进去。这种处理冲突的方法就是拉链法。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insert(int data) {
    Link link = new Link(data);
    int key = link.getKey();
    int hashVal = hash(key);
    array[hashVal].insert(link);
}

public Link find(int key) {
    int hashVal = hash(key);
    return array[hashVal].find(key);
}

public void delete(int key) {
    int hashVal = hash(key);
    array[hashVal].delete(key);
}

2.开放寻址法

基本思路比较容易理解就是只在一个数组中进行操作，防止溢出范围一般要开到题目范围的2-3倍。

假如我们求出的哈希值hash（x） == k，我们就在一个数组从第k个位置开始，如果该位置被占用，则依次看下一个位置，直到找到空位置为止。

找下一个位置也有不同的方法

线性探测

插入思路很朴素：下标一位一位后移，直到为空。查找同理，先算得理论下标，向后逐位比对，若遍历至空位，说明没有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void insert(Student student){
    int key = student.getKey();
    int hashVal = hash(key);
    while (array[hashVal] != null && array[hashVal].getKey() != -1) {
        ++hashVal;
        // 如果超过数组大小，则从第一个开始找
        hashVal %= size;
    }
    array[hashVal] = student;
}

public Student find(int key){
    int hashVal = hash(key);
    while (array[hashVal] != null){
        if (array[hashVal].getKey() == key){
            return array[hashVal];
        }
        ++hashVal;
        hashVal %= size;
    }

    return null;
}

线性探测哈希表的删除相对来说比较复杂一点，我们不能简单的把这一项数据删除，让它变成空，为什么呢？

线性探测哈希表在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定哈希表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。

因此我们需要一个特殊的数据来顶替这个被删除的数据，因为我们的学生学号都是正数，所以我们用学号等于-1来代表被删除的数据。这样会带来一个问题，如何在线性探测哈希表中做了多次操作，会导致哈希表中充满了学号为-1的数据项，使的哈希表的效率下降，所以很多哈希表中没有提供删除操作，即使提供了删除操作的，也尽量少使用删除函数。

二次探测

在线性探测哈希表中，数据会发生聚集，一旦聚集形成，它就会变的越来越大，那些哈希函数后落在聚集范围内的数据项，都需要一步一步往后移动，并且插入到聚集的后面，因此聚集变的越大，聚集增长的越快。这个就像我们在逛超市一样，当某个地方人很多时，人只会越来越多，大家都只是想知道这里在干什么。

二次探测是防止聚集产生的一种尝试，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。在线性探测中，如果哈希函数得到的原始下标是x,线性探测就是x+1,x+2,x+3…，以此类推，而在二次探测中，探测过程是x+1,x+4,x+9,x+16,x+25…,以此类推，到原始距离的步数平方

双哈希（常用）

双哈希是为了消除原始聚集和二次聚集问题，不管是线性探测还是二次探测，每次的探测步长都是固定的。双哈希是除了第一个哈希函数外再增加一个哈希函数用来根据关键字生成探测步长，这样即使第一个哈希函数映射到了数组的同一下标，但是探测步长不一样，这样就能够解决聚集的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public void insert(Student student) {
    int key = student.getKey();
    int hashVal = hash(key);
    // 获取步长
    int stepSize = stepHash(key);
    while (array[hashVal] != null && array[hashVal].getKey() != -1) {
        hashVal +=stepSize;
        // 如果超过数组大小，则从第一个开始找
        hashVal %= size;
    }
    array[hashVal] = student;
}

public Student find(int key) {
    int hashVal = hash(key);
    int stepSize = stepHash(key);
    while (array[hashVal] != null) {
        if (array[hashVal].getKey() == key) {
            return array[hashVal];
        }
        hashVal +=stepSize;
        hashVal %= size;
    }

    return null;
}

public Student delete(int key) {
    int hashVal = hash(key);
    int stepSize = stepHash(key);
    while (array[hashVal] != null) {
        if (array[hashVal].getKey() == key) {
            Student temp = array[hashVal];
            array[hashVal] = noStudent;
            return temp;
        }
        hashVal +=stepSize;
        hashVal %= size;
    }
    return null;
}

双哈希的实现比较简单，但是双哈希有一个特别高的要求就是表的容量需要是一个质数，为什么呢？

为什么双哈希需要哈希表的容量是一个质数？

假设我们哈希表的容量为15，某个**「关键字」**经过双哈希函数后得到的数组下标为0，步长为5。那么这个探测过程是0,5,10,0,5,10，一直只会尝试这三个位置，永远找不到空白位置来存放，最终会导致崩溃。

如果我们哈希表的大小为13，某个**「关键字」**经过双哈希函数后得到的数组下标为0，步长为5。那么这个探测过程是0,5,10,2,7,12,4,9,1,6,11,3。会查找到哈希表中的每一个位置。

使用开放地址法，不管使用那种策略都会有各种问题，开放地址法不怎么使用，在开放地址法中使用较多的是双哈希策略。

字符串哈希

通过比对字符串的哈希值的方法快速判断两个字符串是否相同，操作及思路比KMP方法简单。

求字符串前缀的哈希值

将一个字符串看成一个P进制的数，最后转化成10进制数

假如我们要求一个字符串ABCD的哈希值，ABCD对应1234

A B C D
1 2 3 4
我们要求的就是字符串的前缀哈希值
h[0] = 0
h[1] = 'A’的哈希值
h[2] = 'AB’的哈希值
h[3] = 'ABC’的哈希值
h[4] = 'ABCD’的哈希值

ABCD的哈希值 h[4] =（1234）p = 1 * P3 + 2 * P 2 + 3 * P1 + 4 * P0

因为转化后的数字可能很大，所以我们要对所求的哈希值对Q取模

通过这样一种方式就可以把任意一个字符串映射成一个0~Q-1的数了

注意：
1.不能将字母映射成0，一般从1开始映射，不然会使不同的字符串的哈希值相同

2.有这样一组经验值，当P = 131 或 13331 Q = 264，且我们不那么非，在99.99%的情况下不存在冲突，这可不是我说的

3.因为Q = 264，所以我们用unsigned long long来存储所有的哈希值，就不需要对Q取模了。因为会溢出，所以就等价于取模了

求任意字串的哈希值

我们可以利用我们所求得的前缀哈希用一个公式算出来任意一个子串的哈希值

假设我们已知两个前缀哈希值h[R],h[L - 1], 目标是求得L~R的哈希值

即h[L~R] = h[R] -h[L-1] * PR-L+1

证明过程如下：

h[R] = 1 * PR-1 + 2 * PR-2 + …+ R * P0
h[L-1] = 1 * PL-2 + 2 * PL-2 + …+ (L-1) * P0
要求的L~R的哈希值， 我们需要将h[L-1] * PR-L+1 = 1 * PR-1 + 2 * PR-2 + …+ (L-1) * PR-L+1
h[L~R] = L * PR-L + (L+1) * PR-L-1 + …+ R * P0 = h[R] - h[L-1] * PR-L+1

其实本质就是进制转换