今天继续更新，昨天的排序大家都用明白了么，今天我们来看看hash表，希望大家能和我一起学习呀。每篇文章后面都有对应的练习题哦，我自己会写题解给大家作为参考，好了不bb了，我们开始把！
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
⏳全文大约阅读时间： 120min(有点长，大家忍一下 ，一定会有蜕变的)
文章目录
☘前言☘
🍘一、相关知识点
🎐1.散列定义与整数散列
🍕2.整数的散列
👻3.字符串hash
🐳课后习题
🍘一、相关知识点
🎐1.散列定义与整数散列
散列(Hash)——将元素通过一个函数转换为整数，使得该整数可以尽量的唯一代表这个元素。
很难理解，但是其实我们会在不知不觉中用到这个知识点，我们先来看一个例子。
给你N个正整数，再给你M个正整数。然后求出这M这个正整数分别在N中出现的次数。
其中M、N中所有元素< 。
输入：7 5 N = [1,2,3,4,5,6,7] M = [1,8,5,4,9]
输出：1 0 1 1 0
最简单的暴力肯定是嵌套循环，每次都去遍历，时间复杂度就达到O(MN)的量级。
我们优化的方式最容易想到的其实是给将N中所有元素映射到数组下标中，然后查表就好了。竞赛中的打表查表也是类似的空间换时间的方式。复杂度就降低到了O(M+N)。
const int maxn = 10010; int hash[maxn] = {0}; //初始化为全不存在 int ans[maxn]; for(int i = 0;i < nsize;++i) hash[N[i]]++; //建立hash表 for(int i = 0;i < msize;++i) ans[i] = hash[M[i]]; //查表输出； rteurn ans;
上面这种方式虽然简单，但是请务必熟稔于心，尽量使用，使用场景非常多。
🍕2.整数的散列
上面的方式对空间的牺牲过大，当量级达到亿万级根本就不可能使用，所以会有一些常见的散列方式。这里介绍几种常见的方式。
*直接定址法(就是上面的那种)
*除留余数法(将元素对某个值取余，然后将元素放入相应的位置。)
*平方取中法(将元素平方取中间的几位作为转换后的对应位置、不是很常用)
最常用的就是除留余数法H ( k e y ) = k e y H(key) = key % mod;H(key)=key
其中mod由于希望能将所有数字尽量分散到hash表内一般选择素数。
很容易发现由于mod的选择会造成不同元素对应同一个转换后的整数，会产生冲突。
一般来说解决冲突有三种方式
*线性探测法(产生冲突后向后推移几个单位寻找空位插入，很容易产生堆积)
*平方探测法(产生冲突后 按照、、…的方式探测)
8拉链法(将产生冲突的元素用链表链接起来，这算是一个链表的运用了。0.0)
👻3.字符串hash
上面讨论的都是一个整数的hash方法，那么给你一个字符串char s[]怎么去做hash呢? 其实就是去做映射，当我们知道元素个数之后可以将元素映射到一个范围内。
比如：字母a~z可以看作0-26，在c中其实只要 c - 'a'就可以做到了。
但是如果是一个字符串怎么办呢？可以类比于我们平常见到的数字比如123其实就是十进制。
那我们字母表只有26个就可以用26进制来表示这个字符串了
比如abc对应的就是( 123 ) 26 (123)_{26}(123) 26 ,xyz对应的就是( ( 24 ) ( 25 ) ( 26 ) ) 26 ((24)(25)(26))_{26}((24)(25)(26)) 26 。
考虑到我们比较适应于10进制 我们可以做个转换 就是x y z = 24 ∗ 2 6 2 + 26 ∗ 26 + 26 ∗ 1 xyz = 24 *26^2+ 26 *26 + 26 *1xyz=24∗26 ^2 +26∗26+26∗1；
总结：如果是字符串，确定相应字母表中元素个数n，然后转换为n进制数来表示。
以一个例子作为结束
给出N个字符串(每个字符串都是三个大写字母),在给出M个查询字串，问是否在N中出现。
示例输入:2 5 N = [ “ABC” , “CBA] M = [“ABC”, “ABB”,“ABD”,“AAA”,CBA”]
示例输出: 1 0 0 0 1
首先有一个对应转换函数👇
int strtoint(char s[]){ //运用hash函数将字符串转整形 int ans = 0; for(int i = 0;s[i] != '\0;++i){ ans = ans * 26 + s[i] - 'A'; } return ans; }
bool hash[Nsize] = {false}; bool ans[Msize] = {false}; for(int i = 0;i < Nsize;++i) hash[strtoint(N[i])] = true;//插入hash表 for(int i = 0;i < Nsize;++i) if(hash[strtoint(M[i])]) ans[i] = true; return ans; }
🐳课后习题
我写完会放题解，大家写完了可以在评论区打卡哟！题解我放评论区吧，这样不用修改文章。
题解：评论区见，置顶没有就是我没写完0.0，大佬们刷完打个卡
大家加油冲！！！！
