信奥赛C++提高组csp-s之哈表表

信奥赛C++提高组csp-s之哈表表

一、哈希表基本概念

1.1 什么是哈希表

哈希表（Hash Table）是一种高效的数据结构，它通过键值对存储数据，能够在平均O(1)时间内完成插入、删除和查找操作。

1.2 核心思想

将键(key)通过哈希函数转换成数组下标，然后将值存储在该下标对应的位置。

索引=哈希函数(键)%数组大小

1.3 哈希表的组成部分

1. 键(Key)：用于查找的唯一标识
2. 值(Value)：存储的数据
3. 哈希函数(Hash Function)：将键映射为索引
4. 哈希表(数组)：存储数据的容器
5. 冲突解决机制：处理不同键映射到同一位置的情况

二、哈希函数的构造

2.1 除余法（最常用）

// 基本除余法公式hash_value=key%table_size;// 注意：table_size最好取质数，可以减少冲突

2.2 其他常见哈希函数

// 1. 直接定址法：h(key) = a*key + b// 2. 平方取中法：先平方，取中间几位// 3. 折叠法：将key分成几部分，相加// 4. 乘法散列法：h(key) = floor(m * (key*A mod 1))

2.3 字符串哈希

// 常用字符串哈希函数intstring_hash(conststring&s){inthash_val=0;for(charc:s){hash_val=(hash_val*base+c)%mod;}returnhash_val;}

三、解决冲突的方法

3.1 链地址法（拉链法）

将哈希到同一位置的所有元素存储在链表中。

优点：

• 实现简单
• 可存储任意数量元素

3.2 开放定址法

当发生冲突时，寻找下一个空闲位置。

探测方法：

1. 线性探测：(hash(key) + i) % size
2. 平方探测：(hash(key) + i²) % size
3. 双重哈希：(hash1(key) + i*hash2(key)) % size

3.3 再哈希法

使用多个不同的哈希函数，当第一个哈希函数发生冲突时，使用第二个。

四、案例研究（字符串哈希）

题目描述

如题，给定N NN个字符串（第i ii个字符串长度为M i M_iMi​，字符串内包含数字、大小写字母，大小写敏感），请求出N NN个字符串中共有多少个不同的字符串。

输入格式

第一行包含一个整数N NN，为字符串的个数。

接下来N NN行每行包含一个字符串，为所提供的字符串。

输出格式

输出包含一行，包含一个整数，为不同的字符串个数。

输入输出样例 1

输入 1

5 abc aaaa abc abcc 12345

输出 1

4

说明/提示

数据范围

对于30 % 30\%30%的数据：N ≤ 10 N\leq 10N≤10，M i ≈ 6 M_i≈6Mi​≈6，M max ⁡ ≤ 15 M_{\max}\leq 15Mmax​≤15。

对于70 % 70\%70%的数据：N ≤ 1000 N\leq 1000N≤1000，M i ≈ 100 M_i≈100Mi​≈100，M max ⁡ ≤ 150 M_{\max}\leq 150Mmax​≤150。

对于100 % 100\%100%的数据：N ≤ 10000 N\leq 10000N≤10000，M i ≈ 1000 M_i≈1000Mi​≈1000，M max ⁡ ≤ 1500 M_{\max}\leq 1500Mmax​≤1500。

样例说明

样例中第一个字符串a b c \tt{abc}abc和第三个字符串a b c \tt{abc}abc是一样的，所以所提供字符串的集合为{ a a a a , a b c , a b c c , 12345 } \{\tt{aaaa},\tt{abc},\tt{abcc},\tt{12345}\}{aaaa,abc,abcc,12345}，故共计4 44个不同的字符串。

思路分析

1.哈希函数设计

• 采用经典的多项式哈希方法（Rolling Hash）
• 公式：h = h * base + char
• 使用无符号长整型的自然溢出实现模运算，简化代码
• 基数P选择质数131，减少哈希冲突

2.算法流程

1. 读入n个字符串
2. 对每个字符串计算哈希值
3. 将所有哈希值排序
4. 遍历排序后的哈希值，统计不同的个数

代码实现（方法1）

#include<bits/stdc++.h>usingnamespacestd;// 使用无符号长整型存储哈希值，利用其自动溢出特性实现模运算typedefunsignedlonglongULL;constintN=10010;// 最大字符串数量constULL P=131;// 哈希基数（质数），通常选择131或13331ULL a[N];// 存储每个字符串的哈希值// 字符串哈希函数：将字符串转换为64位无符号整数ULLgetHash(string s){ULL h=0;// 初始化哈希值为0for(charc:s){// 遍历字符串中的每个字符h=h*P+c;// 计算哈希值：h = h * base + char}returnh;// 返回哈希值}intn;// 字符串个数intmain(){cin>>n;// 读入字符串个数// 处理每个字符串for(inti=1;i<=n;i++){string s;cin>>s;// 读入一个字符串a[i]=getHash(s);// 计算并存储其哈希值}// 对哈希值数组排序，便于统计不同值sort(a+1,a+n+1);// 统计不同哈希值数量（即不同字符串数量）intcnt=1;// 至少有1个不同的字符串for(inti=2;i<=n;i++){if(a[i]!=a[i-1]){// 如果当前哈希值与上一个不同cnt++;// 计数增加}}cout<<cnt;// 输出结果return0;}

复杂度分析（方法1）

1.时间复杂度

• 计算哈希值：O(ΣMᵢ)，其中Mᵢ是每个字符串的长度
• 排序：O(N log N)，N≤10000
• 总体复杂度可接受

2.空间复杂度

• 存储哈希值：O(N)
• 存储临时字符串：O(最大字符串长度)

注意事项（方法1）

哈希冲突问题

当前代码存在哈希冲突的可能性，即不同的字符串可能产生相同的哈希值。虽然概率很低，但对于严格要求的场景，可以采取以下改进措施：

1. 使用双哈希：用两个不同的基数和模数计算哈希值
2. 使用更大的模数：如取模一个大质数
3. 实际比较字符串：当哈希值相同时，比较原始字符串

数据范围考虑

• N最大10000，每个字符串最长1500
• 哈希值使用ULL（64位），溢出概率低
• 排序10000个ULL值在时间和空间上都可行

代码实现（方法2）

#include<bits/stdc++.h>// 包含所有标准库头文件（竞赛常用，但不推荐生产环境使用）usingnamespacestd;// 使用标准命名空间intn;// 字符串个数unordered_set<string>st;// 使用无序集合存储字符串，自动去重intmain(){cin>>n;// 读入字符串个数for(inti=1;i<=n;i++){string s;// 临时变量存储当前字符串cin>>s;// 读入一个字符串st.insert(s);// 将字符串插入集合（自动去重）}cout<<st.size();// 输出集合大小，即不同字符串的数量return0;}

方法2思路分析：

1.算法思想

• 直接利用C++ STL的unordered_set容器，自动完成字符串去重
• 通过统计集合大小得到不同字符串的数量

2.数据结构选择

• unordered_set：
  • 底层使用哈希表实现
  • 插入和查找的平均时间复杂度为O(1)
  • 自动去重，相同字符串只存储一次
  • 不保证元素的存储顺序

3.时间复杂度分析

• 插入N个字符串：O(N)，每个字符串的插入平均O(1)
• 总时间复杂度：O(N)，其中N为字符串个数
• 实际运行时间受字符串长度影响（字符串比较和哈希计算需要时间）

4.空间复杂度分析

• 存储所有不同的字符串：O(M)，其中M为所有不同字符串的总长度
• 哈希表的额外开销：O(K)，其中K为不同字符串的数量

5.优缺点分析

优点：

1. 代码简洁：只需要10行左右的核心代码
2. 逻辑清晰：直接使用STL，不需要手动实现哈希函数
3. 运行高效：unordered_set的哈希表实现非常高效
4. 正确性保证：STL经过了充分测试，能正确处理哈希冲突

缺点：

1. 内存占用较大：存储了整个字符串内容，而不仅仅是哈希值
2. 理论上可能超时：虽然对于本题数据范围足够，但在极端情况下，如果字符串非常长，哈希计算可能成为瓶颈

五、STL中的哈希表实现

5.1 unordered_map（无序映射）

C++11引入的基于哈希表的关联容器。

#include<bits/stdc++.h>usingnamespacestd;voidtest(){// 创建unordered_mapunordered_map<int,string>m;// 插入元素（三种方式）m[1001]="张三";// 方式1m.insert({1002,"李四"});// 方式2m.insert(make_pair(1003,"王五"));// 方式3// 遍历（无序）cout<<"遍历unordered_map:"<<endl;for(constauto&pair:m){cout<<"学号: "<<pair.first<<", 姓名: "<<pair.second<<endl;}// 查找元素autoit=m.find(1002);if(it!=m.end()){cout<<"找到学号1002: "<<it->second<<endl;}// 统计元素数量cout<<"元素数量: "<<m.size()<<endl;// 检查键是否存在if(m.count(1004)>0){cout<<"学号1004存在"<<endl;}else{cout<<"学号1004不存在"<<endl;}// 删除元素m.erase(1001);cout<<"删除1001后数量: "<<m.size()<<endl;// 清空哈希表m.clear();cout<<"清空后数量: "<<m.size()<<endl;}

5.2 unordered_set（无序集合）

只存储键的哈希表。

#include<bits/stdc++.h>usingnamespacestd;voidtest(){// 创建unordered_setunordered_set<int>s;// 插入元素s.insert(10);s.insert(20);s.insert(30);s.insert(20);// 重复元素，不会被插入// 遍历cout<<"集合元素: ";for(intnum:s){cout<<num<<" ";}cout<<endl;// 查找元素if(s.find(20)!=s.end()){cout<<"元素20在集合中"<<endl;}// 统计元素数量cout<<"集合大小: "<<s.size()<<endl;}

六、信奥赛备考建议

1. 掌握基本概念：理解哈希函数、冲突解决等基本概念
2. 熟练使用STL：unordered_map和unordered_set是信奥赛中的利器
3. 理解时间复杂度：
   • 平均情况：插入、删除、查找都是O(1)
   • 最坏情况：所有元素冲突，退化为O(n)
4. 选择合适的哈希函数：根据题目特点设计合适的哈希函数
5. 注意边界条件：处理哈希表满、空等特殊情况
6. 实践练习：多做题，如统计问题、查找问题、去重问题等

七、常见问题与解答

Q: 为什么哈希表查找快？
A: 哈希表通过哈希函数直接计算出存储位置，避免了线性搜索。

Q: 哈希冲突是什么？如何处理？
A: 不同键映射到同一位置就是哈希冲突。常用处理方法有链地址法和开放定址法。

Q: STL中map和unordered_map有什么区别？
A: map基于红黑树实现，有序，操作复杂度O(log n)；unordered_map基于哈希表，无序，平均复杂度O(1)。

Q: 如何选择哈希表容量？
A: 选择质数作为容量可以减少冲突，同时考虑负载因子（元素数量/容量），通常保持在0.7以下。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、csp高频考点知识详解及案例实践：
  • CSP信奥赛C++之动态规划
  • CSP信奥赛C++之标准模板库STL
  • 信奥赛C++提高组csp-s知识详解及案例实践
• 四、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

---

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}