哈希表是存储的是键值对,给出一个键值,哈希表可以在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
分享到:
相关推荐
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
关于哈希表及其查找,为某单位的人名(n=30人)设计一个哈希表,使得平均查找长度,要求完成相应的哈希建表和查表。
哈希表的概念作用及意义,哈希表的构造方法
哈希表的设计与实现——链地址法 ...(2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法解决冲突; (4)查找并显示给定电话号码的记录; (5)查找并显示给定用户名的记录。
C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成...
数据结构中的哈希表查找,代码有注释,理解算法后理解代码非常容易看懂
问题描述:针对某个集体中人名设计哈希表,并完成相应的建表和查表程序。 要求: (1)假设人名为中国人姓名的汉语拼音形式。名称的长度不少于3个字符、不多于10个字符; (2)随机生成人名列表,个数不少于3000个,...
//使用哈希函数:H(k)=3*k MOD length,并采用开放定址法处理冲突。试对输入的关键字序列构造哈希表,哈希表长度为length, //求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。
(4)查找元素:查找哈希表中的元素,分为查找成功和查找不成功。 (5)插入元素:在哈希表中,插入一个元素,分为插入成功和失败。 (6)删除元素:在已有的数据中,删除一个元素。 (7)退出系统:退出程序。 涉及的数据...
任务:针对某个集体(比如你所在的班级)中的“姓名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 要求:假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的...
设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希...
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法...////(2)在哈希表中查找元素 ////(3)在哈希表中插入元素 ////(4)输出哈希表中所有元素 ////(5)建立Hash表
在windows环境下,使用codeblocks进行哈希表的创建、增添、删除、寻找、打印
哈希表查找
1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang). 1.3 假设待填入哈希表的人名有30个,...
用哈希表进行查找的代码,数据结构中创建哈希表,解决冲突等等
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
初始化哈希表 清空哈希表 哈希函数 在哈希表中查找元素 在哈希表中插入一个元素 输出哈希表中所有元素
哈希表的查找。用线性探测在散列的方法建立哈希表,然后对其中的元素进行查找