算法 | 哈希专题总结
哈希专题算是我学的最比较好的专题之一了…感觉。
我把哈希的操作笼统地总结为,你有很多东西,然后你要get一件新的东西,你需要判断有没有这件东西,然后你再拿下它。
而哈希的核心问题就集中在如何判断上面。
先抛开这个问题,我们想另外一件事,哈希可以用来做什么。最简单地,可以用来判重。而依我的最近刷的题加以理解,哈希既可以用来帮助状态记录,也可以用来减少枚举量。
回到开始的问题,怎样判重。我觉得,所有的哈希都无异于设一个集合,往里面及元素罢了。而最简单的方式就是开一个数组(即桶),记录正整数元素出现的有无。而对于其他类型的元素,我们可以用到一些数据结构比如哈希树,甚至STL中的map,set等。
我们来讨论各个方式的优劣。开数组无疑是最快捷的,然而它的缺点也同样明显,对于没有出现过的元素,它仍然要开辟同样大的内存,导致空间开销很吃紧,优点是时间调用很快;对于树,代码实现稍显繁琐,而空间复杂度与出现元素个数成正比,但查询速度略差于数组;下面重点谈下STL_map的优缺点:在等同的情况下,map的时空复杂度无疑是占劣势的,而在时空宽裕的情况下,它的优势就同样显现出来了。Map对未出现的元素并不开辟空间,这也就意味着,在某些情况下,map的空间甚至可以达到更优。而在另一些情况下,map的时间(并不是时间复杂度)也会达到更优,如对string处理的时间优于一般的字符串处理。另外两个显而易见的优点,一是可以做到0冲突,二是实现起来也和数组一样方便。所以,我们并不能一味地排斥STL,选择更优的算法而不是更高端的算法。
话说回来,我们要考虑如何将现有的参量转化为可记录在集合(Hash表)中的元素,暂且列举常见的几大类(其实大都可以用map,下面不再另外进行讨论):
大整数 直接对大素数取余
状态 常见于广搜问题中(如八数码/立体八数码(UVa 1604)),可以把状态转化为大整数
字符串 转化为多进制数
特殊整数_全排列 康拓展开及其逆运算
不难发现,最方便的方法其实都是将元素转化为易于处理的数字。而这带来一个很大的问题,数字一大,数组下标不够用了怎么办呢—-前面已经提到,可以取模。而取了模,不同的元素有可能会具有相同的哈希值,这时候我们就需要一些技术,类如开放寻址和拉链。另外在空间允许的情况下,可以在相同的哈希位值上开放更多的“辅助数组”,记录更多的元素特征以防止冲突。如[POJ2000 Squares],由一条对角线确定一个正方形,两点确定一条直线,可以记录对角线的顶点的坐标来判断冲突。同时也要注意,辅助数组并不是多多益善,最好用尽量少的特征来描述状态,如这题,由|x|,|y|<20000,我们可以把一个顶点的坐标记录在一个int上,把y累在x之后,即 point=“x*100000+y[” (23333,6666)-=“”>233336666],当然要注意负数的处理。这样,可以将四个辅助数组缩减到两个。
可见,哈希的主要难点集中在空间和时间的优劣上,事实上,很多哈希题目在暴力情况下的时间和空间是有冲突的,即两点只能取其一,所以需要一些解决办法。某些情况下,改变枚举方式可达到空间时间更优。简单的如[POJ 1840 Eqs],另外如[CodeVS1306广播操的游戏],使用map,若把所有子串直接push进去直接MLE,而如果每次分别枚举相同长的子串,分别进行哈希,不但可以减少枚举量,每个长度for完后对map进行clear,因为并不会和之后的相同了,还使得空间复杂度降低。
最后再讲一个例子来说明好的枚举也可以有利于哈希:[POJ 1971 Parallelogram Counting].这一题,有种做法枚举3个点确定2条边,由这2条边确定第4的点,再用Hash判断是否存在,但是O(n^3)绝对TLE。后来想到,由平行四边形对角线相互平分,即两条中点相同的线段确定一个平行四边形,只要枚举两点,并记录他们的中点,再Hash搜索这个中点是否出现过就可以进行计数了。
由此看来,哈希只是一种手段,运用到题目中是很考验想法的。哈希处理最大的难处可能并不在与时间,空间可能出现更大的问题。所以,尽量用精炼的信息代表状态,必要时还需保留逆运算。在空间允许的条件下,尽量避免冲突。
以上,最后祝大家Hash Hash 愉快—–