【简答题】在采用线性探测再散列方法处理冲突的散列表中，同义词（即散列地址相同的关键字值）在散列表中的位置一定是相邻的，这种说法正确吗？为什么？

【简答题】在采用线性探测再散列方法处理冲突的散列表中，同义词（即散列地址相同的关键字值）在散列表中的位置一定是相邻的，这种说法正确吗？为什么？

这种说法不正确。在线性探测再散列中，同义词（散列地址相同的关键字）的存储位置不一定相邻，可能因非同义词的插入而被间隔。

线性探测的冲突处理逻辑是：当关键字 $k$ 的初始散列地址 $h(k)$ 被占用时，依次探测 $h(k)+1, h(k)+2, \dots$ 直至找到空位置。若插入过程中存在非同义词占用了同义词序列的中间位置，后续同义词将被迫存储在更远的空单元，导致相邻同义词被间隔。

例如，设散列函数为 $h(k) = k \mod 10$，现有同义词 $k_1=10$（$h=0$）、$k_2=20$（$h=0$）、$k_3=30$（$h=0$），以及非同义词 $k_4=11$（$h=1$）。插入顺序如下：

$k_1$ 插入位置 0；

$k_2$ 冲突，探测 1 后插入位置 1（此时 $k_1$ 与 $k_2$ 相邻）；

$k_4$ 散列地址 1 冲突，探测 2 后插入位置 2（非同义词占用中间位置）；

$k_3$ 散列地址 0 冲突，依次探测 1（被 $k_2$ 占用）、2（被 $k_4$ 占用），最终插入位置 3。

结果，同义词 $k_2$（位置 1）与 $k_3$（位置 3）被非同义词 $k_4$（位置 2）间隔，三者位置为 0、1、3，显然不全部相邻。

因此，线性探测中同义词的相邻性仅在无其他非同义词插入间隔时成立，并非必然结果。这一现象也导致了线性探测的“聚集效应”——冲突会像多米诺骨牌一样蔓延，降低查找效率。