散列表实验报告(不同装载因子下链表法和放寻址法对比)

TOC \o "1-4" \h \z \u 1 概述 2

2 原理介绍 2

2.1 散列表介绍 2

2.2 直接寻址表 3

2.3 散列函数 3

2.3.1 除法散列 4

2.3.2 乘法散列 4

2.3.3 全域散列 4

2.4 解决碰撞问题 5

2.4.1 链接法 5

2.4.2 开放寻址法 5

2.4.2.1 线性探查 6

2.4.2.2 二次探查 6

2.4.2.3 双重散列 7

3 算法说明 7

3.1 概述 7

3.2 使用链接法解决碰撞问题 8

3.2.1 算法思想 8

3.2.2 伪代码描述 9

3.2.3 算法分析与证明 10

3.3 使用开放寻址法的双重散列解决碰撞问题 12

3.3.1 算法思想 12

3.3.2 伪代码描述 12

3.3.3 算法分析与证明 14

3.4 两个算法的比较 14

4 实验设计与分析 16

5 C++实现与结果分析 18

5.1 C++实现与结果 18

5.2 结果分析 26

6 实验总结和感想 27

概述

该实验报告主要是通过介绍散列表的各种技术，包括散列函数、解决碰撞的机制等技术，并对两种解决碰撞的机制：链接法和开放寻址法进行分析和证明，并通过实验分析两者在不同的规模下的运行时间和空间占用的对比，来证明在“算法说明”一章中的理论分析。

原理介绍

散列表介绍

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。它实际上是是普通数组概念的推广，因为可以对数组进行直接寻址，故可以而在O(1)时间内访问数组的任意元素。如果存储空间允许，我们可以提供一个数组，为每个可能的关键字保留一个位置，就可以应用直接寻址技术。

　　基本概念

　　若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

　对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称作同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

　若对于关键字集合中的任一个关键字，经散列函数映射到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

　常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位

当实际存储的关键字数比可能的关键字总数较小时，此时采用散列表就会较直接数组寻找更为有效，因为散列表通常采用的数组尺寸与所要存储的关键字数十成比例的。在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标。

名词解释：

碰撞：就是指多个关键字映射到同一个数组下标位置

直接寻址表

当关键字的全域U比较小时，直接寻址是一种简单而有效的技术。假设某应用要用到一个动态集合，其中每个元素都有一个取自全域U={0，1，2，…}的关键字，此外M是一个不很大的数。另假设没有两个元素具有相同的关键字。

此时动态集合中的元素可以放在直接寻址表中。亦即不把每个元素的关键字及其卫星数据都放在直接讯指标外部的一个对象中，再由表中某个槽的指针指向该对象，而是直接把对象放在表的槽中，从而节省了空间。此外，通常不需要存储对象的关键字域，因为如果我们有了一个对象的在表中的下标，就可以得到它的关键字。但是，如果不存储关键字，我们必须有某种办法来确定某个槽是否为空。

一般来说，直接寻址法比较浪费存储空间，而且容易发生碰撞（当有关键字相等的时候）。这里不与讨论。

散列函数

好的散列函数的特点：

一个好的散列函数应（近似地）满足简单一致散列的假设：每个关键字都等可能地散列到m个槽位的任何一个之中去，并与其他得到关键字已被散列到哪一个槽位中无关。不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

有时，我们偶尔也能知道关键字的概率分布。例如，如果已知各关键字都是随机的实数k，他们独立地、一致地分布于范围0<=k<1中，那么散列函数：

h(k)=[km]

就能满足简单一致散列这一假设条件。

将关键字解释为自然数：

一个字符串关键字可以被解释为按适当的基数记号表示的整数。一般来说按照ASCII码来翻译字符。后面的所有算法和实现都是按照自然数来做的。

除法散列

在用来设计散列函数的除法散列函数中，通过取k除以m的余数，来将关键字k映射到m槽的某一个当中去。亦即，散列函数为：

h(k)=k mod m

当应用除法散列时，要注意m的选择。例如，m不应是2的幂，因为如果m=2p，则h(k)就是k的p个最低位数字。除非我们事先知道，关键字的概率分布使得k的各种最低p位的排列形式的可能性相同，否则在设计散列函数时，最好考虑关键字的所有为的情况。

可以选作m的值常常是与2的整数幂不太接近的质数。例如，假设我们要分配一张散列表，并用链接法解决碰撞，表中大约要存放n=3000个字符串，每个字符有8位。一次不成功的查找大约要检查4个元素，故分配散列表的大小为m=749。之所以选择749这个数，是因为它是个接近a=3000/4,但又不接近2的任何次幂的质数。

乘法散列

构造散列函数的乘法方法包含两个步骤。第一步，用关键字k乘上常数A（0<A<1），并抽取出kA的小数部分。然后，用m乘以这个值，再取结果的底。总之，散列函数为：

h(k)=floor(m*(kA mod 1))

其中”kA mod 1 “即kA的小数部分。

乘法方法的一个优点是对m的选择没有什么特别的要求，一般选择它为2的某个幂次，这是因为我们可以在大多数计算机上，按如下所示的方法，很方便地实现散列函数。一般来说A约等于0.6180339887….的时候，散列效果比较好。

全域散列

全域散列的基本思想是在执行开始时，就从一族仔细设计的函数中，随机地选择一个作为散列函数。就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最差性能。同时，随机化使得即使当时对同一个输入，算法在每一次执行时的形态也都不一样。这样就可以确保对于任何输入，算法都具有较好的平均情况性态。

设H为有限的一组散列函数，它将给定的关键字域U映射到{0,1,2,….}当中。这样一个函数组成为市全域的(universal)，如果对每一对不同的关键字k，l属于U，满足h(k)=h(l)的散列函数h属于H的个数至多为|H|/m。换言之，如果从H中随机地选择一个散列函数，当关键字k不等于l时，两者发生碰撞的概率不大于1/m，这也正好是从集合{0,1,2…}中随机地，独立地选择h(k)和h(l)时发生碰撞的概率。

解决碰撞问题

链接法

链接法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。例，一个开散列的散列表，这个表中每一个槽存储一个记录和一个指向链表其余部分的指针。这7个数存储在有11个槽的散列表中，使用的散列函数是h(K) = K mod 11。数的插入顺序是77、7、110、95、14、75和62。有2个值散列到第0个槽，1个值散列到第3个槽，3个值散列到第7个槽，1个值散列到第 9个槽。

开放寻址法

在开放寻址法（open addressing）中，所有的元素都存放在散列表里。亦即，每个表项或包含动态集合的一个元素，或包含NIL。当查找一个元素时，要检查所有的表项，知道找到所需的元素，或者最终发现元素不在表中。不像在链接法中，这儿没有链表，也没有元素存放在散列表外。在这里散列表有可能会被填满，但是绝对不会大于1.

在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项，直到找到一个空槽来放置这个元素为止。检查顺序可以是线性的，可以是二次的，也可以是再次散列的。

查找关键字和插入关键字的算法基本上是一样的。

而在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将NIL置于其中来标识它为空。因为这样做的话，会导致在插入另外的关键字探查过程中，有可能无法检索某些关键字。这里有一个解决方法，就是在槽i中置一个特定的槽当作空槽，从而冉冉可以插入新元素。

线性探查

给定一个普通的散列函数h’:U->{0,1,2…m-1}(称为辅助散列函数)，线性探查方法采用的散列函数为：h(k,i)=(h’(k)+i) mode m , i=0,1,2,…m-1

给定一个关键字k，第一个探查的槽式T(h’(k)),接下来探查下一个槽，知道T[m-1]。

线性探查方法比较容易实现，但存在一个问题，成为一次群集。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽为下一个将被占用的槽的概率是(i+1)/m，连续被占用的槽的序列将会变得越来越长，因而平均查找时间也会随之增加。

二次探查

二次探查（quadratic probing）采用的形式如下：

h(k,i)=(h’(k)+c1i+c2i2)mod m

其中h’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。处事的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。

双重散列

双重散列是用在开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下形式的散列函数：

h(k,i)=(h1(k)+ih(k))mod m

其中h1和h2是辅助散列函数。初始探查位置为T[h1(k)],后续的探查位置在此基础上加上偏移量h2(k)模m。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于k，因为初始探查位置和偏移量都可能发生变化。

算法说明

概述

对于一个散列表，最重要的事情是做两件事情：

选择散列函数，使关键字的分布尽量的均匀

使用一种解决碰撞的机制

对于选择散列函数，我们从原理介绍中可以看出，在我们提供的三种散列函数当中，全域散列具有最好的性能。因为这篇实验报告主要的讨论的是解决碰撞的机制问题，所以，这里我就直接选择了性能最好的散列函数——全域散列函数。在后面的文章中，所有的散列函数都是全域散列。特此说明。

对于解决碰撞的机制，课文提供了两种方法：链接法和开放寻址法。

链接法一般来说就是一种，即不排序的双向链表。

而开放寻址法又至少有三种方法：线性探查、二次探查和双重散列，因为在原理介绍中也谈到：线性探查会产生群集现象，二次探查也会产生程度较轻的群集现象，性能最好的就是双重散列。所以我在用开放寻址法与链接法的对比当中，开放寻址法也相应地采用性能最优的算法，也即双重散列方法。

使用链接法解决碰撞问题

算法思想

在链接法中，把散列到同一槽的所有元素都放在一个链表中。槽j中有一个指针，它指向由所有散列到j的元素构成的链表头；如果不存在这样的元素，则j中位NIL。

链表法是最简单的解决碰撞的方法，但是非常有用。即使是java.util.HashMap的类当中，也是采用链表法。它采用的链表法的方式，链表是单向链表，因此在删除过程中要自己维持prev节点，我想不采用双向链表是从节省空间考虑。

HashMap采用链表法而不是开放地址法，猜想可能的原因是从实用角度出发，对空间和时间效率做出的折中选择。采用开放地址法，无论是线性探测或者二次探测都可能造成群集现象，而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率，容易造成空间的浪费。

主要操作：

插入

首先，使用散列函数计算出要插入的关键字的散列值，然后查找该散列表对应的位置上的指针是否为空。如果为空，则说明该位置上的链表的长度为0，则可以将该元素添加到该散列表对应位置上的链表上。如果不为空，则将该元素添加到已经存在的链表中。

查找

首先使用散列函数计算出要查找的关键字的散列值，然后查找该散列表对应位置上的指针。如果为空，则说明该元素不在散列表中，返回NIL；如果不为空，则沿着该位置上的链表一直搜索下去，知道找到该元素为止，如果还是没有找到，则返回NIL，表明该元素不在散列表中；如果找到，则返回该元素的指针。

删除

首先，使用散列函数计算出要插入的关键字的散列值，然后查找该散列表对应的位置上的指针是否为空。然后类似查找操作，找到该元素的指针，如果找不到则返回操作失败。如果能找到该元素的指针，则首先保存该节点的next指针，然后将next指针覆盖该节点的pre元素的next指针，最后释放该节点的内存。

伪代码描述

插入

CHAINED-HASH-INSERT(T,x)

index=HASH(x)

if(hash_table[index]==NIL)

then create a chain

insert x to the chain

else

then insert x to the head of the chain

return

查找

CHAINED-HASH-SEARCH(T,k)

index=HASH(x)

if(hsh_table[index]==NIL)

then return false

else

then find x in the chain

return x

删除

CHAINED-HASH-DELETE(T,x)

index=HASH(x)

if(hash_table[index]==NIL)

then return false

else

then find x in the chain

if !find(x)

return false

else

then delete x

return true

算法分析与证明

对于查找操作：

给定一个能存放n个元素的、具有m个槽位的散列表T,定义T的装载因子（load factor），=n/m.即一个链中平均存储的元素数。

用链接法散列的最坏性能很差，所以n个关键字都散列在同一个槽中，从而产生一个长度为n的链表。此时，最坏情况下查找的时间为O(n)，加上计算散列函数的时间，这么一来就和一个链表来链接所有时间差不多。

散列方法的平均性态一来与所选取的散列函数h在一般情况下，将所有的关键字分布在m个槽位上的均匀程度。我们假定任何元素散列到m个槽中的概率都是一样的，且与其他元素已经被散列到什么位置上独立无关，即简单一致散列。

对于j=0，1…m-1，列表T[j]的长度用nj表示，这样有：

n=n0+n1+n2…+nm1-1

nj的平均值为E[nj]= =n/m

假定可以再O(1)时间内计算出散列值h(k),从而查找具有关键字为k的元素的时间线性地依赖于表T[h(k)]的长度nh(k).先不考虑计算散列函数和寻址槽h(k)的O(1)的时间，我们查找算法期望查找的元素数，即为比较元素的关键字时候为k而检查的表T[h(k)]中的元素数。我们分两种情况来考虑：

查找成功

假定要查找的关键字时表中存放的n个关键字当中任何一个的可能性事相同的。在对元素x的一次成功的查找中，所检查的元素都是在x之后插入的，这是以内新的元素都是在表头插入的。为了确定所查找的元素的期望数目。对x所在的链表中，在x之后插入到表中的期望元素加1，再对表中的n个元素x取平均。

所以对于一次成功的查找来说，所需的全部时间为.

查找不成功

在简单一致散列的假设下，任何尚未被存储在表中的关键字k都是等可能地被散列到m个槽的任一个当中。因为，当查找一个关键字k时，在不成功的情况下，查找的期望时间就是查找到链尾的期望时间，这一时间的期望商都是E[n(k)]= 。于是一次不成功的查找平均要检查个元素，所需的总时间（包括计算h(k)的时间）为（1+）。

对于插入操作：

主要有两部分运行时间构成，一部分是运行散列函数的时间，还有一部分是在链表头插入元素的部分。因为两个部分的时间都是O(1)，所以其运行时间为.

对于删除操作：

也是主要有两部分运行时间构成,一部分是查找元素的时间，另外一部分是删除元素并调整链表的时间。无论查找成功与否，其运行时间都是（1+）。所以总的运行时间是

。

操作

成功运行时间

不成功的运行时间

平均运行时间

查找

（1+）

（1+）

（1+）

插入

（1+）

（1）

删除

（1+）

（1+）

（1+）

使用开放寻址法的双重散列解决碰撞问题

算法思想

如前面概述所说，这里讨论的是开放寻址法的双重散列方法。双重散列事开放寻址法的最好方法. 它的散列函数大体如下:

h(k,i) = ( h1(k) + i*h2(k) ) mod m, 其中 i是发生碰撞的次数, k是关键字值, m是散列表的容量, h1, h2是两个散列函数称为辅助散列函数,

为了能查找整个散列表, 值h2(k)要与表大小m互质!!! 一般设计为h2(k)是一个总是产生质数的函数, 或者m是一个质数并且h2总是产生比m小的正整数.比如, 我们可以去m为质数, h1(k) = k mod m, h2(k) = 1+ ( k mod (m-1) ) m-1比m略小.

双重散列的探查序列是m的平方级别的, 而线性和二次都是m级别的, 因此双重散列的效果要好得多。

插入操作

首先进行散列函数运算，得出散列值，先查找该位置有没有被元素占据，如果有则进行第一次散列函数运算，计算出下一个探查序列，直到找到一个空的位置插入为止。

查找操作

与插入操作类似，通过运行散列函数得到下一个探查的位置，一直到找个该元素为止。如果探查完所有的序列，但仍旧没有找到，则返回错误。

删除操作

首先执行查找操作，找到后删除该位置的元素。因为对于开放地址法，删除是一个比较困难的问题。删除该位置的元素后，我们置该位置一个DELETE值，表示该位置曾经有元素，但已经被删除了。则程序认可继续探查后面的序列，找到之前插入的其他元素。

伪代码描述

插入

HASH-INSERT(T,k)

i=0

repeat j=h(k,j)

if T[j]=NIL

then T[j]=k

return j

else i=i+1

until i=m

error “hash table overflow”

查找

HASH-SEARCH(T,k)

i=0

repeat j=h(k,i)

if T[j]=k

then return j

i=i+1

until T[j]=NIL or i=m

return NIL

删除

HASH-DELETE(T,k)

i=0

repeat j=h(k,i)

if T[j]=k

then T[j]=DELETED

i=i+1

until T[j]=NIL or i=m

return NIL

算法分析与证明

像在分析链接法时一样，对开放寻址法的分析是以散列表的装载因子=n/m来表达的，n和m趋向于无穷。当然，在开放寻址法中，每个槽中至多只有一个元素，因为n<=m，这意味着<=1。

现假设采用的是一致散列法。在这种理想的方法中，用于插入和查找每一个关键字k的探查序列<h(k,0),h(k,1),h(k,2)….h(k,m-1)>为<0,1,2,…m-1>的任一种排列的可能性是相同的。当然，每一个给定的关键字有唯一固定的探查序列。

对于查找操作：

在一次不成功的查找当中，除了最后一次探查之外，每一次探查都要检查一个被占用的，但并不包含所求关键字的槽，最后检查的槽时空的。先定义随机变量X为一次不成功的查找中所做的探查数，在定义事件Ai(i=1,2,…)为进行了第i次探查，且探查到的是一个已被占用的槽的事件。那么事件{X>=i}即为事件的交集。

由于共有n个元素和m个槽，因为Pr{A1}=n/m。对于j>1,在前j-1次探查到的都是已占用槽的前提下，有第j次探查到的是已占用槽的概率是(n-j+1)/(m-j+1)。之所以会得出这一概率，是因为我们要在(m-(j-1))这个未探查的槽中，查找余下的(n-(j-1))个元素。根据一致散列假设，这一概率为这几个量的壁纸。注意到n<m蕴含对于所有满足0<=j<m的j来说，有(n-j)/(m-j)<=n/m，于是对所有满足1<=i<=m，有：

所以得出期望探查数的界是：

如果是一个常数，一次不成功查找的运行时间为O(1)。例如，如果散列表是半满的，在一次不成功查找中，平均的探查数至多是1/(1-0.5)=2。

两个算法的比较

从理论上，链表法和开放寻址法的运行时间对比如下：

其中m为槽位总数，n为元素总数，=n/m为装载因子

最坏情况

平均情况

理论平均探查界

说明

插入

链表法

假设需要插入到链表中的元素都是不相同的

开放寻址法

查找

链表法

开放寻址法

虽为常数，但与系数相关

删除

链表法

开放寻址法

空间使用对比：

给定n个需要散列的元素，每个元素的长度是固定的a,指针的固定长度为b，假设使用链表法的装载因子为,而使用开放寻址法的装载因子为。

则链表法的空间使用量是：

而开放寻址法的空间使用量是：

假设指针长度为4bytes,元素固定长度为4bytes.

则两中算法的使用空间为：(单位bytes)

平均探查数目

链表法

n=10000

开放寻址法

n=10000

2

=1

120K

=0.5

80K

3

=2

100K

=0.66

60K

4

=3

93K

=0.75

53.3K

5

=4

90K

=0.8

50K

从图中我们可以看出，同等平均性能的情况下，链表法要比开放寻址法占用的空间多50%~80%。

实验设计与分析

测试环境：

配置

说明

CPU

Intel Pentium E5200

2.5GHZ， 2M二级缓存

内存

威刚 DRR2 1066 2G

硬盘

希捷 500G

32M缓存

显卡

昂达 9600GS

384M显存，DDR2颗粒

操作系统

windows 7旗舰版

开发环境：

硬件部分：

如上

说明

操作系统：

window 7旗舰版

开发平台

Visual studio 2008

编程语言

C++

该实验主要是验证链表法和开放寻址法的运行时间。

链表法的实验流程:

开放寻址法的实验流程：

与链表法的流程是基本一样的，只是插入、删除和查找的具体实现不一样。

C++实现与结果分析

C++实现与结果

该图是在n=10000,m=2000,的情况下运行的，从创建10000个随机数组到全部插入，再到全部删除的过程。

该图是链表法在2~5的装载因子下的表现（全部均为成功）：

开放寻址法实验结果：

该图是在n=10000,m=20000,的情况下运行的，从创建10000个随机数组到全部插入，再到全部删除的过程。

该图是开放寻址法在0.3~0.9的装载因子下的表现（全部均为成功）：

装载因子

实际值

实际比例

理论比例

=0.3

1.0ns

1

1

=0.4

1.5ns

1.5

1.2

=0.5

1.88ns

1.88

1.4

=0.6

2.8ns

2.8

1.75

=0.7

5.8ns

5.8

2.331

=0.8

10.9ns

10.9

3.5

=0.9

20.1ns

20.1

7

实际比例跟理论比例有出入，是因为实验的时候查找的是在散列表中都有的关键字，所以查找起来速度会比较慢。算法分析中的理论比例是全部成功和不成功的平均查找性能。

实验部分程序如下图：

结果分析

由实验可知：

链表法（n=10000）：

平均探查数目

装载因子

实际使用空间

实际平均查找时间(不考虑命中)

实际平均查找时间(全部命中)

2

=1

120K

1.688ns

1.3ns

3

=2

100K

1.700ns

1.4ns

4

=3

93K

1.703ns

1.6ns

5

=4

90K

1.734ns

1.8ns

6

=5

88K

1.834ns

2.0ns

开放寻址法（n=10000）：

平均探查数目

装载因子

实际使用空间

实际平均查找时间(不考虑命中)

实际平均查找时间(全部命中)

2

=0.5

80K

2.03ns

0.9ns

3

=0.66

60K

2.5ns

1.1ns

4

=0.75

53.3K

2.97ns

1.2ns

5

=0.8

50K

5.47ns

1.3ns

6

=0.86

48K

8.75ns

1.5ns

从表格我们可以看出链表法和开放寻址法的查找时间都是常数，而这个常数和装载因子是密切相关的。这也证明了我们在算法说明中的分析是正确的。

由表格可见，开放寻址法在相同的探查数目的情况下（忽略程序因素）是比链接法要快一些的，而当开放寻址法在装载因子比较小的时候，其发生碰撞的几率极小，所以其寻址速度接近普通数组。

如果元素所占的空间和指针相比而言较大时，也即链接法使用的指针所占的空间可以忽略不计的时候，链接法以其比较稳定的查找性能胜出。特别是在存储空间有限定的情况下，链接法不失为一种处理碰撞的好方法。

实验总结和感想

这个实验大作业花了我整整一个星期，其中所有的代码都是独立完成，调试和完善的时间用很大一部分。除了深入了解散列是如何运作的之外，最重要是在写程序的过程中学到了不少东西。

总结了一下，从算法方面的体会如下：

散列的效率是很高的

无论是链表法还是开放寻址法，它的运行时间都是常数，当然这取决于装载因子。实际上散列就是用空间来换取查找的速度。散列的另外一层意义就是通过关键字散列后的值作为数组索引查找。

散列函数很重要

理论上，全域散列的一致性比较好，但是在实验的过程中还没有用到

链接法和开放寻址法的对比

链表法比较适用于空间要求比较严格，不允许将左右的元素装在散列表当中的情况，而当关键字的卫星数据比较大的时候，可以使用链表法，简单实用。而开放寻址法的探查方法很讲究，线性查找和二次查找都会导致不同程度的群集，所以基本上不用。最好还是用双重散列，它的探查序列可以达到m的二次方种，比线性探查和二次探查的探查序列可能性要高得多。

从编写程序方面学习到的东西有如下几点：

突破随机数的上限限制

生成随机数虽然看起来比较简单，用rand()函数，再加上srand()给它一个种子，甚至用当前时间来作为种子，可以生成随机数这些简单的东西外。我通过编程发现，rand()函数生成的随机数大小是有上限的，是int类型的最大正整数，也就是32767。如何生成一个比这个数更加大的数的确费了我一番心机。可以考虑的算法如下：如果要生成一个100000的数字，那么可以用两个1~1000随机数相乘，但是这样会导致有些质数不能被生成，而且每个随机数的出现概率不均匀。我的做法是将随机数分成两个部分，如果是1000000就分成千位以上和千位以下的部分，两部分分别用随机数代替即可。

而生成不重复的随机数虽然理论上比较简单，只要比较和它之前生成的随机数，如果有重复的话，就重新生成就OK了， 但是这样的效率非常低，在1~1000000内生成500000个随机数，那是很慢的，大约需要等十几秒。

而随机数的范围限制由一条公式：rand()*(max-min)/32767+min 即可。

指针相关

尽管指针以前学过，也用过，但是在这个实验中调试起来也是挺麻烦的，很容易就内存泄露。在编写链表法的过程中，原来我想用之前封装的链表类实现，但是发现修改了一部分代码后，一直在报内存错误。而我调试多次都不成功，最后发现时把某个指向NILL的指针当成是非空指针使用了。

指针数组的声明是int **p_arr。使用的时候有点不习惯。

程序执行时间的计算

程序的执行时间有一个函数，GetTickCount(),它返回的是一个DWORD类型，只要在程序段的两端记下GetTickCount，相减就能得到该程序段的运行时间。它的计量单位是百万分之一秒，大约在49.7日就会reset一次，如果还想计得更长一些，可以用GetTickCount64()。当然，别忘了include <windows.h>。

格式化输出

格式化输出虽然在这个程序中体现不明显，但是以后应该有用。include <iomanip>头文件后，就可以使用setw(n)等函数进行格式化输出。

参考文献：

《C++ premium 中文版》， 李师贤、蒋爱军等译，2006年，人民邮电出版社

《C++ 程序设计》，王铤等著，2005年1月，清华大学出版社

《算法导论》，Thoma H.Cormen Charles E.Leiserson等著，2008年6月，机械出版社

《数据结构》，严慧敏等著，2001年，清华大学出版社

百度知道

MSDN for C++