哈希表

定义

哈希表(Hash table)： 根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，你也可以叫哈希函数。存放记录的数组叫做散列表。

特点：

  • 哈希表是一种数据结构

  • 哈希表表示了关键码值和记录的映射关系

  • 哈希表可以加快查找速度

  • 任意哈希表，都满足有哈希函数h(key)，代入任意key值都可以获取包含该key值的记录在表中的地址

通俗讲，哈希表是一种表结构，我们可以直接根据给定的key值计算出目标位置。

在工程中这一表结构实现通常采用数组。

与普通的列表不同的地方在于，普通列表仅能通过下标来获取目标位置的值，而哈希表可以根据给定的key计算得到目标位置的值。

复杂度：

在列表查找中，使用最广泛的二分查找算法，复杂度为O(log2n)，但其始终只能用于有序列表。普通无序列表只能采用遍历查找，复杂度为O(n)。

而拥有较为理想的哈希函数实现的哈希表，对其任意元素的查找速度始终为常数级，即O(1)。

两个知识点：

  • 哈希函数： 将哈希表中元素的关键键值映射为元素存储位置的函数。

    以用 y ∈ (0~10^5) 的定义域 通过哈希表 表示值域为 x ∈ (-10^9 ~ 10^9) 的集合为例：

    设 x 为值域中的某个数，

    有 h(x) = y 。 y即定义域中的一个数。

    值域内的 x 通过哈希函数h(x) 表示了定义域的 y 。

  • 哈希冲突：不同的两个 x1，x2 通过哈希函数产生了相同的结果 y。

    这会导致结果冲突，即该哈希表中的 y ，到底是表示 x1 还是 x2 ？

存储结构：

1.拉链法 :开辟一个数组，元素作为链表存放冲突的哈希值。

2.开放寻址法：开辟一个数组，不需要链表，但长度往往是数据的2~3倍。

长度不一定这样长，但更长的长度冲突概率会比较低。

两道题

模拟散列表

1680779269035

拉链法

1.N = 100000?

根据tips，我们要对一个质数取模，1<=N<=10^5，通过试除法能求出来大于N的最小质数是10003。

2.取余值也是N？

x 取余 N，意味着用(0,N-1)的范围表示 x ，也就是(1,10^5) 。这符合我们的数组长度，防止越界。

(哈希函数相当于把10^-9～10^9中的一个个数x压缩存放在N(质数)个链表中)

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
42
43
44
45
46
47
48
#include<iostream>
#include<string.h>
using namespace std ;

//哈希表：实现无非是插入和查找两个功能
const int N = 100003;

int h[N],e[N],ne[N],idx; //静态链表
//h头结点 e 当前结点的值 ne 当前结点的下一个结点下标 ，idx 多余空间的下标 ，k 映射后呈现的数组值
void insert(int x)
{
    int k = (x%N+N)%N; //先取模再+N 使负余数转正（CPP特性）
    
    ne[idx] = h[k];
    h[k] = idx;
    e[idx] = x;
    idx++;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) //-1配合memset
        if (e[i] == x)
            return true;

    return false;
}

int main(void)
{
    int n;cin>>n;
    memset(h,-1,sizeof(h));
    while(n--)
    {
        char c[2];int x;
        cin>>c;cin>>x;
        if(*c=='I'){
            insert(x);
        }
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
               
    
}

开放寻址法

  • 特点：一旦find() 查找不到这个数据 ，就返回最近多余空间的下标。

    所以添加函数利用find就ok了。

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
#include <cstring>
#include <iostream>

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

int h[N];

int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x) //一直往后找闲置空间，null:数组边界
    {
        t ++ ;
        if (t == N) t = 0;    //循环查找
    }
    return t;
}

int main()
{    
	memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

0x3f :

memset是按字节赋值的，因此char类型的数组可以赋任意值。因此memset的正规用法是用来初始化char类型的数组的，也就是说它只会接受0x00-0xFF的值。

因为0的二进制是32个0，-1的二进制是三十二个1，所以使用memset可以直接初始化0和-1。如果要初始最大化，第一位是符号位为0，剩下为1，01111111化十六进制正好为0x7f，所以memset(arr, 0x7f, sizeof())就是初始最大化了。

但是这个数不能满足“无穷大加无穷大依然是无穷大”的性质，相加后它是一个很小的负数。所以一般无穷大常量取值是0x3f3f3f3f。

memse是按字节来初始化的，int中有四个字节，初始化成0x3f就是将每个字节都初始化成0x3f，所以每个int就是 0x3f3f3f3f。

0x3f3f3f3f十进制是1061109567，是10^9级别。
0x3f3f3f3f + 0x3f3f3f3f = 2122219134，没有超过32位int的范围，所以相加也满足“无穷大加无穷大以旧是无穷大”的性质

void memset(void *str, int ch, size_t n)
将str中当前位置后面的n个字节用ch替换并返回s，也就是说这个函数的作用是将数字以单个字节逐个拷贝的方式放到指定的内存中
memset(a, 127, sizeof(a))
127的二进制表示是01111111，在数组里存放的就是四个01111111，十进制数里是2139062143（小于int类型的范围）
memset(a, 127, sizeof(a))
128二进制是10000000，四个10000000就是-2139062144，就是初始化为一个很小的数

字符串哈希

Tips:

  1. 取模所用的数，一般都是质数。

    数学证明，取模质数时，哈希冲突的情况最少。

  2. 哈希表

  3. scanf读入字符，尽量以字符串形式读入。

    因为读入字符串 scanf 自动忽略回车空格换行符

  4. 哈希表的常用操作是 添加 和 查找。

    删除操作比较少。即使支持删除操作功能，也不一定删除源数据。

    （例如设置一个布尔变量或者什么标记，来判断该数据是否已被删除）

    删除操作可以看做查找操作的特殊处理。

  5. 取余 % 不要和除法 混淆。

    n = X%Y ，意味着 n ∈ (0,Y-1)

快来参与讨论吧~