设一组关键字{19，1，23，14，55，20，84，27，68}，采用哈希函数 H(key)=key % 13，分别采用开放地址法的线性探测发及二次探测再散列方法解决冲突，试在0～12的散列地址空间中对该关键字序列构造哈希表，并分别求出平均查找长度。

采用哈希函数 H(key) = key % 13，将关键字序列{19，1，23，14，55，20，84，27，68}插入哈希表中。

### 开放地址法的线性探测法

对于哈希表中每个位置，其对应的值为该位置的关键字，若该位置已经被占用，则继续往后探测，直至找到空闲位置或者已经探测了整个哈希表为止。

插入过程如下：

key    H(key)    插入位置
19       6       6
1        1       1
23       10      10
14       1       2
55       3       3
20       7       7
84       1       4
27       1       5
68       7       8

得到的哈希表如下（- 表示该位置为空）：

0    1    2    3    4    5    6    7    8    9    10   11   12
-    1   14   55   84   27   19   20   68   -    23   -    -

平均查找长度为 (1+2+3+4+5+6+7+8+9+11)/10 = 4.6。

### 开放地址法的二次探测再散列法

若使用开放地址法的线性探测法会导致冲突较多，可以采用二次探测再散列法。即如果插入一个关键字时发生冲突，则将关键字插入到当前位置，同时向后探测的步长变为原步长的平方。

插入过程如下：

key    H(key)    插入位置
19       6       6
1        1       1
23       10      10
14       1       0
55       3       3
20       7       7
84       1       5
27       1       12
68       7       8

得到的哈希表如下（- 表示该位置为空）：

0    1    2    3    4    5    6    7    8    9    10   11   12
14   1    -    55   -    84   19   20   68   -    23   -    27

平均查找长度为 (1+2+3+4+5+6+7+8+9+11)/10 = 4.6。

综上所述，开放地址法的线性探测法和二次探测再散列法得到的平均查找长度相等。但是从上面的过程可以看出，在这个例子中使用二次探测再散列法的冲突次数较少，因此二次探测再散列法比线性探测法更适合这个例子。