`
yzmduncan
  • 浏览: 325972 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

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

阅读更多

    哈希表是存储的是键值对,给出一个键值,哈希表可以在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往往能达到好的效果。

 

 

  • 大小: 15.8 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics