算法基础（6）

哈希表

主要讲两部分内容：存储结构—（开放寻址法，拉链法），字符串哈希方式

哈希表的主要作用是把一个比较大的空间映射到一个比较小的空间（如0-N），如$x \in (-10^9,10^9)$，哈希函数$h(x) \in (0,10^5)$。

如何构造哈希函数：

1. 直接取模 $x \quad\% \quad 10^5 \in (0,10^5)$；（取模的这个数一般要取成质数，且要离2的几次方尽量远，这样冲突的几率是较小的）
2. 冲突：直接取模会把不同的数映射到相同的数。处理冲突的方式可以分为：开放寻址法和拉链法

在算法题中一般不需要在哈希表中进行删除操作，一般只有添加和查找操作。

拉链法

拉链法：开一个一维数组h[]来存储所有的哈希值。每一次当把一个$x$映射到某一个数时，假设第$1$个数插入11，,$h(11)=3$，就在3下面拉一条链（单链表），存下11，即e[1]=11; ne[1]=h[3]=0; h[3]=1；如果第$4$次插入另一个数23，$h(23)=3$，就将23插入到h[3]下面这条链表中，插到头节点，即让e[4] = 23; ne[4] = h[3]= 1, ne[23]=4。

当要查找数11时，先求$h(11)=3$，循环for(i = h[k]; i != -1; i = ne[i])，首先i = h[3] = 4，而e[4]=23不等于11；就让i=ne[4]=1，e[1]=11，因此就找到了11。

例题1：模拟散列表

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

“I x”，插入一个数x；“Q x”，询问数x是否在集合中出现过；

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

输入格式：第一行包含整数N，表示操作数量。接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。

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

数据范围：$1 \le N \le 10^5$，$-10^9 \le x \le 10^9$。

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x)
{
    int k = (x % N + N) % N;  //让负数模N的结果也是正数
    e[idx] = x;       //e[]存第idx个插入的数的值
    ne[idx] = h[k];   //ne[]存第idx个插入的数的next节点，每次在拉链上插入都是插入到头节点
    h[k] = idx ++;    
}

bool find(int x)
{
    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 main()
{
    int n;
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        if(op[0] == 'I')  insert(x);
        else
        {
            if(find(x))  puts("Yes");
            else puts("No");
        }
    }
    
    return 0;
}

开放寻址法

开放寻址法：只开一个数组，但数组长度要开到题目给出的数据范围的2-3倍（经验值）。

添加：$h(x)=k$，先找到k，从第k个坑位开始找，直到找到第一个空的坑位为止，插入。

查找：从第k个坑位开始，从前往后找，每一次看当前坑位是否有数，若是x则查找成功；若不是x，就往后找；若坑位没数，则查找失败。

#include<iostream>
#include<cstring>
using namespace std;

const int N = 200003;  //先找到大于200000的最小质数
const int null = 0x3f3f3f3f;   //找一个数表示坑位没人，要在题目数据范围之外

int h[N];

//如果x在哈希表中已经存在，就返回x的位置；若x在哈希表中不存在，就返回它应该存储的位置
int find(int x)  
{
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x)
    {
        k++;
        if(k == N)  k = 0;
    }
    return k;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    memset(h, 0x3f, sizeof h);  //按字节来初始化
    
    while(n--)
    {
        char op[2];
        int x;
        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;
}

字符串前缀哈希法

字符串哈希方式——字符串前缀哈希法

str="ABCABCDEYXCAcwing"，预处理出所有前缀的哈希，如h[0]=0；h[1]="A"的哈希值；h[2]="AB"的哈希值,……

如何来定义某一个前缀的哈希值：把字符串看成一个P进制的数，如$”ABCD”=(1234)_P=1 \times P^3+ 2 \times P^2 + 3 \times P^2 + 4 \times P^0$，若字符串很长，那转化后的数会很大，因此可以让其模上一个较小的数$Q$，这样就能把字符串映射到$0 $~ $Q-1$之间的数。计算前i个字符的前缀就是：h[i] = h[i-1]* p + str[i]

要注意的是：不能把一个字母映射到0；前一小节中哈希数字时可能发生冲突，这里的字符串哈希是假定我们人品够好，不去考虑冲突的情况，当然也有经验值：$P=131或13331$，$Q=2^{64}$时，$99.99\%$不会遇到冲突。

这样做的好处：可以利用前缀哈希，计算出任意一个子段的哈希值。

如已知从1到R的哈希值h[R]，从1到L-1的哈希值h[L-1]，由于左边时高位，右边是低位。先将h[L-1]这一段往左移若干位，让它和h[R]这一段右端点对齐（就是让哈希值位数相等，相当于在h[L]后面补0啦），然后两段哈希值相减，用公式表示就是：

$$h[R]-h[L-1] \times P^{R-L+1}$$

还有一个技巧是：我们最后要模$2^{64}$，那直接可以用unsinged long long来存哈希值h[]，若溢出就等价于模$2^{64}$。

字符串哈希相较于kmp的独特作用：快速判断两个区间内的字符串是否相同。

字符串哈希例题（Acwing 841）

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数$l_1,r_1,l_2,r_2$，请你判断$[l_1,r_1]$和$[l_2,r_2]$这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。

输入格式：第一行包含整数n和m，表示字符串长度和询问次数。第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。接下来m行，每行包含四个整数$l_1,r_1,l_2,r_2$，表示一次询问所涉及的两个区间。注意，字符串的位置从1开始编号。

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

数据范围：$1 \le n,m \le 10^5$

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];  //h[N]存字符串的哈希值，p[N]存p的几次方

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[]，即p的几次方；以及h[]，即字符串的前缀哈希值
    {
        p[i] = p[i - 1] * 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;
}

STL

vector：可变数组，采用倍增的思想——在数组扩展空间使，将其原来的空间再扩大一倍，对空间为n的大小只需扩展$\log (n)$次即可，对每一次的扩展只用$O(1)$来实现。（系统为某一程序分配空间时，所需时间与空间大小无关，与请求次数有关）

#include<vector>

//定义一个vector
vector <int> a;

//定义一个vector，指定长度为100，先初始化为1
vector <int> a(100, 1);

//求变长数组a的长度，时间复杂度为O(1)；所有容器都有
a.size();

//判断变长数组a是否为空，时间复杂度为O(1)；所有容器都有
a.empty();

//清空变长数组a；.clear()并不是所有容器都有，如队列，就没有.clear( )
a.clear();

//向变长数组a的末尾压入数x
a.push_back(x);

//将变长数组a的末尾元素删除
a.pop_back();

//取变长数组a的第一个元素和最后一个元素
a.front(), a.back();

//取迭代器第一个元素和最后一个元素(指针)
a.begin(), a.end();

//三种遍历方式
for (int i = 0; i < a.size(); ++i) cout << a[i];
//vector <int> :: iterator i;
for (auto i = a.begin(); i != a.end(); ++i) cout << *i;
for (auto x : a) cout << x;

//vector是支持比较运算的，按字典序比较
vector<int> a(4, 3), b(3, 4);
if(a < b)  puts("a < b");    //输出 a < b

//二元组：pair <int, int>、pair <int, string>、pair <int, char>等
//在进行排序时先以first的字典序进行排列，后以second的字典序进行排列
typedef pair <int, int> PII;
PII a;       
vector <PII> a;  //与vector操作类似，但push_back({x, c})，注意{}
//向a中添加一个元素
a = maek_pair(x, y);
a = {x, y};
//取出a中的第一、二个元素
a.first, a.second;

//假设某个东西有两种不同的属性，这时就可以用pair存；若要按某种属性进行排序，就把这个属性存入pair中的first。

string： C++封装好的字符串，可支持多种操作。

string s;

//求字符串的长度
s.size(), s.length();

//判断字符串是否为NULL
s.empty();
//将字符串置为空字符串
s.clear();

//可在字符串末尾添加字符或字符串
s += 'A';
s += 'ABCD';

//取子串substr(下x, y)(重点)，取下标从x开始的长度为y的子串。
s.substr(x, y);

//返回字符串的的首地址
s.C_str();

queue：队列，先进先出，通常用于广度优先（bfs）等算法，可支持插入队尾，弹出队头等操作。

queue <int> q;

//向队尾插入元素x
q.push(x);

//将队头元素弹出
q.pop();

//判断队列是否为空
q.empty();

//取队头、队尾元素
q.front(), q.back();

//但是不能使用clear()，若要清空，可以直接建一个新的队列
q = queue <int> ();

priority_queue：优先队列（实现原理是堆），队列中的元素按照某种顺序规则排序，默认是大根堆，A*算法等是需要用到的。

堆(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树：
(1)若树根结点存在左孩子，则根结点的值(或某个域的值)小于等于左孩子结点的值(或某个域的值)；

​ (2)若树根结点存在右孩子，则根结点的值(或某个域的值)小于等于右孩子结点的值(或某个域的值)；

​ (3)以左、右孩子为根的子树又各是一个堆。

大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。

//定义成小根堆
priority_queue<int, vector<int>,  greater<int>> q;

//向堆中插入一个元素x
q.push(x);

//返回堆顶元素
q.top();

//弹出堆顶元素
q.pop();

stack：栈，与队列类似，区别是先进后出。

stack <int> stk;

//向栈顶插入一个元素
stk.push(x);

//取出栈顶元素
stk.top();

//弹出栈顶元素
stk.pop();

//判断栈是否为空
stk.empty();

deque：双端队列，既可以对队头操作，与可以对队尾操作，但是时间复杂度相对较高；双端队列可支持的操作较多。

deque <int> q;

//取双端队列大小
q.size();

//判断双端队列是否为NULL
q.empty();

//清空双端队列，无需按q = deque <int> ()重新赋值
q.clear();

//返回第一个元素(队头)、最后一个元素(队尾)
q.front(), q.back();

//队尾插入、弹出一个元素
q.push_back(x), q.pop_back();

//队头插入、弹出一个元素
q.push_front(x), q.pop_front();

//也可使用随机寻址 []
//也支持迭代器q.begin()、q.end()

set/multiset，map/multimap，是基于平衡二叉树（红黑树），动态维护有序序列。

set/multiset：集合，集合中的元素是从小至大排好序的。set里面所有的元素都不可重复（集合的互异性），自动去重的功能。multiset里面所有的元素可以重复。

set <int> s;

//支持迭代器，也支持--(前驱)、++(后继)操作，时间复杂度为O(logn)
set <int> iterator :: it;

//插入元素x，时间复杂度为O(1)
s.insert(x);

//删除元素x，若输入是一个数，就删除所有x，时间复杂度为O(k+logn)；若输入一个迭代器，就删除这个迭代器
s.erase(x);

//清空集合
s.clear();

//返回集合元素的个数
s.size();

//返回某一个元素的个数
s.count();

//判断集合是否为空
s.empty();

//查找元素x是否在集合中出现，如果不出现则返回s.end()，否则返回对应的迭代器
s.find(x);

//核心操作: 返回大于等于x的第一个元素（大于等于x的最下的数）的迭代器
lower_bound(x);
//返回大于x的第一个元素的迭代器
upper_bound(x);

map/multimap： STL的一个关联容器，它提供一对一的hash。map/multimap 在插入元素时，内部按照key进行从小到大进行排序。核心为映射key - value，支持随机访问[]。

map <int, int> m;
multiimap <int, int> ms;
pair<int, int> p;
p = make_pair(x, y);

//插入的数是一个pair
m.insert(p);

//删除，输入的参数是pair或者迭代器
m.erase(p);

//查找
m.find(p);

//可以完全像数组一样来使用map，时间复杂度为O(logn)
map<string, int> a;
a["yxc"] = 1;

//也支持lower_bound()，upper_bound()

unordered_set，unordered_map，unordered_multiset，unordered_multimap，哈希表。和上面类似，可以理解为无序版，增删改查的时间复杂度为$O(1)$。但不支持lower_bound()，upper_bound()，迭代器的++，--。

bitset：压位

C++中的bool数据类型是占一个字节，如要开一个1024个bool的数组，就要$1024 B=1KB$的空间，bitset可以在一个字节压8位，则就只要$128B$的空间。bitset使用的内存是正常的bool数组的八分之一。

如要存一个1000010000的bool矩阵，那就需要$10^8 B = 100 MB$的空间，若题目限制空间为$64MB$，则可以使用*bitset进行压位，就只需12MB的空间了。

bitset<10000> s;
//支持各种位运算操作 
~, &, |, ^, 
>> , <<
==, !=
[]
    
s.count();  //返回有多少个1
s.any();   //判断是否至少有一个1
s.none();  //判断是否全为0

s.set();       //把所有位置成1
s.set(k, v);   //把第k位变成v
s.reset();     //把所有位置变成0
s.flip();      //等价于~
s.flip(k);     //把第k位取反