7.6 哈希表查找
7.6 哈希表查找
7.6.1 哈希表查找的基本概念
在前面讨论的各种查找方法中，查找的过程都需要根据关键字进行若干次的比较判断，最后确定在数据表中是否存在关键字等于某个给定值的元素，以及该元素在数据表中的位置。在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字没有直接关系。如果在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无须做比较或只做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是哈希表查找的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，哈希表查找法又叫杂凑法或散列法。
例如，假设某个教室由40个坐位，如果不加限定让学生随便就座，则在查找学生时就要将待找学生与当前坐位上的学生一一比较，这就是前面介绍的查找方法的思路。而哈希表查找则要限定学生所坐的位置，比如，规定学生座位的编号与其学号的后两位相同，即学号为982608的学生应坐编号为08的座位。这样，我们要找到某个学生时只需根据其学号的末两位到相应座位上去找即可。在此例中，学生相当于记录，学号则为关键字，对关键字进行的操作则是取学号的末两位，用以确定记录的位置。
设置一个长度为m的表A，用一个函数H把数据集中的n个节点的关键字唯一地转换成0～m-1范围内的数值，即对于数据集中的任意节点的关键字ki，有：
0≤H(ki)≤m-1 （0≤i≤n-1）
这样就可以利用函数H将数据集中的元素映射到表A中，H(ki)便是ki在表中的存储位置。H是表与元素关键字之间映射关系的函数，称为哈希函数。
当然，可以用给定的关键字和所采用的哈希函数直接在给定的表中进行查找运算。然而，由于数据集中各元素关键字的取值可能在一个很大的范围内，所以即使当数据集中的元素个数不是很多时，也很难选取一个合适的哈希函数H()，它能保证对于任意不同的ki和kj，有H(ki)≠H(kj)。若ki≠kj，则H(ki)=H(kj)的现象称为冲突现象。
尽管冲突现象是难免的，但还是希望能找到尽可能产生均匀映射的哈希函数，从而尽可能地降低发生冲突的概率。另外，当发生冲突时，还必须有相应的解决冲突的方法。因此，构造哈希函数和建立解决冲突的方法是哈希表查找的两个主要任务。
7.6.2 哈希函数的构造方法
构造哈希函数的方法很多，但如何构造一个“好”的哈希函数是个具有很强的技术性和实践性的问题。这里的“好”指的是哈希函数的构造比较简单并且用此哈希函数产生的映射，发生冲突的可能性较小。换句话说，一个好的哈希函数能将给定的数据集均匀地映射在所给定的地址区间中。
关键字可以唯一地对应一个记录，因此，在构造哈希函数时，应尽可能地使关键字的各个成分都对它的哈希地址产生影响。下面介绍几种常用的构造哈希函数的方法。
1．直接地址法
直接地址法的哈希函数H，对于关键字是数值类型的数据直接利用关键字求得哈希地址。
H(ki)=aki+b （a、b为常量）
在使用时，为了使哈希地址与存储空间吻合，可以调整a和b。例如，取H(ki)=3*ki+5。
直接地址法的特点是哈希函数简单，并且对于不同的关键字，不会产生冲突。但在实际问题中，由于关键字集合中的元素很少是连续的，用该方法产生的哈希表会造成空间的大量浪费。因此，这种方法很少使用。
2．数字分析法
数字分析法是假设有一组关键字，每个关键字由n位数字组成，如k1k2…kn。数字分析法是从中提取数字分布比较均匀的若干位作为哈希地址。
例如，对于一组关键字k1～k8的序列{100011211,100011322,100011413,100011556,
100011613,100011756,100011822,100011911}，可以取第6位和第7位作为哈希地址，即H(k1)=12，H(k2)=13，H(k3)=14，H(k4)=15，H(k5)=16，H(k6)=17，H(k7)=18，H(k8)=19。
又假定已知可能出现的所有键值中的一部分如下：
0 0 1 3 1 9 4 2 1
0 0 1 6 1 8 3 0 9
0 0 1 7 3 9 4 3 4
0 0 1 6 4 1 5 1 6
0 0 1 8 1 6 3 7 8
0 0 1 1 4 3 3 9 5
0 0 1 2 4 2 3 6 3
0 0 1 9 1 5 4 0 9
…
不难看出，（左起）前3位分布不均匀，第5位和第7位也有很多重复，因此应将这5位丢弃。剩下的第4、6、8、9位都是分布较均匀的，可考虑将它们或其中几位组合起来作为散列地址。至于到底选择哪几位，需进一步考虑散列查找表的容量（即其中数据元素的最大数目）以及散列表组织形式。
数字分析法一般可以做到没有冲突，但如果事先不知道各关键字，则不能采用此方法。
3．除留余数法
除留余数法是用关键字ki除以一个合适的、不大于哈希表长m的正整数p所得余数作为哈希地址的方法。对应的哈希函数H(ki)为：
H(ki)=ki MOD p
其中，MOD表示求余数运算符。用该方法产生的哈希函数的好坏取决于p值的选取。实践证明，当p取小于哈希表长m的某个素数时，产生的哈希函数较好。
这一方法的关键在于p的选取，若p选的不好，容易产生同义词。实验证明，若选p为偶数，则所得的散列函数总是将奇数的关键字映射成奇数地址，把偶数的关键字映射为偶数地址，因而增加了冲突的机会。另外，若用素数或含有小素数因子的合数作为p，也会导致散列地址不均匀的后果。为了获得比较均匀的地址分布，通常选p为小于或等于散列表容量的最大素数。例如，当m=8，16，32，64时，相应的p最好为7，13，31，61。
除留余数法是一种简单且行之有效的构造哈希函数的方法。
4．平方取中法
平方取中法是取关键字平方的中间几位作为散列地址的方法，具体取多少位视实际情况而定。即：
H(ki)= ki的平方的中间几位
这也是一种常用的较好的设计哈希函数的方法。关键字求平方后使得它的中间几位和组成关键字的各位值均有关，从而使哈希地址的分布更为均匀，减少了发生冲突的可能性。
5．折叠法
折叠法首先将关键字分割成位数相同的几段（最后一段的位数可少一些），段的位数取决于哈希地址的位数，由实际情况而定，然后将它们的叠加和舍去最高进位作为哈希地址的方法。
例如，假设关键字为某人的身份证号码420700781027815，则可以用4 位为一组进行叠加，即有7815+8102+7007+420=23344，舍去高位，则有：
F(420700781027815)=23344
为该身份证号码关键字的散列地址。
与平方取中法类似，折叠法也使得关键字的各位值都对哈希地址产生影响。
7.6.3 哈希冲突的解决方法
在哈希表中，发生冲突在所难免，这主要与3个因素有关：
（1）与装填因子a有关。所谓装填因子，是指哈希表中已存入的记录数n与哈希地址空间大小m的比值，即a= 
。a越小，冲突的可能性就越小；a越大（最大可取1），冲突的可能性就越大。这很容易理解，因为a越小，哈希表中空闲单元的比例就越大，所以待插入记录与已插入存在的记录发生冲突的可能性就越小；反之，a越大，哈希表中空闲单元的比例就越小，所以待插入记录与已插入存在的记录冲突的可能性就越大。此外，a越小，存储空间的利用率就越低；反之，存储空间的利用率也就越高。为了兼顾减少冲突的发生和提高存储空间的利用率这两个方面，通常使最终的a控制在0.6～0.9的范围内。
（2）与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。
（3）与解决冲突的哈希冲突函数有关。哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。
下面介绍几种常用的解决哈希冲突的方法。
1．开放地址法
开放地址法又分为线性探测再散列、二次探测再散列和随机探测再散列。
假设哈希表空间为A[0]～A[m-1]，哈希函数为H(ki)。
（1）线性探测再散列。
线性探测再散列解决冲突求“下一个”地址的公式是：
d1=H(ki)
dj=(dj-1+1) MOD m j=2，3，…
例如，表长为14的散列表中已有关键字分别为17，57，19的记录（F(key)=key mod 13），如图7-15（a）所示。现在有第4条记录，其关键字为43，由散列函数得到的散列地址为4，产生冲突。若用线性探查法探查，得到下一个地址为5，仍然冲突；再探查到下一个地址为6，仍冲突；直到探查到散列地址为7的位置是空时为止，处理冲突的过程结束，记录填入散列表中序号为7的位置，如图7-15（b）所示。
（2）二次探测再散列。
二次探测再散列解决冲突求“下一个”地址的公式是：
d1=H(ki)
d2j=(d1+j2 ) MOD m
d2j+1=(d1-j2) MOD m j=1，2，…
该方法在发生冲突时，将同义词来回散列在冲突地址的两端。其缺点是不易探查到整个散列表空间。
对上例用二次探查法探查到散列地址如图7-15（c）所示。
（3）随机探测再散列。
随机探测再散列解决冲突求“下一个”地址的公式是：
d1=H(ki)
dj+1=(d1+R) MOD m
其中，
伪随机序列为R1，R2，……
伪随机公式为Ri+1=(aRi+p) MOD q a、p和q均为常量
该方法探查散列地址取决于得到的随机数列，若随机数列为2，5，……，则第一次探查得到的散列地址为6，仍然发生冲突；第二次探查到的散列地址为9，该位置为空，可将记录填入地址序号为9的空间中，如图7-15（d）所示。
图7-15 用开放地址法处理冲突示例
【例7-5】设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，采用哈希函数为H(key)=
key % 13。采用开放地址法的线性探测再散列方法解决冲突。在0～18的散列地址空间中对该关键字序列构造哈希表。并求等概率情况下查找成功时的平均查找长度。
解：m=19，线性探测再散列下一地址的计算公式为：
d1=H(ki)
dj=(dj-1+1) MOD m j=2，3，…
其计算过程如下：
H(19)=19 MOD 13=6 /*检测1次*/
H(01)=1 MOD 13=1 /*检测1次*/
H(23)=23 MOD 13=10 /*检测1次*/
H(14)=14 MOD 13=1 /*冲突*/
H(14)=(1+1) MOD 19=2 /*检测2次*/
H(55)=55 MOD 13=3 /*检测1次*/
H(20)=20 MOD 13=7 /*检测1次*/
H(84)=84 MOD 13=6 /*冲突*/
H(84)=(6+1) MOD 19=7 /*仍冲突*/
H(84)=(7+1) MOD 19=8 /*检测3次*/
H(27)=27 MOD 13=1 /*冲突*/
H(27)=(1+1) MOD 19=2 /*冲突*/
H(27)=(2+1) MOD 19=3 /*仍冲突*/
H(27)=(3+1) MOD 19=4 /*检测4次*/
H(68)=68 MOD 13=3 /*冲突*/
H(68)=(3+1) MOD 19=4 /*仍冲突*/
H(68)=(4+1) MOD 19=5 /*检测3次*/
H(11)=11 MOD 13=11 /*检测1次*/
H(10)=10 MOD 13=10 /*冲突*/
H(10)=(10+1) MOD 19=11 /*仍冲突*/
H(10)=(11+1) MOD 19=12 /*检测3次*/
H(77)=77 MOD 13=12 /*冲突*/
H(77)=(12+1) MOD 19=13 /*检测2次*/
对应的哈希表如图7-16所示。在查找哈希表时，一个关键字对应的探查次数就是成功找到该记录所需的比较次数，因此，等概率情况下，本哈希表查找成功时的平均查找长度如下：
图7-16 哈希表
对于本例给定的条件，构造和输出哈希表的算法如下：
typedef struct
{
KeyType key; /*关键字值*/
int si; /*探查次数*/
} HashTable; /*哈希表元素类型*/
void CreateHT(HashTable ht[],KeyType a[],int n,int m,int p)/*构造哈希表*/
{
int i,d,cnt;
for(i=0;i<m;i++) /*置初值*/
{
ht[i].key=0;
ht[i].si=0;
}
for(i=0;i<n;i++)
{
cnt=1; /*累计探查次数*/
d=a[i]%p;
if(ht[d].key==0)
{
ht[d].key=a[i];
ht[d].si=cnt;
}
else
{
do /*处理冲突*/
{
d=(d+1)%m;
cnt++;
} while(ht[d].key!=0);
ht[d].key=a[i];
ht[d].si=cnt;
}
}
}
void DispHT(HashTable ht[],int n,int m) /*输出哈希表*/
{
int i;
double avg;
printf("i: ");
for(i=0;i<m;i++)
printf("%-3d",i);
printf("\n");
printf("key:");
for(i=0;i<m;i++)
printf("%-3d",ht[i].key);
printf("\n");
printf("si: ");
for(i=0;i<m;i++)
printf("%-3d",ht[i].si);
printf("\n");
avg=0;
for(i=0;i<m;i++)
avg+=ht[i].si;
avg=avg/n;
printf("平均查找长度:ASL(%d)=%g\n",n,avg);
}
设计如下主函数：
void main()
{
HashTable ht[MaxSize];
KeyType a[]={19,1,23,14,55,20,84,27,68,11,10,77};
int n=12,m=19,p=13;
CreateHT(ht,a,n,m,p);
DispHT(ht,n,m);
}
本程序的执行结果如下：
|
i: |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
key: |
0 |
1 |
14 |
55 |
27 |
68 |
19 |
20 |
84 |
0 |
23 |
11 |
10 |
77 |
0 |
0 |
0 |
0 |
0 |
|
si: |
0 |
1 |
2 |
1 |
4 |
3 |
1 |
1 |
3 |
0 |
1 |
1 |
3 |
2 |
0 |
0 |
0 |
0 |
0 |
|
平均查找长度:ASL(12)=1.91667 | |||||||||||||||||||
2．链地址法
|
图7-17 用链地址处理冲突时的散列表 |
例如，有5个关键字：16，7，1，5，19。取散列表长为m=7，散列函数为：
H(key)=key mod 7
用链地址法解决冲突所构造出来的散列表，如图7-17所示。
【例7-6】 线性表的关键字集合{87,25,310,08,27,132,68,95,187,123,70,63,47}，已知散列函数为：
H(ki) = ki MOD 13
采用拉链法处理冲突。设计出这种链表结构，并求等概率情况下查找成功的平均查找长度。
解：构造哈希表的过程如下。
H(87)=87 MOD 13=9
H(25)=25 MOD 13=12
H(310)=310 MOD 13=11
H(08)=08 MOD 13=8
H(27)=27 MOD 13=1
H(132)=132 MOD 13=2
H(68)=68 MOD 13=3
H(95)=95 MOD 13=4
H(187)=187 MOD 13=5
H(123)=123 MOD 13=6
H(70)=70 MOD 13=5
H(63)=63 MOD 13=11
H(47)=47 MOD 13=8
采用链地址法处理冲突的链表如图7-18所示。
图7-18 处理冲突的链表
对于每个单链表，成功查找时，第一个节点需比较1次，第二个节点需比较2次，……。因此，等概率情况下，成功查找的平均查找长度如下：
对于本例给定的条件，构造和输出哈希表的算法如下：
typedef struct node
{
KeyType key; /*关键字值*/
int si; /*探查次数*/
struct node *next;
} Node; /*数据节点类型*/
typedef struct
{
Node *link;
} HNode; /*头节点类型*/
void CreateHT(HNode *ht[],KeyType a[],int n,int p) /*构造哈希表*/
{
int i,d,cnt;
Node *s,*q;
for(i=0;i<p;i++) /*所有头节点的link域置空*/
{
ht[i]=(HNode *)malloc(sizeof(HNode));
ht[i]->link=NULL;
}
for(i=0;i<n;i++)
{
cnt=1;
s=(Node *)malloc(sizeof(Node)); /*构造一个数据节点*/
s->key=a[i];s->next=NULL;
d=a[i]%p; /*求其哈希地址*/
if(ht[d]->link==NULL)
{
ht[d]->link=s;
s->si=cnt;
}
else
{
q=ht[d]->link;
while(q->next!=NULL)
{
q=q->next;cnt++;
}
cnt++;
s->si=cnt;q->next=s;
}
}
}
void DispHT(HNode *ht[],int n,int p) /*输出哈希表*/
{
int i,sum=0;
Node *q;
printf("哈希表:\n");
for(i=0;i<p;i++)
{
q=ht[i]->link;
printf("%d:link->",i);
while(q!=NULL)
{
sum+=q->si;
printf("[%d,%d]->",q->key,q->si);
q=q->next;
}
printf("∧\n");
}
printf("平均查找长度:ASL=%g\n",1.0*sum/n);
}
设计如下主函数：
void main()
{
HNode *ht[MaxSize];
KeyType a[]={87,25,310,8,27,132,68,95,187,123,70,63,47};
int n=13,p=13;
CreateHT(ht,a,n,p);
DispHT(ht,n,p);
}
本程序的执行结果如下：
哈希表:
0:link->∧
1:link->[27,1]->∧
2:link->[132,1]->∧
3:link->[68,1]->∧
4:link->[95,1]->∧
5:link->[187,1]->[70,2]->∧
6:link->[123,1]->∧
7:link->∧
8:link->[8,1]->[47,2]->∧
9:link->[87,1]->∧
10:link->∧
11:link->[310,1]->[63,2]->∧
12:link->[25,1]->∧
平均查找长度:ASL=1.23077
与开放地址法相比，链地址法有如下几个优点：
（1）链地址法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短。
（2）由于链地址法中各链表上的记录空间是动态申请的，因此，更适合于造表前无法确定表长的情况。
（3）开放地址法为减少冲突要求装填因子a较小，因此，当数据规模较大时会浪费很多空间，而链地址法中可取a≥1，且记录较大时，链地址法中增加的指针域可忽略不计，因此节省了空间。
（4）在用链地址法构造的哈希表中，删除记录的操作易于实现，只要简单地删去链表上相应的记录即可。而对开放地址法构造的哈希表，删除记录不能简单地将被删记录的空间置为空，否则将截断在它之后填入哈希表的同义词记录的查找路径，这是因为各种开放地址法中，空地址单元（即开放地址）都是查找失败的条件。因此，在用开放地址法处理冲突的哈希表上执行删除操作，只能在被删记录上做删除标记，不能真正删除记录。
链地址法也有缺点：指针需要额外的空间，因此，当记录规模较小时，开放地址法较为节省空间。而若将节省的指针空间用来扩大哈希表的规模，则可使装填因子变小，这又降低了开放地址法中的冲突的概率，从而提高了平均查找速度。
3．性能分析法
查找成功时的平均查找长度是指查找到表中已有表项的平均探查次数，它是找到表中各个已有表项的探查次数的平均值；而查找不成功的平均查找长度是指在表中查找不到待查的表项，但可找到插入位置的平均探查次数，它是表中所有可能散列的位置上要插入新元素时，为找到空位置的探查次数的平均值。表7-2列出了用几种不同的方法解决冲突时哈希表的平均查找长度。
表7-2 用几种不同的方法解决冲突时哈希表的平均查找长度
|
解决冲突的方法 |
平均查找长度 | |
|
成功的查找 |
不成功的查找 | |
|
线性探查法 |
|
|
|
平方探查法 |
|
|
|
链地址法 |
|
|
从表中看到，哈希表的平均查找长度不是对象个数n的函数，而是装填因子a的函数。因此，在设计哈希表时可选择a控制哈希表的平均查找长度。
下面给出一个完整的程序实例：
/*哈希法: 使用链接表处理碰撞*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#define MAX_NUM 100 /*最大数据个数*/
#define PRIME 97 /*MAX_NUM的质数*/
#define NOTEXISTED NULL
/*定义数据结构*/
typedef struct Person
{
long id;
char name[21];
struct Person *link;
} Student;
/*建立哈希表*/
Student *Hashtab[MAX_NUM];
/*函数原型声明*/
long hashfun(long);
void insert();
void del();
Student *search(Student *,Student *);
void query();
void show();
void main()
{
char *menu_prompt=
"=== Hashing Table Program==\n"
" 1. Insert\n"
" 2. Delete\n"
" 3. Show\n"
" 4. Search\n"
" 5. Quit\n"
"Please input a number: ";
char menusele;
int i;
/*起始哈希表，将各链表指向NULL*/
for(i=0;i<MAX_NUM;i++)
Hashtab[i] = NULL;
do
{
printf("%s",menu_prompt);
menusele=toupper(getche());
puts("");
switch (menusele)
{
case '1' :
insert();
break;
case '2' :
del();
break;
case '3' :
show();
break;
case '4' :
query();
break;
case '5' :
puts("Bye Bye ^_^");
break;
default :
puts("Invalid choice !!");
}
} while(menusele !='5');
}
/*哈希函数:*/
/*以除法运算求出记录应存储的位置*/
long hashfun(long key)
{
return(key % PRIME);
}
void insert()
{
Student *newnode;
long index;
/*输入记录*/
newnode=(Student *)malloc(sizeof(Student));
newnode->link=NULL;
printf("Enter id : ");
scanf("%ld",&newnode->id);
printf("Enter Name : ");
scanf("%s",newnode->name);
/*利用哈希函数求得记录地址*/
index=hashfun(newnode->id);
/*判断该链表是否为空，若为空则建立链接表*/
if(Hashtab[index]==NULL )
{
Hashtab[index]=newnode;
printf("Node insert ok!\n");
}
else
{
/*查找节点是否已存在表中，如未存在，则将此节点插入表前端*/
if((search(Hashtab[index],newnode))==NOTEXISTED)
{
newnode->link=Hashtab[index];
Hashtab[index]=newnode;
printf("Node insert ok!\n");
}
else
printf("Record existed...\n");
}
}
/*删除节点函数*/
void del()
{
Student *node,*node_parent;
long index;
node=(Student *)malloc(sizeof(Student));
printf("Enter ID : ");
scanf("%ld",&node->id);
/*利用哈希函数转换记录地址*/
index=hashfun(node->id);
/*搜索节点是否存在，并返回指向该节点的指针*/
node=search(Hashtab[index],node);
if(node==NOTEXISTED)
printf("Record not existed...\n");
else
{
/*如节点为表首，则将表指向NULL，否则找到其父节点，并将父节点link指向节点后端*/
printf("ID : %ld Name : %s\n",node->id,node->name);
printf("Deleting record...\n");
if(node==Hashtab[index])
Hashtab[index]=NULL;
else
{
node_parent=Hashtab[index];
while(node_parent->link->id !=node->id)
node_parent=node_parent->link;
node_parent->link=node->link;
}
free(node);
}
}
/*查找节点函数，如找到节点则返回指向该节点的指针，否则返回NULL*/
Student *search(Student *linklist,Student *Node)
{
Student *ptr=linklist;
while (ptr->id !=Node->id && ptr->link !=NULL)
ptr=ptr->link;
if(ptr==NULL)
return NOTEXISTED;
else
return ptr;
}
/*查询节点函数*/
void query()
{
Student *query_node;
long index;
query_node=(Student *)malloc(sizeof(Student));
printf("Enter ID : ");
scanf("%ld",&query_node->id);
index=hashfun(query_node->id);
/*搜索节点*/
query_node=search(Hashtab[index],query_node);
if(query_node==NOTEXISTED )
printf("Record not existed...\n");
else
{
printf("ID : %ld Name : %s\n",
query_node->id,query_node->name);
}
}
/*显示节点函数，从哈希表一一寻找是否有节点存在*/
void show()
{
int i;
Student *ptr;
puts("ID NAME");
puts("------------------------");
for(i=0;i<MAX_NUM;i++)
{
/*表不为空，则显示整张表*/
if(Hashtab[i] !=NULL)
{
ptr=Hashtab[i];
while(ptr)
{
printf("%-5ld %15s\n",ptr->id,ptr->name);
ptr=ptr->link;
}
}
}
}
上述程序的输出结果为：
=== Hashing Table Program ===
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 1
Enter id :
43
Enter Name : John
Node insert ok!
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 1
Enter id :
452
Enter Name : Mary
Node insert ok!
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 1
Enter id : 591
Enter Name : Tom
Node insert ok!
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 1
Enter id : 459
Enter Name : Joe
Node insert ok!
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 3
ID NAME
------------------------
591 Tom
43 John
452 Mary
459 Joe
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 2
Enter ID : 43
ID : 43 Name : John
Deleting record....
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 3
ID NAME
------------------------
591 Tom
452 Mary
459 Joe
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 4
Enter ID : 591
ID : 591 Name : Tom
=== Hashing Table Program ==
1. Insert
2. Delete
3. Show
4. Search
5. Quit
Please input a number : 5
Bye Bye ^_^