哈希表设计
一．实验目的
熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。
二．实验内容
程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲
突来建立相应的哈希表和完成查找过程及平均查找长度的计算。
三．问题描述
研究哈希（）表查找技术的两个重要问题是：构造 函数和处理冲突。
现在要求针对某个数据集合中的关键字设计一个哈希表（选择合适的哈希函数和处理
冲突的方法），完成 表的建立、查找，并计算 表查找成功的平均查找长度。
函数的构造方法有多种，其中除留余数法是一种最简单和最常用的方法。
考 虑 具 体 问 题 的 关 键 字 集 合 ， 如
，，，，，，，，，，，这样一组数据和给定的
哈希表长 或哈希表的装填因子 ，选用除留余数法和线性探测再散列技术解决冲突
所形成的哈希表以及该哈希表在查找成功时的平均查找长度 。
四．数据描述
表是根据设定的 函数和处理冲突的方法将一组关键字映射到一个有限
的连续的地址区间上，并以关键字在地址区间的“象”作为记录在表中的存储位置。因此
我们可以采用动态分配的顺序存储结构表示 表。
!"#
$%!#&&元素类型的定义
$%!'#&&动态分配的哈希表的首地址
五．算法描述
、选择合适的哈希函数 （ "）(")（* 为小于或等于 表长的最大质
数）；
、计算各个关键字的直接哈希函数值；
、根据处理冲突的方法建立哈希表，并输出；
、在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计
算和输出在等概率情况下查找成功的平均查找长度。
