目 录
1 需 求 分 析 ...................................................................................................................................... 1
1.1 Hash 表设计 ........................................................................................................................ 1
1.2 添加与导入记录 .................................................................................................................. 1
1.3 查询记录 ............................................................................................................................. 2
1.4 不 同 Hash 函 数 比 较 ........................................................................................................... 2
1.5 不同冲突解决方法比较 ...................................................................................................... 2
2 概 要 设 计 ...................................................................................................................................... 2
2.1 数据类型的定义 .................................................................................................................. 2
2.2 功能模块结构图 .................................................................................................................. 5
2.3 Hash 模 块 概 要 设 计 ............................................................................................................ 6
3 运 行 环 境 ...................................................................................................................................... 7
4 开发工具和编程语言................................................................................................................... 7
5 详 细 设 计 ...................................................................................................................................... 7
5.1 Hash 函数设计 .................................................................................................................... 7
5.2 链地址法 Hash 设计 ........................................................................................................... 9
5.3 线性探测法 Hash 表设计 ................................................................................................. 16
5.4 电话号码查询系统设计 .................................................................................................... 19
6 运 行 结 果 .................................................................................................................................... 21
7 调 试 分 析 .................................................................................................................................... 25
8 心 得 体 会 .................................................................................................................................... 26
9 参 考 文 献 .................................................................................................................................... 27
本系统为电话号码查找系统，本系统最频繁的操作为查询功能，查询速度的快慢对此系统有至关重要的影响，因此应该选择合适的数据结构来进行设计。散列表可以实现 O(1)的快速查找，用 Hash 数据结构作为底层存储结构较为合适。本系统应首先实现 Hash 表的基本结构和操作，在此基础上构建电话号码查找系统。电话号码查找系统包括若干数据项：电话号码、用户名、地址，可以键盘输入或文件批量导入记录，既可以使用电话号码作为索引建立 Hash 表，也可以使用姓名作为索引建立 Hash 表，并通过电话号码和姓名进行查找记录。更进一步， 在设计 Hash 数据结构时，可设计不同的 Hash 函数及采用不同的冲突解决算法， 来比较性能的差异。具体功能如下：
Hash 函数对字符串进行散列，设计不同的冲突解决策略，如链地址法、线性探测法等。Hash 表的结构由 key-value 组成，基本操作有添加元素、查找元素、删除元素、遍历元素、建表、销毁表等，并且设计可以计算平均查找长度（ASL）的函数，以此来比较不同的 Hash 函数使用相同的冲突解决算法，以及相同的 Hash 函数使用不同的冲突解决算法的优劣。为方便 Hash 表的使用，Hash 表可自动扩容。
