1、 数数 据据 结结 构构 课课 程程 设设 计计 说说 明明 书书 学生姓名学生姓名: 学学 号：号： 学学 院院: 软件学院 专专 业业: 软件工程 题题 目目: 散列表的实验研究 指 导 教指 导 教 师师 2011 年 12 月 20 日 1 1. 设计任务概述（包括系统总体框图及功能描述）设计任务概述（包括系统总体框图及功能描述） 系统总体框图 问题描述 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的 方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函 数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。 概要设计 散列又称哈希或杂凑。散
2、列法（Hashing）在表项的存储位置与它的关键码 之间建立一个确定的对应函数关系 Hash（） ，以使每个关键码与结构中的唯一存 储位置相对应，该关系可用下式表示： Address=Hash（Record.key） 相应的表称为哈希表，这种方法的基本思想是：首先在元素的关键字 k 和元素的 存储位置 p 之间建立一个对应关系 H，使得 p=H(k)，H 称为哈希函数。创建哈希 表时，把关键字为 k 的元素直接存入地址为 H(k)的单元；以后当查找关键字为 k 的元素时，再利用哈希函数计算出该元素的存储位置 p=H(k)，从而达到按关键 字直接存取元素的目的。 哈希函数是一个映象，哈希函数的设
3、定灵活，只要使得任何关键字所得的哈希函 数值都落在表长范围之内即可。 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地 址上，即 k1k2，但 H(k1)=H(k2)，这种现象称为冲突，此时称 k1 和 k2 为同 建立散列 表 线性探测 再散列 二次探测 再散列 链地址法 线 性 探 测 再 散 列 查 找 二 次 探 测 再 散 列 查 找 链地址法 查找 2 义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。 综上所述，哈希法主要包括以下两方面的内容。 (1）如何构造哈希函数； (2） 如何处理冲突。 2. 本设计所采用的数据结构（如：链表、栈、树、图
4、等）本设计所采用的数据结构（如：链表、栈、树、图等） 一、散列函数 通常，构造散列函数应该注意的几个问题包括：首先，散列函数的定义域必 须包括需要存储的全部关键码，而如果散列表允许有 m 个地址，其值域必须在 1m-1 之间;其次，散列函数计算出来的地址应能均匀分布在整个地址空间中； 再次，散列函数应当是尽量简单的。 1直接定址法 直接定址法蓝颜元素关键码的某个线性函数值作为该元素的散列地址 （散列 地址，即元素最终在字典中的存储位置） 。如下面的函数式： Hash（key）=akey+b 式中，a，b 为常数。采用该种方法，当向字典中加入某一新元素时算法自动调 用此函数，以确定该元素最终的存储位置。若某元素关键码 key 为 1，上式中， a=2，b=3 则该元素最终会存储在字典第 5 个位置中。 直接定址法的优点是实现方法简单，算法时间复杂度较小，而且不会产生冲 突。但是，直接定址法要求散列地址空间的大小与关键码集合的大小一致，而这 种要求是苛刻的，一般很难实现。例如当关键码的范围为 11000000 时，元素散 列地址的个数也要达到 10000
