Hash作为初等数据结构的一些简单优化
Hash常常作为Boolean数组来使用。例如在搜索难以表达的状态的时候（八数码难题就可以用Hash储存康托展开来解决），以及数据范围极大的时候（离散排序之外的另一种离散）来判断是否出现。
事实上Hash也可以作为一种数据结构（虽然它本来就是）来优化程序，像树状数组、线段树一般。
例如下题：
1051 接龙游戏
题目描述 Description
给出了N个单词，已经按长度排好了序。如果某单词i是某单词j的前缀，i->j算一次接龙(两个相同的单词不能算接龙)。
你的任务是：对于输入的单词，找出最长的龙。
输入描述 Input Description
第一行为N(1<=N<=105)。以下N行每行一个单词（由小写组成），已经按长度排序。(每个单词长度<50)
输出描述 Output Description
仅一个数，为最长的龙的长度。
样例输入 Sample Input
5
i
a
int
able
inter
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
1<=N<=10^5
个人解法：
显然不难想到方程：
F[i]=max{F[j]}+1，其中j是i的前缀。
接下来考虑怎么迅速地取到max？
显然根据数据范围，字符长度不大，只有50个。所以如果我们枚举前缀，时间复杂度是可以接受的。
所以此时我们就可以用Hash表储存前缀字符串以及其DP值。之后我们就可以很快地查找到符合要求的状态来更新了。
它速度虽然不够树结构的logn，但是可以处理许多不能由树来储存的东西。所以hash不失为一种很优的数据结构。
代码见：https://liaoy148.lofter.com/post/1da8a74e_c926e09
再例如下题：
1247 排排站
题目描述 Description
FJ的N头奶牛有一些共同之处(1 <= N <= 100,000)。FJ可以将这N头奶牛通过K种特征来归类(1 <= K <= 30)。例如，一些奶牛表现出来的特征1可能是有斑点，特征2可能是较之于PASCAL更喜欢C，等等。
FJ发明了一种简明的描述特征的方法——“特征码”，用一个长度为k的二进制串来表示这头牛的特征表现。例如，一头牛的“特征码”为13，转换为二进制就是1101，代表这头牛具有特征1、3、4 (从右读到左)，但是不表现特征2。总的说来，如果这头奶牛表现特征i，那么我们在他的“特征码”的二进制的第i位就为1。
FJ将奶牛排成了一个1..N的队列，他注意到一种确定的排列方法可以使奶牛们的表现更“平衡”。一个连续的i..j的范围平衡表示为如果K种特征都有同样多的奶牛来表现。FJ想知道他究竟可以排出一个多长的“平衡”队列。请帮助他。
输入描述 Input Description
第一行两个整数n和k
接下来n行每行一个整数
输出描述 Output Description
一个整数表示最大的长度
样例输入 Sample Input
7 3
7
6
7
2
1
4
2
样例输出 Sample Output
4
个人解法：
由数据范围10^5可知，应该是枚举一个端点，之后套一个数据结构迅速查找都左端点。
不难想到，既然是判断一段区间的问题，就应该用到前缀和。
如果一个区间是符合要求的，那么相当于左端点（未考虑边界）各个状态的个数与右端点各个状态的个数增加的相等。由于不清楚到底会加多少，就不难想到转和为差：如果一个区间是符合要求的，那么每两个相邻的特征值的差是不变的。
所以就可以把相邻的特征值的差作为元素，插入到Hash表中。之后我们直接查找最左边的就可以了。
可能会有疑问——这不还是O(n^2)的？万一有很多相同的元素？
由于题目要求，我们只需要找到最左边的端点。所以同一组 元素可以只记录最早出现的一次。这样就可以把查询的复杂度降为地址冲突数了。
代码见：https://liaoy148.lofter.com/post/1da8a74e_c926f54
所以事实上Hash也是一种可以类似于线段树（树状数组）等树结构的数据结构，而不应该只是简简单单的一个Boolean数组。它同样还可以做到一些树结构难以做到的，例如指定方向的更新（如第一题中只能由前缀来更新）。
看来之前自己只会把Hash看成Boolean数组（还就这么对学弟说：Hash就是一个Boolean），简直有愧于于Hash表(～￣▽￣)～。
不过这些还只是Hash作为初等数据结构的简单应用（功能就还只是如树状数组对程序的优化一样，简单地查找可以用来更新的元素），每回想起很蒟蒻的时候，看的杨弋老师的论文，就会想，其实Hash肯定还有更高级的运用的吧。
哪个算法有何尝不是呢？