哈希表存储结构

整体结构

0~10⁹->0~10⁵

方法：

1. x mod 10⁵
2. 处理冲突
   1. 开放寻址法
   2. 拉链法

拉链法：

思想：每个槽上拉一条链，用于储存该槽上所有数

插入

1. 确定插槽
2. 确定插槽链表

3. 插入至头节点

​

查询

1. 确定插槽
2. 遍历插槽链表

题目

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

1.  `I x`，插入一个数 xx；
2.  `Q x`，询问数 xx 是否在集合中出现过；

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

输入格式

第一行包含整数 N，表示操作数量。

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

输出格式

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

每个结果占一行。

数据范围

1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109

输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
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

#include 
#include 
using namespace std;
const int N = 100003;

//e被拆成了很多链
int h[N],e[N],ne[N],idx;
//插入到链表头部
void insert(int x)
{
    //将k映射至题目范围
    int k = (x % N + N)%N;
    //插入：单链表插入
    //h[k]代表k链的头部节点，节点值为x
    e[idx] = x,ne[idx] = h[k],h[k] = idx++;
}
bool find(int x)
{
    int k = (x%N+N)%N;
    /*
    遍历，
    从头指针开始，头指针存储第一个结点的下标，
    e[i]表示当前节点的值是多少
    ne[i]下一个节点的下标
    空指针的下标为-1
    */
    for(int i = h[k];i!=-1;i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}


int main()
{
    /*寻找大于100000的最小质数
    //1.确定范围
    for(int i =100000;;i++)
    {
    	//2. 设置标志位
        bool flag = true;
        //3. 从2开始查找，条件为平方小于i
        for(int j = 2;j*j<=i;j++)
        {
            if( i % j == 0 )
            {
            	//4. 设置标志
                flag = false;
                break;
            }
        }
        //5. 判断标志
        if(flag)
        {
            cout<< i<
    int n;
    scanf("%d",&n);
	//槽清空
    memset(h,-1,sizeof(h));
    while(n--)
    {
        //注意此处为数组输入%s
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(*op == 'I') insert(x);
        else
        {
            if(find(x)) puts("Yes");
            else
                puts("No");
        }
    }
}


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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

注意

1. 取模计算

​ 负数模一个值等于该绝对值模值结果添加负号

-10 %3 = -1
1

​ 需要先模再加再模，才可以使得负数取模为正数。

开放寻址法

只开了一个一维数组，没有开辟链表，形式更为简单。

一维数组的长度经验来说开到题目的两到三倍

如何处理冲突：从第k个坑位开始找，如果第k个坑位有人的话就查找下一个坑位

一般题目只会用到查找与添加

添加

查找：从前向后找

删除：找到x后打个标记，表示x删除

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

1.  `I x`，插入一个数 xx；
2.  `Q x`，询问数 xx 是否在集合中出现过；

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

输入格式

第一行包含整数 N，表示操作数量。

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

输出格式

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

每个结果占一行。

数据范围

1≤N≤1051≤N≤105
−109≤x≤109−109≤x≤109

输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
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

查找质数

#include 

using namespace std;
//开两倍
const int N = 200003;

int main()
{
    //首先找到大于200000的质数
    for(int i = 200000;;i++)
    {
        bool flag = true;
        for(int j = 2; j*j<=i ;j++)
            if(i%j ==0)
            {
                flag = false;
                break;
            }
        if(flag)
        {
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}
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

得到结果为 200003

代码

#include 
#include 
using namespace std;
//N为大于2倍的最小质数，null为大于区间的一个值，用于表示空
//一般设置最大值也设置0x3f3f3f3f
const int N = 200003,null = 0x3f3f3f3f;
int h[N];

//find--寻找下一个坑位
int find(int x)
{
    //映射
    int k = (x % N + N) % N;
    //坑位有人并且不等于x
    //循环退出条件：找到值或者找到新的坑位
    //一定可以停止：因为数组大小较大
    while(h[k] != null && h[k] != x )
    {
        //向后查找下一个坑位
        k++;
        //如果已经到达结尾，循环看第一个坑位
        if(k == N) k = 0;
    }

    //如果x在哈希表中，k返回为下标；
    //如果不在哈希表中，k表示应该存储的位置
    return k;
}



int main()
{
    int n;
    int x;
    char op[2];
    /*
    为什么memset 0x3f
    因为memset按字节进行，不是按数字初始化的,h是int型数组，一共有4个字节，每个字节都是0x3f，因此每个数是0x3f3f3f3f.
    一个字节是八位。
    memset(h,0,sizeof(h)); 每个字节是0，整体为0
    memset(h,-1,sizeof(h));  每个字节是-1（1111 1111），整体为-1
    */
    memset(h,0x3f,sizeof(h));
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s%d",op,&x);
        int k = find(x);
        if(op[0] == 'I') h[k] = x;
        else 
        {
            if(h[k] != null) puts("Yes");
            else puts("No");
        }

    }
    return 0;
}

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
49
50
51
52
53
54
55
56
57
58
59
60

字符串哈希方式

字符串前缀哈希法

步骤：

1. 预处理所有前缀的哈希

   

   1. 如何定义某个前缀的哈希值

      把字符串看成P进制的数。

      假定映射关系如下表

      字母	值
      A	1
      B	2
      C	3
      D	4

      字符串“ABCD”对应的数值如下图所示：

      

   2. 预处理方式

      

   3. 将P进制的数转化为10进制的数；数字可能很大，通过取模进行映射到0,Q-1

      

注意：

1. 不能把字母映射为0。不然不同的字符串均映射为0导致出错与冲突

   

2. R_p【P进制】足够好，不存在冲突。经验值：131或13331

   

好处：可以利用前缀哈希，求得所有子串 的哈希值

已知h[R]、h[L-1]

1. h[L-1]左移至与R对齐

2. 然后相减: h[R]-h[L-1]+P^R-L+1

   

   

3. Q:2⁶⁴

   用unsigned long long存储h，当数值溢出相当于取模，因此不需要取模

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
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

#include 
#include 

typedef unsigned long long ULL;

const int N = 100010,P = 131;

int n,m;
char str[N];
/*
p数组用来存储p的多少次方的数值，p的0次方等于1
h数组表示某个前缀的哈希值，h[R]表示前R个字母的哈希值
*/
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;  //填充进制 P的一次方 P的二次方
        h[i] = h[i-1] * P+ str[i];  //填充前缀和
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1) == get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}
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

---

STL相关知识

/*
vector:变长数组，数组长度动态变化，倍增的思想
string：字符串，substr(),c_str()
queue:push(),front(),pop()
priority queue,优先队列，push(),top(),pop()
stack,栈，push(),top(),pop()
deque,双端队列
set,map, multiset,multimap，基于平衡树二叉树（红黑树）实现，动态维护有序序列
unordered_set,unordered_map,unordered_multiset,unordered_multimap，哈希表
bitset，压位
*/
1
2
3
4
5
6
7
8
9
10
11

一开始学习的时候，现用现查就可以了

vector的倍增思想

系统为某一个程序分配空间时，所需的时间基本上与空间大小无关，与申请次数有关

vector数组长度不够时，新建一个二倍长度的数组，然后把之前的数据copy过来

/*知道存在该操作，用的时候现用现查
vector:变长数组，数组长度动态变化，倍增的思想
        size();  //返回元素个数
        empty();  //返回a是否为空
        clear():清空，这个函数不是所有容器都有
        front()/back()
        push_back()/pop_back()
        begin()/end()
        [] 随机取址
        支持比较运算
pair 用于存储二元组
        first,第一个元素
        second, 第二个元素
        支持比较运算，以first为第一个关键字，以second为第二个关键字（字典序）
        pair与结构体相比有什么好处
        pair可以看作帮我们实现了一个结构体，自带一个比较函数，比一般结构体省代码
        可以存储任意多个，可以随便嵌套
string：字符串，substr(),c_str()
        size()/length() 返回字符串长度
        empty()
        clear()
queue:队列，队尾插入，队头弹出，先入先出的关系
        size()
        empty()
        push()  向队尾插入一个元素
        front()  返回队头元素
        back()  返回队尾元素
        pop()  弹出队头元素
        没有clear函数，如果需要清空一个queue，直接构造一个queue就可以
        定义时小根堆，多加两个参数
        priority_queue,greater> heap;
priority queue,优先队列，默认时大根堆
        push(),插入一个元素
        top(),返回堆顶元素
        pop()，弹出堆顶元素
stack,栈，
        size()
        empty()
        push(),向栈顶插入一个元素
        top(),返回栈顶元素
        pop()，弹出栈顶元素
deque,双端队列
        size()
        empty()
        clear()
        front()
        back()
        push_back() / pop_back()
        push_front() / push_front()
        begin() / end()
        []
        deque用的比较少，以为deque的效率低的令人发指，比一般的慢好几倍
set,multiset,map, multimap，
 基于平衡树二叉树（红黑树）实现，动态维护有序序列
        size()
        empty()
        clear()
        begin()/end() ++，--  返回前驱和后继 时间复杂度 O(logn)

        set/multiset
            set不支持插入重复元素
            multiset 支持插入重复元素
            insert() 插入一个数
            find() 查找一个数
            count() 返回某个数的个数
            erase()
                (1)输入是一个数，删除所有x  O(k + log(n))//k为数的个数
                (2)输入一个迭代器，删除这个迭代器
            lower_bound()/upper_bound()
                lower_bound(x) 返回大于等于x的最小的数的迭代器
                upper_bound(x) 返回大于x的最小的数的迭代器
        map/multimap
            insert()   插入的数是一个pair
            erase()   插入的参数是pair或者迭代器
            find()
            [] 时间复杂度是O(logn)
            lower_bound()/upper_bound()


unordered_set,unordered_map,unordered_multiset,unordered_multimap，哈希表
        和上面类似，增删改查的时间复杂度是O(1)
        不支持lower_bound()/upper_bound(),及迭代器的++ --
bitset，压位
        一个整数，4个字节，32位，
        很多题目压位计算
        bitset
        1024 bool数组 C++中一个bool是一个字节
        1024B = 1KB
        移到位中去，只需要开128B，比正常数组省8倍内存
        bitset<10000> s; <>中为个数
        ~s,&,|,^
        >>,<<
        ==,!=
        []
        count() 返回多少个1
        any/none()
            any() 判断是否至少有一个1
            none() 判断是否全为0
        set() 把所有位置置为1
        set(k,v) 将第k位变为v
        reset()  把所有位变为0
        flip()  等价于~
        flip(k)  把k位取反

C++ Reference C++最权威语法
*/
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace  std;

int main()
{
    /*
    vector a;
    vector b(10);
    vector c(10,-3);
    for(auto x :c )
        cout< a[10];
    //size与empty是所有元素都有的函数，所有容器都有
    //时间复杂度是O(1)的，不会说求size的时候遍历，而是有一个变量来存储size
    a.size();  //返回元素个数
    a.empty();  //返回a是不是空的
     */
    /*vector遍历
    vector a;
    for(int i = 0 ;i < 10;i++) a.push_back(i);
    for(int i = 0;i::iterator i = a.begin();i != a.end();i++) cout<<*i<<' ';
    //auto关键字，系统自动推断类型，当类型特别长时,用auto很省事
    for(auto i = a.begin();i != a.end();i++) cout<<*i<<' ';
    cout< a(4,3),b(3,4);
    if(a < b) puts("a
    /*
     *  pair p;
     *  某个东西有两个不同的属性，就可以用pair存储，可能需要按照某一个属性排序
        p.first
        p.second
        有三个属性也可以用pair存储
        pair > p

        pair p;
        p = make_pair(10,"jgy");
        p = {20,"abc"};

     * */
    /*
     * string a = "yxc";
    a += "def";
    a += 'c';

    //  cout<< a <

    /*queue清空
     * queue a;
    a = queue();
     * */
    /* heap默认大根堆
     *   priority_queue heap;
     * 如果要使用小根堆，
     * 1. 直接插入-x
     * 2. 定义时直接定义为小根堆，多加两个参数
     *  //小根堆
    priority_queue,greater> heap;
     * */
    /*集合
     * set s;
    multiset ms;
     * */
    /*map
     *     map a;
    a["yxc"] = 1;
    cout<
    /*
    unordered_map a;
    unordered_multimap b;
    return 0;
     * */
    /*bitset
     * 10000*10000 bool
     * 10的8次方 100MB空间  题目限制64M
     * bitset 12M足够了
     * */
 }
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

bitset

1024 bool数组 C++中一个bool是一个字节

1024B = 1KB

移到位中去，只需要开128B