结构推理
按α=0.6把下面列出的关键码存入散列表中,按除余法定义散列函数h(k)。对于下面给出的所有的关键码值k,求出h(k)的值。用结合的同义词子表法解决碰撞,将全部关键码都依次存入散列表后的存储状况画出来。关键码集合为:850,880,709,247,983,323,407,552,411,123,200,150。
【正确答案】(1)因为n=12,α=0.6。所以基本区域长度取20。又因为19是小于20的最大素数,所以散列函数h(j)=k/%19。计算结果如下:
| 关键码k | h(k) |
| 850 | 10 |
| 880 | 0 |
| 709 | 9 |
| 247 | 7 |
| 983 | 3 |
| 323 | 3 |
| 407 | 7 |
| 552 | 12 |
| 411 | 11 |
| 123 | 3 |
| 200 | 0 |
| 150 | 10 |
(2)所谓结合同义词子表,是一种用拉链法处理碰撞的技术。其特点是把n个同义词组成的链表全部分配在基本区域之中。这种方法只有当负载因子小于等于1时才能使用,因为这时基本区域才能够存放下全部元素。另外,要求基本区域中每个结点都需要增加一个指针域。具体同义词空间的分配策略也可以很多,下面采用的是从基本区域末端向前查找,遇到第一个空闲结点就进行分配。例如关键码323与983碰撞时,基本区域的最后一个结点空间就分配给323。同时,在983的结点中用link把它们链接起来。
| 地 址 | key | link |
| 0 | 880 | 16 |
| 1 | | |
| 2 | | |
| 3 | 983 | 19 |
| 4 | | |
| 5 | | |
| 6 | | |
| 7 | 247 | 18 |
| 8 | | |
| 9 | 709 | ∧ |
| 10 | 850 | 15 |
| 11 | 411 | ∧ |
| 12 | 552 | ∧ |
| 13 | | |
| 14 | | |
| 15 | 150 | ∧ |
| 16 | 200 | ∧ |
| 17 | 123 | ∧ |
| 18 | 407 | ∧ |
| 19 | 323 | 17 |
【答案解析】