【免费】全国信息学竞赛算法研究论文合集资源-CSDN文库

信息学竞赛

论文

需积分: 0 62 浏览量 2011-09-18 09:58:20 上传评论收藏 8.09MB PDF 举报

资源推荐

资源详情

资源评论

全国信息学竞赛算法研究论文合集

Hash 函数的设计优化 ....................................................................................................................................... 4

Hash 在信息学竞赛中的一类应用 ........................................................................................................... 14

部分贪心思想在信息学竞赛中的应用 .................................................................................................. 25

从一类单调性问题看算法的优化 ............................................................................................................ 33

计算几何中的二分思想 ................................................................................................................................. 43

论程序的调试技巧 ............................................................................................................................................ 51

欧拉回路性质与应用探究 ............................................................................................................................ 69

平衡规划 ................................................................................................................................................................. 93

浅谈“调整”思想在信息学竞赛中的应用 ..................................................................................... 117

美，无处不在 ..................................................................................................................................................... 127

浅谈二分策略的应用 ..................................................................................................................................... 141

浅谈基于分层思想的网络流算法 .......................................................................................................... 148

浅谈类比思想 ..................................................................................................................................................... 172

浅谈数据的合理组织 ..................................................................................................................................... 187

贪婪的动态规划 ............................................................................................................................................... 201

浅谈信息学竞赛中的区间问题................................................................................................................ 214

浅谈信息学中状态的合理设计与应用 ................................................................................................ 256

浅析倍增思想在信息学竞赛中的应用 ................................................................................................ 275

浅析非完美算法在信息学竞赛中的应用 .......................................................................................... 302

浅析信息学中的“分”与“合” .......................................................................................................... 317

数据结构的提炼与压缩 ............................................................................................................................... 331

Hash 函数的设计优化

天津南开中学李羽修

【摘要】

Hash 是一种在信息学竞赛中经常用到的数据结构。一个好的 Hash 函数可以很大程度上提高程序的整体时

间效率和空间效率。本文对面向各种不同标本（关键值）的 Hash 函数进行讨论，并对多种常用的 Hash 函数进

行了分析和总结。

【关键字】

Hash 函数，字符串，整数，实数，排列组合

【正文】

对于一个 Hash 函数，评价其优劣的标准应为随机性，即对任意一组标本，进入 Hash 表每一个单元（cell）

之概率的平均程度，因为这个概率越平均，数据在表中的分布就越平均，表的空间利用率就越高。由于在竞赛

中，标本的性质是无法预知的，因此数学推理将受到很大限制。我们用实验的方法研究这个随机性。

一、整数的 Hash 函数

常用的方法有三种：直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下

假定我们的关键字是，Hash 表的容量是

，Hash 函数为

 

。

1．直接取余法

我们用关键字

除以

，取余数作为在 Hash 表中的位置。函数表达式可以写成：

 

Mkkh mod

。

例如，表容量

12M

，关键值

100k

，那么

 

4kh

。该方法的好处是实现容易且速度快，是很常用的一

种方法。但是如果

选择的不好而偏偏标本又很特殊，那么数据在 Hash 中很容易扎堆而影响效率。

对于

H H H H H H

H H H H

H H H H H

H H H H

H H H H H

H H H H

H H H H H

P P P

P P

的选择，在经验上，我们一般选择不太接近

的一个素数；如果关键字的值域较小，我们一般在

此值域 1.1~1.6 倍范围内选择。例如

的值域为

 

600,0

，那么

701M

即为一个不错的选择。竞赛的时候可以

写一个素数生成器或干脆自己写一个“比较像素数”的数。

我用 4000 个数插入一个容量为 701 的 Hash 表，得到的结果是：

测试数据

随机数据

连续数据

最小单元容量：

最大单元容量：

期望容量：

5.70613

标准差：

2.4165

0.455531

可见对于随机数据，取余法的最大单元容量达到了期望容量的将近 3 倍。经测试，在我的机器（Pentium III

866MHz，128MB RAM）上，该函数的运行时间大约是 39ns，即大约 35 个时钟周期。

2．乘积取整法

我们用关键字

乘以一个在

 

1,0

中的实数

（最好是无理数），得到一个

 

k,0

之间的实数；取出其小数部

分，乘以

，再取整数部分，即得

在 Hash 表中的位置。函数表达式可以写成：

 

 

1mod)( kAMkh 

；

其中

1modkA

表示

的小数部分，即

 

kAkA

。例如，表容量

12M

，种子

15 

A

（

15 

A

是

一个实际效果很好的选择），关键值

100k

，那么

 

9kh

。

同样用 4000 个数插入一个容量为 701 的 Hash 表（

15 

A

），得到的结果是：

测试数据

随机数据

连续数据

最小单元容量：

最大单元容量：

期望容量：

5.70613

标准差：

2.5069

0.619999

从公式中可以看出，这个方法受

的影响是很小的，在

的值比较不适合直接取余法的时候这个方法的

表现很好。但是从上面的测试来看，其表现并不是非常理想，且由于浮点运算较多，运行速度较慢。经反复优

化，在我的机器上仍需 892ns 才能完成一次计算，即 810 个时钟周期，是直接取余法的 23 倍。

3．平方取中法

我们把关键字

平方，然后取中间的

 

log

位作为 Hash 函数值返回。由于

的每一位都会对其平方中

间的若干位产生影响，因此这个方法的效果也是不错的。但是对于比较小的

值效果并不是很理想，实现起来

也比较繁琐。为了充分利用 Hash 表的空间，

最好取 2 的整数次幂。例如，表容量

162

M

，关键值

100k

，那么

 

8kh

。

用 4000 个数插入一个容量为 512 的 Hash 表（注意这里没有用 701，是为了利用 Hash 表的空间），得到的

结果是：

测试数据

随机数据

连续数据

最小单元容量：

最大单元容量：

期望容量：

7.8125

标准差：

2.95804

2.64501

效果比我们想象的要差，尤其是对于连续数据。但由于只有乘法和位运算，该函数的速度是最快的。在我

剩余531页未读，继续阅读

评论收藏

内容反馈

zpjun

粉丝: 1
资源: 1

全国信息学竞赛算法研究论文合集

全国信息学竞赛算法研究论文合集(续)

全国信息学竞赛算法合集(免费滴)

算法合集之《“分层图思想”及其在信息学竞赛中的应用》.pdf

2008年信息学奥林匹克中国国家国家集训队论文

2009年信息学奥林匹克中国国家国家集训队论文

acm国家集训队2008年论文合集

acm国家集训队2005年论文合集

acm国家集训队2007年论文合集

算法合集之《基本数据结构在信息学竞赛中的应用》.doc

算法合集之《信息学竞赛中搜索问题的常见优化技巧》.

算法合集之《浅析最大最小定理在信息学竞赛中的应用》.ppt

算法合集之信息学竞赛中概率问题求解初探PPT学习教案.pptx

算法合集之浅析最大最小定理在信息学竞赛中的应用PPT学习教案.pptx

IOI国家集训队论文集1999-2019

acm国家集训队2006年论文合集

acm国家集训队2003年论文合集

IOI 2009 国家集训队论文part_2

国家集训队2007论文集

1.信息学奥赛骗分导论 2.数之理 3.数学奥林匹克中的应试技巧

IOI 08集训队论文

国家集训队2019论文集.pdf

IOI 2009 国家集训队论文part_1

2017数学建模国赛+深圳杯优秀论文

国家集训队2019论文集.zip

Academic+Phrasebank+2021+Edition+_中英文对照.pdf

基于python的超市管理系统的设计与实现毕业论文+项目文档源码

1000套计算机毕业设计带源码

数模国赛word模板.zip

最新资源