学习笔记哈希表

Lbmttw 2019-08-08 原文

最近开始把之前欠的NOIP基础知识点刷一下

2333其实我的作业还没有写完

做到哈希表的时候，我有点懵，显然前几次讲课的时候我没有听

于是Lbmttw_lx就开始在网上学习了

（啊啊啊沙雕橘猫真心可爱，爱了爱了）

发现其实Hash表是个比较有趣的东西

（一种典型的空间换时间的数据结构，也叫散列表）

时间复杂度O(1)查询

哈希表之所以能过做到O（1）查询，是因为它的查询是直接按照关键字Key Value来的

也就是说，它将关键字通过某种规则映射到数组中的某个位置，以加快查找的速度。

哈希表中的每一个元素，都应该有且只有一个地址。

如果两个元素都拥有一个地址，就产生了哈希冲突，发生冲突的不同关键字被称之为同义词。

处理哈希冲突有很多方法，但是都是基于处理关键字而来的，尽可能让关键字都不相同。

那么，关键字是如何来的呢？其实就是哈希函数处理得到的。

首先是哈希函数H，H就是赋予特定元素特定的地址的函数，哈希表则是基于哈希函数而建立起来的查找表

那么问题来了，既然哈希函数这么好，我们如何构造它呢？？

有好几种构造哈希函数的方法，分别是

1.直接定址法

2.数学分析法

3.平方取中法

4.折叠法

5.除留余数法

由于第一种和第五种方法可能用到的比较广泛，主要说一下这两种吧

我是不会告诉你们剩下几种我也不会的！

1.直接定址法

取元素的关键字或关键字的线性函数值为散列地址

如H(x)=x或H(x)=a*x+b（a，b都为常数）

2.除留余数法

取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。

即 H(key) = key % p, p < m。

还有很多构造哈希函数的方法，无论是什么方法，原则都应该是

尽可能避免或减少哈希冲突

23333上那道模板题

问题描述

给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 10^9，并且每个集合的元素个数不大于10000 个。我们希望求出A、B之间的关系。只需确定在B 中但是不在 A 中的元素的个数即可。

输入文件

第一行两个数m和n分别表示集合A和集合B元素的个数。以下两个分别是集合A和集合B的元素。

输出文件

一个数，表示在B中但是不在 A 中的元素的个数。

输入样例

5 6
1 3 8 4 9
4 8 9 10 12 13

输出样例

限制和约定

时间限制：1s

空间限制：128MB

是不是看完博客介绍之后觉得这道题很简单了呢？？

 1 #include <bits/stdc++.h>
 2 #define mo 100005
 3 #define MAXN 2000000
 4 using namespace std;
 5 int m,n,a[MAXN],b,ans,ha[MAXN],now[MAXN];
 6 bool Hash(int i)
 7 {
 8     int pos=a[i]%mo+1;    //除留余数法赋予地址 
 9     ha[i]=now[pos];
10     now[pos]=i;
11 }
12 bool judge(int x)
13 {
14     int pos=x%mo+1;
15     bool ju=0;
16     for(int i=now[pos];i;i=ha[i])   //类不类似于 图论中的链表 
17     {
18         if(a[i]==x)
19         {
20             ju=1;
21             break;
22         }
23     }
24     return ju;
25 }
26 int main()
27 {
28     cin>>m>>n;
29     for(int i=1;i<=m;i++)
30     {
31         scanf("%d",&a[i]);
32         Hash(i);
33     }
34     for(int i=1;i<=n;i++)
35     {
36         scanf("%d",&b);
37         if(!judge(b))
38         ans++;
39     }
40     cout<<ans<<endl;
41     return 0;
42 }