哈希查找算法程序

查找算法

问题描述：

设计一个实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找算法的程序，并具有人机交互界面。

基本要求：

（1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；

（2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；

（3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；

（4）二叉排序树必须实现构建、查找、插入、删除四个基本 *** 作；

（5）输出各种排序的结果并进行比较。*/

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 20

typedef struct/*顺序结构数据类型*/

h.length++

h.r[ }

else

if(k<l.r[mid].key) high=mid-1

else low=mid +1

}

if(i!=0)

{

printf("l.r[%d].key=%d\n",i,k)

printf("查找成功\n")

}

return ht

}

void HashSearch(RecordHash ht) /*哈希查找*/

{

int k,i

page_title("哈希查找")

printf("请输入要查找的关键字:")

scanf("%d",&k)

i=k%13

if(ht.HashTable[i].key==k)

{

printf("ht.HashTable[%d].key=%d\n",i,k)

printf("查找成功\n")

}

else

{

i=i+1

for(i<MAXi++)

if(ht.HashTable[i].key==k)

{

printf("ht.HashTable[%d].key=%d\n",i,k)

printf("查找成功\n")

break

}

if(i==MAX) printf("查找失败\n")

}

return_confirm()

}

void main()

{

RecordList L1,L2

BSTNode *pt

RecordHash ht

int k,i

printf("\n创建顺序查找线性表,输入0则结束输入(可不按顺序输入)\n")

L1=creat1()

printf("\n创建二分查找线性表，输入0则结束输入(按递增顺序输入)\n")

L2=creat1()

printf("\n创建二叉排序树，输入0则结束输入\n")

pt=creat2()

printf("\n创建哈希表\n")

ht=creat3()

menu:page_title("请选择查找方式，输入0则结束输入")

printf("顺序查找请按1\n二分查找请按2\n二叉排序树查找请按3\n哈希查找请按4\n推出请按0\n")

switch(getch())

{

case '1':

SeqSearch(L1)

break

case '2':

Binsrch(L2)

break

case '3':

page_title("二叉排序树查找")

printf("请输入要查找的关键字:")

scanf("%d",&k)

SearchBST(pt,k)

break

case '4':

HashSearch(ht)

break

case '0':

exit(0)

default :

printf("输入错误，按任意键返回")

getch()

}

goto menu

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte，而且用于记录规则的表大小会根据规则，大小可能是不定的。

通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。

一种比较直接的办法就是，将大小为M 的数组的每一个元素指向一个链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。下图很清楚的描述了什么是拉链法。

“John Smith”和“Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。

单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中（聚集），该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。当链表过长、大量的键都会映射到相同的索引上，哈希表的顺序查找会转变为链表的查找，查找时间将会变大。对于开放寻址会造成性能的灾难性损失。

实现基于拉链表的散列表，目标是选择适当的数组大小M，使得既不会因为空链表而浪费内存空间，也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于，这种数组大小M的选择不是关键性的，如果存入的键多于预期，那么查找的时间只会比选择更大的数组稍长。另外，我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期，索然有些浪费空间，但是查找速度就会很快。所以当内存不紧张时，我们可以选择足够大的M，可以使得查找时间变为常数，如果内存紧张时，选择尽量大的M仍能够将性能提高M倍。

线性探测法是开放寻址法解决哈希冲突的一种方法，基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。如下图所示：

对照前面的拉链法，在该图中，“Ted Baker” 是有唯一的哈希值153的，但是由于153被“Sandra Dee”占用了。而原先“Snadra Dee”和“John Smith”的哈希值都是152的，但是在对“Sandra Dee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以索引加1 把“Sandra Dee”存放在没有被占用的153上，然后想把“Ted Baker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)。

原文： 哈希查找 - 卖贾笔的小男孩 - 博客园 (cnblogs.com)

---