哈希表又称为散列表,一般是由Hash函数(散列函数)与链表结构共同实现。与离散化的思想类似,当我们要对若干复杂信息进行统计的时候,可以用Hash函数将这些复杂的信息映射到一个容易维护的值域内。因为值域变简单、范围变小,有可能造成两个不同的原始信息被Hash函数映射为相同的值,所以我们要处理这种冲突情况。
拉链法
拉链法也称开散列法(open hashing)。
拉链法是在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方,只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是1...M ,哈希表的大小为 N,那么一次插入/查询需要进行期望 次比较。
输入样例:
5 I 1 I 2 I 3 Q 2 Q 5输出样例:
Yes No
- #include
- #include
-
- 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;
- e[idx] = x;
- ne[idx] = h[k];
- h[k] = idx ++ ;
- }
-
- bool find(int x)
- {
- int k = (x % N + N) % N;
- for(int i = h[k]; ~i; i = ne[i])
- if(e[i] == x)
- return true;
- return false;
- }
-
- int main()
- {
- int n;
- cin >> n;
-
- memset(h, -1, sizeof h);
-
- while(n -- )
- {
- char op[2];
- int x;
- scanf("%s%d", op, &x);
-
- if(*op == 'I') insert(x);
- else
- {
- if(find(x)) puts("Yes");
- else puts("No");
- }
- }
-
- return 0;
- }
闭散列方法把所有记录直接存储在散列表中,如果发生冲突则根据某种方式继续进行探查。
比如线性探查法:如果在 d
处发生冲突,就依次检查 d + 1
,d + 2
……
- #include
- #include
-
- 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)
- {
- 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;
- }
字符串Hash函数可以把一个任意长度的字符串映射成非负整数,并且其冲突概率几乎为0.
取一固定值P,把字符串看做P进制数,并分配一个大于0的数值,代表每种字符。
一般来说,我们分配的数值都小于P,例如,对于小写字母构成的字符串,可以令
。取一固定值M,求出该P进制数对M的余数,作为该字符串的哈希值。
一般来说,我们取 或 ,此时Hash值产生冲突的概率极低,只要Hash值相同,我们就可以认为原字符串时相等的。通常我们取,即直接使用 unsigned long long 类型存储这个Hash值,在计算时不处理算术溢出问题,产生溢出时相当于自动对 取模,只要可以避免低效的取模(mod)运算。
对字符串的各种操作,都可以直接对P进制数进行算术运算反映到Hash值上。如果我们已知字符串 的Hash值为 ,那么在 S 后面添加一个字符 c 构成的新字符串 S + c 的Hash值就是 。其中乘P就相当于把P进制下的左移运算,value[c] 就是我们为c选定的代表数值。
输入样例:
8 3 aabbaabb 1 3 5 7 1 3 6 8 1 2 1 2输出样例:
Yes No Yes
- #include
-
- using namespace std;
-
- typedef unsigned long long ULL;
-
- const int N = 100010, P = 131;
-
- int n, m;
- char str[N];
- int 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;
- h[i] = h[i - 1] * P + str[i];
- }
-
- while(m -- )
- {
- int l1, r1, l2, r2;
- cin >> l1 >> r1 >> l2 >> r2;
-
- if(get(l1, r1) == get(l2, r2)) puts("Yes");
- else puts("No");
- }
-
- return 0;
- }
vector 变长数组,倍增的思想
string 字符串,substr(), c_str()
queue 队列 push(), top(), pop()
priority_queue 优先队列 push(), top(), pop()
stack 栈 push(), top(), pop()
deque 双端队列
set, map, multiset, multimap 基于平衡二叉树(红黑树),动态维护有序序列
unordered_map,unordered_set,unordered_multiset,unordered_multimap 哈希表
vector 可以理解为变长数组,它的内部实现基于倍增思想。
vector 支持随机访问,可以使用 [ ] 进行访问
#include vector<int> a; vector<int> b[233] struct rec{...} vectorc; // 自定义的结构体也可以保存在vector中 sizz/empty
size 返回vector的实际长度(包含元素个数),empty返回一个bool变量,表明vector是否为空。时间复杂度是 O(1)
所有的STL容器都支持这个操作,含义也都相同。
clear
清空容器
迭代器/begin/end
迭代器就像是STL容器的指针,可以用 * 解引用
vector<int>::iterator it; for(int i = 0; i < a.size(); i ++ ) cout << a[i] << endl; for(vector<int>::iterator it = a.begin(); it != a.end(); it ++ ) cout << *it << endl;插入删除
a.push_back(x) 把元素 x 插入到vector a 的尾部
a.pop_back 删除vector a 的最后一个元素
包括循环队列 queue 和优先队列 priority_queue
循环队列 queue
push 入队(从队尾) O(1) pop 出队(从队头) O(1) front 队头元素 O(1) back 队尾元素 O(1) 优先队列 priority_queue
push 把元素插入堆 O(logn) pop 删除堆顶元素 O(logn) top 查询堆顶元素(最大值) O(1) priority_queue实现小根堆
① 将要插入元素的相反数放入堆中,取出的时候再变回来
② 自定义结构体类型
重载小于号,但是当做“大于号”来编写函数
struct rec {int id; double value;} bool operator <(const rec& a, const rec& b) { return a.value > b.value; }
包括 set 和 multiset 两种容器,分别是“有序集合”和“有序多重集合”,
即前者的元素不能重复,后者可以包含若干个相等的元素。
内部实现是一棵红黑树。
s.insert(x)
s.insert(x) 是把一个元素插入到 s 中,时间复杂度是O(logn)
multiset<int> s; for(int i = 1; i <= n; i ++ ) s.insert(a[i]); for(multiset<int>::iterator it = s.begin(); it != s.end(); it ++ ) cout << *it << endl;s.find(x)
s,find(x)是在集合s中查找等于 x 的元素,时间复杂度是O(logn)
若存在则返回指向该元素的迭代器,若不存在则返回 s.end()
s.erase()
从multiset 中删除多个相同的数
if((it = s.find(x)) != s.end()) s.erase(it);
lower_bound/upper_bound
s.lower_bound(x) 查找 >= x 的元素中最小的一个,返回指向该元素的迭代器
s.upper_bound(x) 查找 > x 的元素中最小的一个,返回指向该元素迭代器
s.count(x)
返回s的集合中等于 x 的元素个数