hash&set&map学习（复习）笔记

# $\text{Hash}$ ## 前言 $\text{Hash}$是一个老算法，主要运用在信息的储存上，可以用来快速查找或匹配 $\text{Hash}$就是通过一个哈希函数$H$，将数据转化成更加方便的数值，这个数值叫做哈希值 在信息学上，$\text{Hash}$的用途主要分为两种： >1.字符串$\text{Hash}$ >2.哈希表 ## 详解 ### 1.字符串$\text{Hash}$ #### 前言 主要用来进行字符串匹配，大部分情况下可以用$KMP$取代，但在主串中每次选出两个子串判断是否匹配，还是要用字符串$\text{Hash}$ #### 流程 介绍一种滚动$\text{Hash}$的技巧，可以使计算子串$\text{Hash}$值的时间复杂度从$O(m)$到$O(1)$ 先找两个合适的互质常数$b$和$h(b<h)$，假设有字符串 $$C=c_1c_2c_3...c_m$$ 那么我们定义哈希函数：$H(C)=(c_1b^{m-1}+c_2b^{m-2}+...+c_mb^0)\text{ mod h}$ 相当于把字符串看成了一个$b$进制数转化为10进制数之后$\text{Hash}$ 这一过程是递推计算的 # $\text{STL}$ ## $\text{Set}$ ## $\text{Map}$