一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...
如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?
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 |
|
刘丽 |
刘宏英 |
吴军 |
吴小艳 |
李秋梅 |
陈伟 |
... |
姓名中各字拼音首字母 |
ll |
lhy |
wj |
wxy |
lqm |
cw |
... |
用所有首字母编号值相加求和 |
24 |
46 |
33 |
72 |
42 |
26 |
... |
最小值可能为3 最大值可能为78 可放75个学生 |
用上述得到的数值作为对应记录在表中的位置,得到下表:
|
|
成绩一 |
成绩二... |
3 |
... |
|
|
... |
... |
|
|
24 |
刘丽 |
82 |
95 |
25 |
... |
|
|
26 |
陈伟 |
|
|
... |
... |
|
|
33 |
吴军 |
|
|
... |
... |
|
|
42 |
李秋梅 |
|
|
... |
... |
|
|
46 |
刘宏英 |
|
|
... |
... |
|
|
72 |
吴小艳 |
|
|
... |
... |
|
|
78 |
... |
|
|
上面这张表即哈希表。
如果将来要查李秋梅的成绩,可以用上述方法求出该记录所在位置:
李秋梅:lqm 12 17 13=42 取表中第42条记录即可。
问题:如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录?
这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。