ACM讲座_hash-lecturex_fanskyer

Hash方法&&一些题目用到的方法Plus个人心得=A.C.T=Fanskyer[e-mail]||BBS站内信件IDfanskyer引入Hash;线性重新散列1hash表的引入2hash表的构造方法3hash方法的用优缺点Hash表就是线性重新散列技术1Hash表的引入考虑下面一个问题[取自一道题的一部分]平面上有N(N很大)个点的集合。使用一种方法来判断给出的一个点是否属于这N个点的集合。Hash引入1方法1For(i=1;i=n;i++)//n=点的数量一个循环如果查到两个点重合。那么就说明找到否则就是没有找到。笨办法O(n)的算法慢~但是数据小或者查找次数很少的时候推荐使用Hash引入2方法2首先对存储点的数组按照先X后Y由大到小排序。之后在进行2分查找使用快速排序算法效率O(n*log(n))2分查找效率O(log(n))在大量查找的情况下效率比第一种高很多当查找量比较小的时候第一种更为合适Hash引入3方法3使用hash表首先对存储点集的表用Hash的方法存储。[处理部分]然后使用Hash方法查询。|Vcontinued…简单介绍Hash（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素。也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。计算hash函数的值计算hash值[有很多种方法]使用(x*P1+y*P2)mod[一个大于n的质数]P1P2是一个比较大的质数得到一个Hash值判断冲突如果没有冲突将hash值填到hash表中判断&解决冲突由于不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，解决方法就是按照索引存放在另外一个地方可以开比较大的数组或者用链表见附图也可以用链表来实现，不过麻烦一些，但是比较保险计算Hash值的技巧重要性哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，增加编程复杂度。因此我们的目标就是尽力避免冲突。计算hash值1[common]除余法：选择一个适当的正整数p，令h(k)=kmodpK如果有2个||更多变量的话通常，可以使用平方来降低可以参考刚才的例子这里，p如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。计算hash值2数字选择法：如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位[比如奇数位]-事情况而定，所组成的新的值作为关键字或者直接作为函数值。特殊情况下用到经验之谈试验表明当元素充满哈希表的90%的时候，效率就已经开始明显下降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大[即取模的那个N值]（由于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况例外），但对太大的数组进行操作也比较费时间，需要找到一个平衡点。通常使它的容量至少是题目最大需求的120%，越大越好效果比较好（这个仅仅是经验，没有严格证明）。Hash的优点Hash接近提供O(N)的效率代价是编程的复杂和消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。但是如果规模较小完全可以使用简单的方法这样出错的可能性更小编程速度快Hash‘sover…Goingtonextpart…特殊方法通常都比较简单没有固定思路可循~通常都需要用到数学技巧比如公式推倒或者一些很巧妙的方法下面拿一道题来说明下问题2100GraveYardPKU题目要求给定1个数求出该数由哪些连续的自然数的平方相加的和。要求输出所有解。问题规模很大10^14次方时间限制很严例如2030=21^2+22^2+23^2+24^22030=25^2+26^2+27^22100GraveYardSolution方法很多但是比较差的方法和好的方法在时间上差别很大。解方程法考虑奇数情况设最中间的数是X2030=(X-1)^2+(x)^2+(x+1)^2展开2030=3*(X^2)+[注意到这里恰好正负抵消]+常数22100GraveYardSolution由此可以直接求解奇数~对于偶数可以考虑用类似的方法首要考虑抵消中间的项2030=(X-1.5)^2+(X-0.5)^2+(X+0.5)^2+(X+1.5)^22030=4*X^2+[中间项全部抵消]+常数带小数…2100GraveYardSolved枚举所有的可能项数值N=10^14由公式(n)(n+1)(2n+1)/(6)==N[求和公式]由此公式可以推知可能项数值[tips]可推知时间复杂度O(N^0.3)Nextto个人心得体会心得体会1Linux&&GCC[GOODSTUFF]建议大家把注意力放在无调试环境[或者尽量减少调试器的使用]编程上而不是linux的使用所以平时建议使用记事本然后放到VC或者仿Linux环境中编译比如cygwin==心得体会2CS现在给大3的开了算法选修课。比较系统可以考虑去听时间1-10周周一周三第2节课地点西阶101心得体会3有目的的编程提高比较大现在大家处于初级阶段巩固各种基础算法可以参考以前的题目分类多编~增熟练度ThankYou提问||休息||StartNextLecture…欢迎Beyonder大B