OPEN哈希表实现单词本

一、算法思想

哈希表是根据关键码值而直接进行访问的数据结构，也就是说它可以通过对关键字进行某种函数映射直接找到其对应的表中的位置，这个映射函数叫做哈希函数。

由于哈希表中不需要比较即可找到所需元素，能够极大节省查找所需时间，但哈希表中在存储的时候可能会出现不同关键字通过函数映射却对应哈希表中同一位置的情况，这种情况我们称之为冲突。人们对此提出了两种解决方法，开放定址法（OpenAddressHash）和封闭定址法（CloseAddressHash），此次作业主要应用开放定址法来解决冲突。

开放定址法即如果一个元素的Hash地址对应的Hash单元已被另一个元素占有（冲突），我们需定义一个候选地址序列，每当发生冲突时，就选择下一个地址去试探，循环重复此过程。

 

二、设计思路

由于在题目中已经给出要存储的数据大小和类型，因此首先最重要的应该是确定合适的哈希表容量。效率较高的哈希表数据容量一般为待存数据量的2倍，且为素数。因为本作业要求存储1000个单词，所以选择哈希表容量大小为2729。 其次要确定合适的哈希函数，根据题目确定了关键字为单词的前三个字母，此函数同时要较好地适应哈希表大小，因此最终决定采用编码方式，即先计算首字母的ASCI码值*26*26、次字母的ASCI码值*26、再次字母的ASCI码值的总和，再用此总和对哈希表大小（即2729）取模。最终能够达到较好的存取效率。

 

三、程序代码

四、测试例

手工输入了21个单词作为测试，结果中将输出单词和该单词在哈希表中的位置。

五、运行结果

结果中显示出单词以及该单词在哈希表中所在位置。

六、分析

本作业中对于哈希函数的设计主要受到了二进制编码方式的启发，对于关键字，即单词中三个字母的选择是有关于哈希表大小的考虑，如果关键字定义为两个字母，按编码方式所需要的最大的地址空间为26*26+26=702，小于哈希表的数据容量大小。而选择三个字母时，按该编码方式所需要的最大的地址空间为26*26*26+26*26+26=18278，大于哈希表的数据容量大小，最终只需要再将其取模变成适合哈希表大小即可。

本作业中最大的问题在于单词输入时需要手工输入，费时费力，如果能够改写为从文本中读取，将节省很多人工输入单词的时间。