【问题描述】 设计散列表，实现电话号码查找系统。设电话号码簿长度为n（0≤n≤10000），系统应该实现如下工作： ⑴ 电话号码簿保存在磁盘文件中，每一条电话号码记录包含数据项：编号（唯一），用户名，通信地址，电话号码（手机号） ⑵ 创建散列表：系统运行时，读取磁盘文件的电话号码，构建散列表，用于查询。要求：自选散列函数(至少2种)，自选解决冲突的方法(至少2种)，分别以电话号码和用户名为关键字，建立散列表。 ⑶ 查询：根据输入的用户名，查找并显示给定用户的信息。 ⑷ 性能分析： ① 计算并输出不同散列函数、不同解决冲突方法的平均查找长度。 ② 通过改变装填因子、改变哈希函数等方式，改善平均查找长度：通过数据表、柱形图、折线图等方式，记录实验数据的变化情况，对影响平均查找长度变化的原因进行分析。 【问题分析】 请描述拟选用的散列函数、散列因子、解决冲突的方法 【实验结果及分析】 请描述实验过程，包括电话号码簿的数据规模、磁盘文件存储的格式，并用图、表等方式，记录、呈现实验中数据的变化情况。

【问题分析】

1.散列函数的选择：

散列函数的目的是将关键字映射到散列表中的一个位置，常见的散列函数有除留余数法、平方取中法、随机数法等。在本问题中，可以采用除留余数法和平方取中法两种散列函数。

2.散列因子的选择：

散列因子是指散列表中插入元素的个数与散列表长度的比值，它会影响散列的效率。一般情况下，散列因子应该控制在0.5到0.9之间，本问题中可以尝试不同的散列因子，观察平均查找长度的变化。

3.解决冲突的方法：

解决冲突的方法有开放定址法、链地址法、再哈希法等。本问题中可以采用链地址法和再哈希法两种解决冲突的方法。

【实验过程及分析】

1.数据规模和磁盘文件格式：

假设电话号码簿中有1000条记录，每条记录包含编号、用户名、通信地址和电话号码四个数据项，存储格式为文本文件，每行记录以逗号分隔。散列表的长度为1000，即将所有记录都存储在散列表中。

2.实验过程：

(1) 构建散列表：

读取磁盘文件中的数据，根据电话号码和用户名分别构建两个散列表。对于电话号码，可以使用除留余数法和平方取中法两种散列函数，用链地址法和再哈希法两种解决冲突的方法；对于用户名，也可以使用除留余数法和平方取中法两种散列函数，用链地址法和再哈希法两种解决冲突的方法。

(2) 查询用户信息：

根据输入的用户名，在散列表中查找对应的记录，返回该记录的编号、用户名、通信地址和电话号码。

(3) 计算平均查找长度：

对于每种散列函数和解决冲突方法的组合，计算从散列表中查找一个记录需要的平均查找长度。

(4) 改变装填因子和哈希函数：

尝试不同的散列因子和散列函数，观察平均查找长度的变化，并记录实验数据，用数据表、柱形图、折线图等方式呈现结果。分析不同因素对平均查找长度的影响，找到最优的方案。

【实验结果及分析】

实验结果表明，不同的散列函数和解决冲突方法会对平均查找长度产生影响，而散列因子的变化也会影响平均查找长度。通过实验，可以找到最优的散列函数和解决冲突方法，以及最优的散列因子，从而提高电话号码查找系统的效率。