设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3

[单选题]

设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3...xk）满足H(x1)=H(x2)=...=H(xk).若用线性探测法将这K个关键字存入哈希表中，至少要探测（）次。

```
K-1
```
```
K
```
```
K+1
```
```
K(K-1)/2
```

张小头

线性探测法。当d，=0，1，2，m-1时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
线性探测法可能使第；个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+

1个散列地址的元素就争夺第1+2个散列地址的元素的地址…从而造成大量元素在相邻的散列地址上“聚集”（或堆积）起来，大大降低了查找效率。

题目的条件是H(x1)=H(x2)=...=H(xk)，所以经过散列函数都在同一个位置，所以每加入一个新元素，就要按顺序向后走，第一个探测0次，第k个探测k-1次，所以总共k(k-1)/2

发表于 2021-02-13 18:00:02 回复(0)