基本概念
- 又称散列表
- 类似离散化（离散化是特殊的哈希表）
- 实现数据的快速查找，将同个要素的值归在一起，查找时先查找要素，再在同要素的集合中找
实现方法（处理数字）
- 先取模，一般要找到规定范围内的，最大质数，并且要离2的整数次幂尽可能远（实现重复程度低）(开放寻址要更长的数组大概2到3倍）
两种实现
一. 拉链法
- 创建一个主数组，满足同条件的在数组上开一条链（LinkedList），为同要素的集合
- 删除
- 一般不会把元素删去，只是做个标记来判断元素是否存在而已
二. 开放寻址法
- 创建一个长数组用来存放各个元素，插入时算出放哪里，如果已经有数了，就往后找，找到第一个没数的存进去
- 查找就是定位到第一个点，有数而不相等就往后找，找到或发现有空位（数不存在）就停下
- 删除
- 打标记，如同拉链法
处理字符串
- 比较特殊
- 对字符串中的字符做映射，映射为数字（如A映射到1，B映射到2…）
- 然后取不同长度的字符串（ 前缀哈希 ），假定其映射值都是 P 进制的数， 将其换算成十进制，再mod上 Q 得到hash值
- 要注意的是：字符不能映射为0，如果为0会出现重复（如A为0，AA也为0）
- 不考虑冲突，将 P 取 131 或 13331， Q 取 2^{64} 时认为没有冲突
得到前缀的Hash值后，可以通过
-
假设 R > L
h[R] - h[L - 1] * P^{R - L + 1}得到 L - R 的hash值（因为一直到L- 1，R和L的字符是一样的，取幂相当于二进制左移运算，让L的hash与R的hash位数相同，前缀相同，后面都是0，相减可以得到L- R的Hash值 -
而对于Q，直接使用unsigned long long （大小为2^{64} ） 相当于取过模了，大的话会溢出差值
-
具体实现