哈希查找

哈希查找

一、 功能
自定义哈希函数及解决冲突的方法，建立一张哈希表；输入要查找的数据，进行哈希查找，查找结果有相应提示。

二、 哈希查找简介
哈希查找是一种基于计算的查找，其查找长度与查找表的长度无关，而与哈希函数的选择和解决冲突的方法有关。
哈希查找先将关键字通过哈希函数进行计算，计算出其地址，放入哈希表中（查找的过程同此）。如果地址已经有其他元素，称为冲突，此时要根据采用的解决冲突的方法来解决。
下面我们通过一个实例来进行学习。

三、 哈希表的建立和哈希函数的选择
如建立一个长度为35的哈希表，即定义一个长度为35的数组。
哈希函数用来计算关键字的地址，如选择的哈希函数为f（x）=x % 29，则关键字35的数组元素下标应该为6，关键字72的数组元素下标应该为14，等等。

四、 解决冲突的方法
当 两个不同关键字通过哈希函数计算出来的地址一样时，称为冲突。如输入关键字35，计算出其下标为6，此时下标为6的地方已经存在元素64，此时产生冲突。 可以用线性探测方法，即依次探测下标6后面的地址，是否有空位可以存放35。探测的次数不能过多，例如最多5次为宜，即6后面连续5个下标都无空位的话， 当作溢出处理，不能插入。

五、 哈希查找
元素的查找与元素的插入相对应。如查找关键字35，通过哈希函数计算出其下标当为6，则查看数组下标为6的元素是否35，如果是则找到，如果不是则需要线性探测6后面的5个位置，如果在这5个位置的其中一个，则找到，否则输出找不到。

六、 程序流程
1、 定义哈希表；
2、 输入若干个数，插入到哈希表中，输出哈希表；
3、 输入要查找的关键字，输出查找结果。
（如果可能，建立菜单以便选择操作最好）