ACM编程Hash及应用.ppt

ACM程序设计 第十四讲 Hash及应用(Hash Application) 导引问题 (HDOJ-1425 sort ) Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。 Input 每组测试数据有两行，第一行有两个数n,m (0n,m1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。 Output 对每组测试数据按从大到小的顺序输出前m大的数。 初步分析 题目特点： 数据量大 数据在一定范围 思考： 常规算法的缺陷？ 是否可以将“数据值”和“存储位置”做某种对应？ 再思考（1425加强版）： 原题描述： 第二行包含n个各不相同，且都处于区间[-500000,500000]的整数 加强版(思考)： 如果整数允许相同怎么处理？ Hash表简介——基本原理 哈希表（散列表）的基本原理： 使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。 Hash表简介——函数构造 无定式，方法很多 最常见的方法：除余法 H(k ) = k mod p  (p一般选取适当大的素数) 常用的经典字符串Hash后面介绍 Hash表简介——冲突 由于不能够保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况： “对于不同的元素关键字，Hash函数计算出了相同的函数值”，这就是产生了所谓的“冲突”。 换句话说，就是Hash函数把不同的元素分在了相同的下标单元。 Hash表简介——冲突解决 方法很多～ 常用方法：线性探测再散列技术 即：当 h(k)位置已经存储有元素的时候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中， S为 数组长度。 特别地，如果将数组扫描一圈仍未发现空单元，则说明哈希表已满，这会带来麻烦，但是，该情况完全可以通过扩大数组范围来避免。 Hash表简介——基本操作 Hash表初始化（0或-1或其它） 哈希函数运算 插入元素（包含冲突解决） 定位（需考虑可能冲突的情况） 总结： Hash函数评价标准： 低冲突率 易于编码 Hash函数特点： 优点：数据存储和查找效率高 （几乎是常数时间） 缺点：消耗较多内存（内存很便宜哪～） Hash主要应用： 查找元素是否属于集合 搜索中的状态表示 Hash-应用基础 第一部分 整数Hash 例1 (HDOJ-1496 Equations) Consider equations having the following form: a*x12+b*x22+c*x32+d*x42=0a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0. It is consider a solution a system (x1,x2,x3,x4) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}. Determine how many solutions satisfy the given equation. HDOJ-1496题目分析 题意简单（类似“百钱买百鸡”问题） 传统方法是（几重循环）？复杂度？ 上述方法如何判断两端相等？（查找？） 可行方案（两重循环＋Hash存储查找） Hash表大小？ HDOJ-1496参考代码（1） // by linle #include stdio.h #include memory.h int pin[101]; int hash[2000003]; int main() { int a,b,c,d; int i,j,sum; for(i=1;i101;i++) pin[i] = i*i; while(scanf(%d %d %d %d,a,b,c,d)!=EOF) { …… } } HDOJ-1496经验之谈 “两层循环最多只可能产生10000个不同的结果,开200W的数组将会浪费很多初始化的时间,所以开小数组+处理冲突会比较好.”——by LaiLi 具体见论坛讨论： /forum/read.php?tid=3276fpage=0toread=page=2 HDOJ-1496参考代码（2） // by laili #inclu