哈希表设计：除留余数法与线性探测再散列解决冲突

本文主要探讨了哈希表的设计，包括实验目的、实验内容、问题描述、数据描述和算法描述，并提供了源程序示例。实验旨在通过除留余数法和线性探测再散列解决冲突，建立哈希表并计算查找成功率的平均查找长度。 哈希表是一种高效的数据结构，它通过哈希函数将关键字映射到一个固定大小的数组中，以实现快速的插入、删除和查找操作。在这个实验中，哈希表的构造方法是除留余数法，这是一种常见的哈希函数构造策略，它将关键字与一个小于或等于表长的最大质数取模，以此确定关键字在表中的位置。 实验内容涉及了处理冲突的方法，即线性探测再散列。当两个或多个关键字通过哈希函数得到相同的地址时，线性探测再散列会按照一定的顺序（通常是+1）寻找下一个空位置，直到找到合适的位置或者遍历完整个表。 在问题描述部分，给出了一个具体的关键字集合，例如{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，并且提到了哈希表的长度（m）和装填因子（a）。哈希表的装填因子是表中已存储元素数量与表长度的比值，它影响查找效率和冲突概率。 数据描述中，哈希表被表示为动态分配的顺序存储结构，每个元素包含一个关键字。`ElemType`结构体定义了这种元素，包含一个`KeyType`类型的键。 算法描述包括以下步骤： 1. 选择哈希函数`H(key) = key % p`，其中`p`是不超过哈希表长度`m`的最大质数。 2. 计算每个关键字的哈希值。 3. 使用线性探测再散列来处理冲突，建立哈希表。 4. 在哈希表中执行查找操作，记录关键字比较的次数，计算并输出查找成功的平均查找长度。 提供的源代码片段展示了如何定义数据类型和哈希函数`haxi`的框架，但实际的查找和冲突解决代码并未给出。完整的程序应该包含查找操作的实现，计算平均查找长度的逻辑，以及可能的冲突解决循环。 这个实验旨在让学生深入理解哈希表的工作原理，掌握哈希函数的选择和冲突解决策略，并通过实际编程加深对这些概念的理解。通过这样的实践，可以提升在真实场景中应用哈希表解决问题的能力。