哈希表在查找中凸显的作用

    哈希表是存储的是键值对，给出一个键值，哈希表可以在O(1)的时间复杂度查询。也就是说，它通过把关键码值映射到一个表中的一个位置来记录，加快查找速度。这个函数叫散列函数，存放记录的数组叫散列数组。

    构造查询效率高的散列表基于以下两个方面：构造散列函数的方法和处理冲突的方法。

    构造散列函数，即哈希函数，好的哈希函数，能使冲突和空间降低。一般有直接寻址法，折叠法，除留余数法。在ACM中，见到的字符串hash函数ELFHash。一般采用除留余数法。

    处理冲突的方法也有很多：线性探测，链地址法等等。一般采用链地址法。

    在ACM中只要设计大规模(10,000以上)的查找问题，首先应该想到hash。

    例如POJ2503，给出一串单词+对应的英文，任意给出一个单词，要你查出它的英文。

输入：

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

 

输出：

cat
eh
loops

    输入的有10W对，要是每次都从这10W的数据线性比较O(n)，每次查询一个单词需要20*100000。查询多个单词，显然效率太低。还可以想到用二分，将输入的数据按照单词排序，查询就只需要log2(n)，每次查询一个单词需要20*25。

    还可以将单词hash，哈希函数采用ELFHash，冲突处理采用链表法，这样，对于要查询的单词，先hash，再在hash表中查看，匹配是否相等。只需要O(1)。

从上面的三种算法来看，时间复杂度由O(n)-->O(log2n)-->O(1)，可见二分查找还是很牛B的，但hash更强。

 

    对于POJ2002，给出n个点的坐标（n=1000，-20000<=x,y<=20000），现在要判断这些点能构成多少个正方形。

    首先是如何判断几个点能否构成正方形：从n个点中任意选取两点，求出另外两点的坐标，看另外两点是否在那n个点中。

 

 

 

     枚举每两个点(O(n*n))，根据两点算出另外两点，判断这两点是否在集合中。现在问题转化为：如何判断某点是否在输入的集合中。这个问题与2002类似，这里就不再赘述。

 

    对于POJ3349，每片雪花有6个数组成，在这6个树中，可以从任意一个数开始，顺时针或者逆时针走一遍，认为也是相同的雪花。现在给出n片雪花，判断这n片雪花中是否有相同的两片。n=100,000。

    最简单的就是枚举每两片雪花，判断他们是否相同。时间复杂度为O(n*n)，显然效果不理想。有没有更好的算法呢？

    hash：每读进一片雪花，将雪花hash，判断hash表里是否有相同的hash值，有相同的hash值，从链表中一一取出并判断是否同构，是同构得出结果。然后将该雪花加入到表中，所有雪花读完也没有发现相同的，则得出结果。

 

    对于POJ3274，每头牛有一个特征值n，将n表示成K位二进制形式，第i位上的数为1代表该牛拥有特征i，现在有一排牛，要求出连续的牛，满足这些牛的K个特征个数都相同，求出满足要求的最长的牛序列。n=100,000

    很直接的想法就是枚举所有的牛，求和，判断每个属性是否相等，复杂度为O(n*n)。

    将数据处理：

//对于SAMPLE的数据的处理  
//前导零        000     000  
//7---->111---->111---->000  
//6---->110---->221---->110(*)  
//7---->111---->332---->110  
//2---->010---->342---->120  
//1---->001---->343---->010  
//4---->100---->443---->110(*)  
//2---->010---->453---->120  
//443 - 221 = 222说明在这个范围内3中特色都有相同的个数2  
//每个2进制结果所有位减去他们当中的任意位，上面例子取减去最右边那一位  
//这样将问题转化为判重,，只要找两位他们是相同的并且距离是最远的即可(加*为答案)，用HASH来解决是O(NK) 

   对于POJ2151，也是类似的。

   可见，遇到这类题意简单并且没有好的算法时，用hash往往能达到好的效果。