HashTable

creatory

HashTable
一般的线性表中记录的位置是随机的，不具有确定的关系，因此查找时需要从头到尾依次比较，比较浪费时间。而如果能找到一种方
法，使得要查找记录的关键字与存储位置之间映射一个对应的关系,这样查找效率就大大提高。
哈希表举例：
以学生学号为关键字建立哈希表检索学生成绩
我们采用下面的设计方法:
1.学号与位置一一对应
第1个位置存储1号学生成绩
第2个位置存储2号学生成绩
... ...
第n个位置存储n号学生成绩
2.对姓名中的拼音首字母编号
a b c d e  f  g h i  j     k   l    m  n   o    p    q    r    s    t    u    v    w  x     y    z  
1 2 3 4 5 6 7 8 9 10 11  12 13 14  15 16  17  18 19  20 21 22  23 24  25 26
根据上面2个假设的条件，得到如下对应关系
姓名   刘丽 刘宏英 吴军 吴小艳 陈伟
姓名中各拼音首字母  ll lhy wj wxy cw
姓名中各拼音首字母之和 24 46 33 72 26
最小值可能为3(1+2=3)
最大值可能为78(26+26+26=78)
可存放78-3=75个学生的信息
用以上得到的信息构造以下成绩哈希表
===================================================
学号 姓名 数学成绩  英语成绩
..
24 刘丽 89  98
..
26 陈伟 78  87
..
33 吴军 34  87
..
46 刘宏伟 56  87
..
72 吴小艳 45  57
====================================================
如果要查吴军的英语成绩，可用如下方法：
1.吴军的姓名中各拼音首字母 wj
2.w=23 j=10
23+10=33
3.取出哈希表中的第33条记录,取第二个成绩即可
据此，我们可以定义一个哈希函数
unsigned int hashFunc(const char *name);
直接传入姓名，经过哈希函数映射后返回一个记录号，这样就可以直接在表中查找了.


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u1/56374/showart_2119725.html