哈希学习笔记

## 前言 ### 理解 将一个内容映射成另一个内容，如： 1. 班级学生学号 2. 打车/外卖 手机尾号 3. 口红色号 ### 简介 将一个内容映射进一个数组（哈希表） 例如 H(X) = X % 11 可以将任意一个数组映射成区间 [1,11) 之间的数 ### 冲突 可能会有数 $\%$ 一个数在同一个位置，我们有两个办法解决 1. 加上一个数，直到一个空的位置（但是查询很慢） 2. 使用 `vector`，制作一个类链表的结构（会被hack，依然很慢） 3. 尽可能分散（设计一个好的哈希函数） ### 常识 Hash(x) = x % p，p 一般为素数（可以用9999971） - p 为容量 - 元素总数 / 容量 = 负载因子（α，阿尔法） ## --- ## 设计函数 ### 定义 定义一个集合 s，s = $\overline {s_1 s_2 \ldots s_n},s_i \in \{'a' \ldots 'z'\}$ 定义一个集合 c，$c_i = s_i - 'a'$ Hash(s) = $ (\displaystyle \sum_{i=1}^n {c_i * base^ {n-1}})$ mod p base 是一个指定的数，一般是一个大于字符集中字符数量（c 的最大值）的素数，比如此处可以取 base = 137 ```cpp for(int i = 0; i < n; i++) res = (res * base + (s[i]-'a')) % p; ``` 双哈希（减少重复概率，更加方便）：选两个 base ### 区间 在处理过程中，用数组 a 记录下计算 Hash(s) 的过程 也就是说，a[i] = Hash($\overline {s_1 s_2 \ldots s_i}$) 定义 $s_{l,r}$ = $\overline {s_l s_{l+1} \ldots s_r}$ 当我们求任意子串 $s_{l,r}$ 的哈希值时，可以快速求出 Hash($s_{l,r}$) = ($a[r] - a[l-1] * base^{r-l+1}$) mod p ```cpp for(int i = 1; i <= n; i++){ res = (res * base + (s[i]-'a')) % p; a[i] = res; } ``` ```cpp int t = a[l-1] * pow(base,r-l+1) % p; return (a[r] - l + p) % p; ``` 关于 `(a[r] - l + p) % p`，是为了解决可能存在负数的问题 ```cpp unordered_map<string,int > hash_table; ``` 一种类似于 map 的数据结构，可以解决大多数哈希表的操作 unordered_map 底层是用哈希表实现的，map 底层是用红黑树实现的 ```cpp if(hash_table.find("qwq") == hash_table.end()) ;//找不到 else ;//找得到 ```