哈希游戏,哈希游戏注册,哈希游戏平台,哈希游戏平台注册,哈希游戏注册平台

　　浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 哈尔滨市第三中学 刘翀 哈尔滨市第三中学 刘翀 应用 哈希表 数据结构 关键词 应用 哈希表 数据结构 [关键词] [ ] 摘要 [摘要] [ ] 哈希表是一种高效的数据结构。本文分五个部分：首先提 出了哈 哈希表是一种高效的数据结构。本文分五个部分：首先提 出了哈 希表的优点，其次介绍了它的基础操作， 着从简单的例子中作 了效 希表的优点，其次介绍了它的基础操作， 着从简单的例子中作 了效 率对比，指出其适用范围以及特点，然后通过例子说明了如何在题 目 率对比，指出其适用范围以及特点，然后通过例子说明了如何在题 目 中运用哈希表以及需要注意的问题，最后总结全文。 中运用哈希表以及需要注意的问题，最后总结全文。 正文 [正文] [ ] 1. 引言 1. 引言 哈希表 （ ）的应用近两年才在 中出现，作为一种高效的数据结 哈希表 （ ）的应用近两年才在 中出现，作为一种高效的数据结 Hash Table NOI Hash Table NOI 构，它正在竞赛中发挥着越来越重要的作用。 构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可 以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越 以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越 来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的 来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的 特点之一。 特点之一。 哈希表又叫做散列表，分为 “开散列” 和 “闭散列”。考虑到竞赛时多数人 哈希表又叫做散列表，分为 “开散列” 和 “闭散列”。考虑到竞赛时多数人 通常避免使用动态存储结构，本文中的 “哈希表”仅指 “闭散列”，关于其他方面 通常避免使用动态存储结构，本文中的 “哈希表”仅指 “闭散列”，关于其他方面 读者可参阅其他书籍。 读者可参阅其他书籍。 2. 基础操作 2. 基础操作 2.1基本原理 2.1基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数 第 页 共 页 第 1 页 共 26 页 1 26 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 （哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值 （哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值 （即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简 （即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简 单的理解为，按照关键字为每一个元素 “分类”，然后将这个元素存储在 单的理解为，按照关键字为每一个元素 “分类”，然后将这个元素存储在 相应“类”所对应的地方。 相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极 有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲 有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲 突”，换句话说，就是把不同的元素分在了相同的 “类”之中。后面我们 突”，换句话说，就是把不同的元素分在了相同的 “类”之中。后面我们 将看到一种解决“冲突”的简便做法。 将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 2.2 函数构造 h(k) k 构造函数的常用方法 （下面为了叙述简洁，设 h(k) 表示关键字为 k 构造函数的常用方法 （下面为了叙述简洁，设 表示关键字为 的元素所对应的函数值）： 的元素所对应的函数值）： 除余法： a) 除余法： a) p h(k ) = k mod p 选择一个适当的正整数 p ，令 h(k ) = k mod p 选择一个适当的正整数 ，令 p 这里， p 如果选取的是比较大的素数，效果比较好。而 这里， 如果选取的是比较大的素数，效果比较好。而 且此法非常容易实现，因此是最常用的方法。 且此法非常容易实现，因此是最常用的方法。 数字选择法： b) 数字选择法： b) 如果关键字的位数比较多，超过长整型范围而无法直接运 如果关键字的位数比较多，超过长整型范围而无法直接运 算，可以选择其中数字分布比较均匀的若干位，所组成的新的 算，可以选择其中数字分布比较均匀的若干位，所组成的新的 值作为关键字或者直接作为函数值。 值作为关键字或者直接作为函数值。 2.3 冲突处理 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数 S h(k) (h(k)+i) mod S , 为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , 为 ，则当 已经存储了元素的时候，依次探查 i=1,2,3 i=1,2,3…… ，直到找到空的存储单元为止 （或者从头到尾扫描一圈仍未发 …… ，直到找到空的存储单元为止 （或者从头到尾扫描一圈仍未发 现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大 现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大 数组范围避免的）。 数组范围避免的）。 2.4 支持运算 2.4 支持运算 (makenull) 哈希表支持的运算主要有：初始化(makenull) 、哈希函数值的运算 哈希表支持的运算主要有：初始化 、哈希函数值的运算 (h(x)) (insert) (member) (h(x)) 、插入元素(insert) 、查找元素(member) 。 、插入元素 、查找元素 。 x A 设插入的元素的关键字为 x ，A 为存储的数组。 设插入的元素的关键字为 ， 为存储的数组。 初始化比较容易，例如 初始化比较容易，例如 const empty=maxlongint; // const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 用非常大的整数代表这个位置没有存储元素 p=9997; // p=9997; // 表的大小 表的大小 procedure makenull; procedure makenull; var i:integer; var i:integer; begin begin for i:=0 to p-1 do for i:=0 to p-1 do A[i]:=empty; A[i]:=empty; End; End; 2 26 第 2 页 共 26 页 第 页 共 页 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： function h(x:longint):Integer; function h(x:longint):Integer; begin begin h:= x m d p; h:= x m d p; end; end; 我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元 我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元 素若存在，它应该存储在什么位置，因此加入一个定位的函数 素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate locate function locate(x:longint):integer; function locate(x:longint):integer; var orig,i:integer; var orig,i:integer; begin begin orig:=h(x); orig:=h(x); i:=0; i:=0; while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do while (iS)and(A[(orig+i)mod S]x)and(A[(orig+i)mod S]empty) do inc(i); inc(i); // // 当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元 // //素存储的单元，要么表已经满了 素存储的单元，要么表已经满了 locate:=(orig+i) mod S; locate:=(orig+i) mod S; end; end; 插入元素 插入元素 pr cedure insert(x:longint); pr cedure insert(x:longint); var posi:integer; var posi:integer; begin begin p si:=l cate(x); // p si:=l cate(x); // 定位函数的返回值 定位函数的返回值 if A[posi]=empty then A[posi]:=x if A[posi]=empty then A[posi]:=x else err r; //err r else err r; //err r 即为发生了错误，当然这是可以避免的 即为发生了错误，当然这是可以避免的 end; end; 查找元素是否已经在表中 查找元素是否已经在表中 pr cedure member(x:longint):b lean; pr cedure member(x:longint):b lean; var posi:integer; var posi:integer; begin begin p si:=l cate(x); p si:=l cate(x); if A[posi]=x then member:=true if A[posi]=x then member:=true else member:=false; else member:=false; end; end; 这些就是建立在哈希表上的常用基本运算。 这些就是建立在哈希表上的常用基本运算。 下文提到的所有程序都能在附录中找到。 下文提到的所有程序都能在附录中找到。 3. 效率对比 3. 效率对比 第 页 共 页 第 3 页 共 26 页 3 26 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 3.1 简单的例子与实验 3.1 简单的例子与实验 下面是一个比较简单的例子： 下面是一个比较简单的例子： =================================================================== =================================================================== 集合 集合 ( Subset ) ( Subset ) 问题描述： 问题描述： 9 A B x 9 A B x ≤ ≤ ， 给定两个集合 、 ，集合内的任一元素 满足 ≤ ≤ ，并且每个集合的元素个数 给定两个集合 、 ，集合内的任一元素 满足 1 x 10 并且每个集合的元素个数 1 x 10 4 不大于 4 不大于 A B B A A B B A 个。我们希望求出 、 之间的关系。只需确定在 中但是不在 中的元素的个 10 个。我们希望求出 、 之间的关系。只需确定在 中但是不在 中的元素的个 10 数即可。 数即可。 OIBH NOIP 2002 # 1 OIBH NOIP 2002 # 1 这个题目是根据 模拟赛 的第一题改编的。 这个题目是根据 模拟赛 的第一题改编的。 A B 我们先不管A 与 B 的具体关系如何，注意到这个问题的本质 分析：我们先不管 与 的具体关系如何，注意到这个问题的本质 分析： A B A 就是对于给定的集合A ，确定B 中的元素是否在 A 中。所以，我们使用 就是对于给定的集合 ，确定 中的元素是否在 中。所以，我们使用 哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了 哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了 H(x) = x mod 15889; 原题的数据规模， H(x) = x mod 15889; 原题的数据规模， + 当然本题可以利用别的方法解决，所以选取了速度最快的快速排序+ 当然本题可以利用别的方法解决，所以选取了速度最快的快速排序 二分查找，让这两种方法作效率对比。 二分查找，让这两种方法作效率对比。 A=B 50 我们假定 A=B ，对于随机生成的数据，计算程序重复运行 50 次 我们假定 ，对于随机生成的数据，计算程序重复运行 次 所用时间。 所用时间。 对比表格如下： 对比表格如下： s c + (sec) s c + (sec) 哈希表（ ） 快速排序 二分查找 哈希表（ ） 快速排序 二分查找 O(N) ( 复杂度 O(N) (只有忽略了冲突才是这 复杂度 只有忽略了冲突才是这 O(N log N+ N) = O(N log N) O(N log N+ N) = O(N log N) 个结果。当然实际情况会比这 个结果。当然实际情况会比这 个大，但是重复的几率与哈希 个大，但是重复的几率与哈希 ) 函数有关，不容易估计) 函数有关，不容易估计 测试数据规模 —— —— 测试数据规模 —— —— 500 0.957 0.578 500 0.957 0.578 1000 1.10 1 0.825 1000 1.10 1 0.825 2500 1.476 1.565 2500 1.476 1.565 5000 2.145 2.820 5000 2.145 2.820 7500 2.905 4.203 7500 2.905 4.203 10000 3.740 5.579 10000 3.740 5.579 13500 7.775 7.753 13500 7.775 7.753 15000 27.550 8.673 15000 27.550 8.673 Cel ron566 TP 在 Cel ron566 下用 TP 测试，为了使时间的差距明显， 对于数据的说明： 对于数据的说明：在 下用 测试，为了使时间的差距明显， 50 P= 15889 0..15888 让程序重复运了行 50 次。同时哈希表中的P= 15889 ，下标范围 0..15888 。由 让程序重复运了行 次。同时哈希表中的 ，下标范围 。由 于快速排序不稳定，因此使用了随机数据。 于快速排序不稳定，因此使用了随机数据。 3．2 对试验结果的分析： 3．2 对试验结果的分析： 4 26 第 4 页 共 26 页 第 页 共 页 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设 注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设 P . 哈希表的大小为 P . 哈希表的大小为 a 10% * P a 10% * P 首先，当规模比较小的时候 （大约为 ，这个数据仅仅是通 首先，当规模比较小的时候 （大约为 ，这个数据仅仅是通 过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。 过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。 O(1) 这是由于，虽然每次计算哈希函数用 O(1) 的时间，但是这个系数比较大。 这是由于，虽然每次计算哈希函数用 的时间，但是这个系数比较大。 H(x)=x mod 15589 例如这道题的 H(x)=x mod 15589 ，通过与做同样次数的加法相比较，测 例如这道题的 ，通过与做同样次数的加法相比较，测 12 mod 试发现系数 12 ，因为 mod 运算本身与快速排序的比较大小和交换元 试发现系数 ，因为 运算本身与快速排序的比较大小和交换元 O(N) 素运算相比，比较费时间。所以规模小的时候，O(N) （忽略冲突）的算法 素运算相比，比较费时间。所以规模小的时候， （忽略冲突）的算法 O(NlogN) 反而不如 O(NlogN) 。这一点在更复杂的哈希函数上会体现的更明显，因 反而不如 。这一点在更复杂的哈希函数上会体现的更明显，因 为更复杂的函数系数会更大。 为更复杂的函数系数会更大。 15%*P a 85%*P 15%*P a 85%*P 其次，当规模稍大 （大约为 ） 的时候，很明显 其次，当规模稍大 （大约为 ） 的时候，很明显 哈希表的效率高。这是因为冲突的次数较少。 哈希表的效率高。这是因为冲突的次数较少。 90%*P a P 90%*P a P 再次，当规模再大 （大约为 ）的时候，哈希表的效 再次，当规模再大 （大约为 ）的时候，哈希表的效 率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得 率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得 不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统 不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统 13500 150000 计，当规模为 13500 的时候，为了找空位置，线 计，当规模为 的时候，为了找空位置，线 次运算；而当规模为 15000 的时候，平均竟然高达 2000000 次运算，某 次运算；而当规模为 的时候，平均竟然高达 次运算，某 4265833 些数据甚至能达到 4265833 次。显然浪费这么多次运算来解决冲突是不合 些数据甚至能达到 次。显然浪费这么多次运算来解决冲突是不合 算的，解决这个问题可以扩大表的规模，或者使用 “开散列”（尽管它是 算的，解决这个问题可以扩大表的规模，或者使用 “开散列”（尽管它是 动态数据结构）。然而需要指出的是，冲突是不可避免的。 动态数据结构）。然而需要指出的是，冲突是不可避免的。 初步结论： 初步结论： 当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现 当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现 高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点 高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点 可以充分体现。我们可以从图像直观的观察到这一点。 可以充分体现。我们可以从图像直观的观察到这一点。 时 时 间 间 效 效 率 率 其他方法 其他方法 哈希表 哈希表 数据规模 数据规模 90% 试验表明当元素充满哈希表的 90% 的时候，效率就已经开始明显下 试验表明当元素充满哈希表的 的时候，效率就已经开始明显下 降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大 （由 降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大 （由 5 26 第 5 页 共 26 页 第 页 共 页 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况 于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况 例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。 例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。 120% 通常使它的容量至少是题目最大需求的 120% ，效果比较好 （这个仅仅是 通常使它的容量至少是题目最大需求的 ，效果比较好 （这个仅仅是 经验，没有严格证明）。 经验，没有严格证明）。 4. 应用举例 4. 应用举例 应用的简单原则 4.1 应用的简单原则 4.1 什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问： 什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问： “某个元素是否在已知集合中？”，也就是需要高效的数据存储和查找， “某个元素是否在已知集合中？”，也就是需要高效的数据存储和查找， 则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意 则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意 的是什么呢？ 的是什么呢？ 哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突 哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突 的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因 的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因 此我们的目标就是尽力避免冲突。前面提到，在使用“除余法”的时候， 此我们的目标就是尽力避免冲突。前面提到，在使用“除余法”的时候， h(k)=k mod p p h(k)=k mod p p ， 最好是一个大素数。这就是为了尽力避免冲突。为什么 ， 最好是一个大素数。这就是为了尽力避免冲突。为什么 p=1000 呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数 呢？假设 ，则哈希函数分类的标准实际上就变成了按照末三位数 1000 p 分类，这样最多 1000 类，冲突会很多。一般地说，如果 p 的约数越多， 分类，这样最多 类，冲突会很多。一般地说，如果 的约数越多， 那么冲突的几率就越大。 那么冲突的几率就越大。 p q 简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 简单的证明：假设 是一个有较多约数的数，同时在数据中存在 gcd(p,q)=d 1 p=a*d , q=b*d, q mod p= q – p* [q di p] gcd(p,q)=d 1 p=a*d , q=b*d, q mod p= q – p* [q di p] 满足 ，即有 则有 满足 ，即有 则有 =q – p*[b div a] . [b div a ] [0 b] =q – p*[b div a] . [b div a ] [0 b] ① 其中 的取值范围是不会超过 ， 的正整 ① 其中 的取值范围是不会超过 ， 的正整 [b di a] b+1 p 数。也就是说， [b di a] 的值只有 b+1 种可能，而 p 是一个预先确定 数。也就是说， 的值只有 种可能，而 是一个预先确定 b+1 mod 的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然 mod 运算之后 的数。因此 ① 式的值就只有 种可能了。这样，虽然 运算之后 [0 p-1] [0 p-1] 的余数仍然在 ， 内，但是它的取值仅限于 ① 可能取到的那些值。 的余数仍然在 ， 内，但是它的取值仅限于 ① 可能取到的那些值。 p 也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这 也就是说余数的分布变得不均匀了。容易看出， 的约数越多，发生这 种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最 种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最 少的，因此我们选用大素数。记住“素数是我们的得力助手”。 少的，因此我们选用大素数。记住“素数是我们的得力助手”。 另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个 另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个 几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样 几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样 的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设 的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设 计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数 计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数 还需要易于编码，即易于实现。 还需要易于编码，即易于实现。 综上所述，设计一个好的哈希函数是很关键的。而 “好”的标准，就 综上所述，设计一个好的哈希函数是很关键的。而 “好”的标准，就 是较低的冲突率和易于实现。 是较低的冲突率和易于实现。 另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变 另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变 的。有的时候，需要按照题 目的要求对哈希表的结构作一些改进。往往一 的。有的时候，需要按照题 目的要求对哈希表的结构作一些改进。往往一 些简单的改进就可以带来巨大的方便。 些简单的改进就可以带来巨大的方便。 这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具 这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具 体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现 体问题具体分析才行。下面，我们看几个例子，看看这些原则是如何体现 的。 的。 6 26 第 6 页 共 26 页 第 页 共 页 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 有关字符串的例子 4.2 有关字符串的例子 4.2 我们经常会遇到处理字符串的问题，下面我们来看这个例子： 我们经常会遇到处理字符串的问题，下面我们来看这个例子： ====================================================================== ====================================================================== 找名字 找名字 问题描述： 问题描述： 给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编 给定一个全部由字符串组成的字典，字符串全部由大写字母构成。其中为每个字符串编 n n 写密码，编写的方式是对于 n 位字符串，给定一个 n 位数，大写字母与数字的对应方式按 写密码，编写的方式是对于 位字符串，给定一个 位数，大写字母与数字的对应方式按 照电话键盘的方式： 照电线: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S 4: G,H,I 7: P,R,S 1 12 1 12 题目给出一个 —— 位的数，找出在字典中出现且密码是这个数的所有字符串。字典 题目给出一个 —— 位的数，找出在字典中出现且密码是这个数的所有字符串。字典 8000 中字符串的个数不超过 8000 。 中字符串的个数不超过 。 USACO Training Ga e 1.2.4 USACO Training Ga e 1.2.4 这个是 的一道题。 这个是 的一道题。 看懂题 目之后，对于给定的编码，只需要一个回溯的过程，所 分析：看懂题 目之后，对于给定的编码，只需要一个回溯的过程，所 分析： 有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在 有可能的原字符串都可以被列举出来，剩下的就是检查这个字符串是否在 给定的字典中了。所以这个问题需要的还是 “某个元素是否在已知集合 给定的字典中了。所以这个问题需要的还是 “某个元素是否在已知集合 ASCII 中？”由于给出的 “姓名”都是字符串，因此我们可以利用字符的 ASCII 中？”由于给出的 “姓名”都是字符串，因此我们可以利用字符的 码。那么，如何设计这个哈希函数呢？注意到题 目给出的字典中，最多能 码。那么，如何设计这个哈希函数呢？注意到题 目给出的字典中，最多能 5000 ASCII 26 有 5000 个不同元素，而一个字符的 ASCII 码只能有 26 种不同的取值， 有 个不同元素，而一个字符的 码只能有 种不同的取值， 3 26^3 5000 26^2 5000 3 26^3 5000 26^2 5000 因此至少需要用在 个位置上的字符 （ ，但是 ）， 因此至少需要用在 个位置上的字符 （ ，但是 ）， 3 1 12 3 1 12 于是我们就选取 个位置上的字符。由于给定的字符串的长度从 —— 于是我们就选取 个位置上的字符。由于给定的字符串的长度从 —— 1 2 都有可能，为了容易实现，选取最开始的 1 个字符，和最末尾的 2 个字符。 都有可能，为了容易实现，选取最开始的 个字符，和最末尾的 个字符。 3 27 3 让这 3 个字符组成 27 进制的 3 位数，则这个数的值就是这个字符串的编 让这 个字符组成 进制的 位数，则这个数的值就是这个字符串的编 码。这样哈希函数就设计出来了！ 码。这样哈希函数就设计出来了！ 1 不过，由于可能出现只有 1 位的字符串，在写函数代码的时候需要 不过，由于可能出现只有 位的字符串，在写函数代码的时候需要 13883 特殊考虑；大素数选取 13883 。 特殊考虑；大素数选取 。 这个函数是这样的： 这个函数是这样的： function hash(s:string):integer; function hash(s:string):integer; var i,tmp:longint; var i,tmp:longint; beg n beg n tmp:=0; { 27 } tmp:=0; { 27 } 用来记录 进制数的值 用来记录 进制数的值 f length(s)1 then beg n f length(s)1 then beg n tmp:=tmp*27+ord(s[1])-64; tmp:=tmp*27+ord(s[1])-64; for :=1 downto 0 do for :=1 downto 0 do tmp:=tmp*27+ord(s[length(s)-i])-64; { } tmp:=tmp*27+ord(s[length(s)-i])-64; {取第一位和后两位} 取第一位和后两位 end end else for :=1 to 3 do else for :=1 to 3 do tmp:=tmp*27+ord(s[1])-64;{ 1 } tmp:=tmp*27+ord(s[1])-64;{ 当长度为 1 的时候特殊处理} 当长度为 的时候特殊处理 hash:=tmp mod 13883; hash:=tmp mod 13883; end; end; 7 26 第 7 页 共 26 页 第 页 共 页 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似 “平 值得指出的是，本题给出的字符串大都没有什么规律，用哈希表可以做到近似 “平 均”，但是对于大多数情况，字符串是有规律的 （例如英文单词），这个时候用哈希表反 均”，但是对于大多数情况，字符串是有规律的 （例如英文单词），这个时候用哈希表反 con 而不好（例如英语中有很多以 con 开头的单词），通常用检索树解决这样的查找问题。 而不好（例如英语中有很多以 开头的单词），通常用检索树解决这样的查找问题。 4.3 4.3 在广度优先搜索中应用的例子 在广度优先搜索中应用的例子 在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先 在广度优先搜索中，一个通用而且有效的剪枝就是在拓展节点之前先 判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。 判重。而判重的本质也是数据的存储与查找，因此哈希表大有用武之地。 来看下面的例子： 来看下面的例子： 转花盆 转花盆 题意描述 题意描述: : 6 给定两个正 6 边形的花坛，要求求出从第一个变化到第二个的最小操作次数以 给定两个正 边形的花坛，要求求出从第一个变化到第二个的最小操作次数以 6 及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的 6 盆花按照顺时针 及操作方式。一次操作是：选定不在边上的一盆花，将这盆花周围的 盆花按照顺时针 3 或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过 3 或者逆时针的顺序依次移动一个单位。限定一个花坛里摆放的不同种类的花不超过 2 2 种，对于任意两种花，数量多的花的盆数至少是数量少的花的 倍 种，对于任意两种花，数量多的花的盆数至少是数量少的花的 倍 SGOI-8 这是 SGOI-8 的一道题 这是 的一道题 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。 分析： 首先确定本题可以用广度优先搜索处理，然后来看问题的规模。 分析： 6 19 正 6 边形共有 19 个格子可以用来放花，而且根据最后一句限定条件，至 正 边形共有 个格子可以用来放花，而且根据最后一句限定条件，至 C(2,19) * C(5,17) = 1058148 C(2,19) * C(5,17) = 1058148 多只能存在

　　2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。

　　3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。

　　4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

　　四川省成都市2018-2019学年高一上学期期末调研考试英语试卷.pdf

　　2018-2019学年四川省蓉城联盟高二上学期期末联考英语试卷.pdf

　　根据湖北省中小学教师信息技术应用能力提升工程培训项目实施方案要求.pdf

　　电大小学语文教学研究-0007期末机考复习资料以及2020部编版小学道德与法.pdf

　　河南省郑州经济技术开发区第四中学2023-2024学年八年级上学期第一次月考物理试卷.docx

　　河南省郑州实验外国语中学2024-2025学年八年级上学期第一次月考物理试卷(无答案).docx

　　河南省实验中学2024-2025学年八年级上学期第一次月考物理试卷及答案.pdf

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者