求出key中各值查找成功时的查找次数；求出key中各值查找成功时的查找次数；

根据线性探测再散列的方法，当查找一个关键字时，如果发现该位置为空，则说明该关键字不存在于哈希表中；如果该位置不为空，则需要判断该位置上的关键字是否与待查找的关键字相等。如果相等，则查找成功；否则需要继续往后查找，直到找到空位置或者找到相等的关键字为止。因此，查找一个关键字的查找次数是不确定的，取决于该关键字的位置以及后续的探测次数。

根据上述构造哈希表的过程，可以得到各个关键字在哈希表中的位置，以及查找成功时的查找次数如下：

|关键字|地址|查找次数|
|-|-|-|
|37|2|1|
|12|5|1|
|28|0|1|
|55|6|1|
|20|3|1|
|39|4|1|
|9|2|2|

其中，9 的地址为 2，但是 2 的位置已经被 37 占用，因此需要继续往后查找，直到找到空位置。因此，查找 9 的过程中需要查找两次。

相关问题

cpp 查找哈希表中是否存在某个key值

在 C++ 中查找哈希表中是否存在某个 key 值，可以使用 unordered_map 的 find() 函数或者 count() 函数。

使用 find() 函数的方法如下所示：

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_map<int, std::string> mymap = {
        {1, "apple"},
        {2, "banana"},
        {3, "orange"},
        {4, "pear"},
    };

    auto it = mymap.find(2); // 查找键值为 2 的元素

    if (it != mymap.end()) { // 如果找到了
        std::cout << "key 2 found" << std::endl;
    } else {
        std::cout << "key 2 not found" << std::endl;
    }

    return 0;
}

这里使用 unordered_map 的 find() 函数查找键值为 2 的元素，如果找到了，则输出 "key 2 found"；否则输出 "key 2 not found"。

另外，也可以使用 count() 函数来判断哈希表中是否存在某个 key 值，方法如下所示：

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_map<int, std::string> mymap = {
        {1, "apple"},
        {2, "banana"},
        {3, "orange"},
        {4, "pear"},
    };

    if (mymap.count(2)) { // 如果键值为 2 的元素存在
        std::cout << "key 2 found" << std::endl;
    } else {
        std::cout << "key 2 not found" << std::endl;
    }

    return 0;
}

这里使用 unordered_map 的 count() 函数判断键值为 2 的元素是否存在，如果存在，则输出 "key 2 found"；否则输出 "key 2 not found"。注意，count() 函数返回的是键值为 key 的元素的个数，因为在 unordered_map 中，每个键值对的 key 是唯一的，因此如果存在键值为 key 的元素，count() 函数返回的值肯定是 1。

线性表的关键字集合key = { 37，12，28，55，20，39，9 }，构造哈希表，表长为7（范围0~6），选取哈希函数的方法为“除留余数法”：H ( key ) = key % 7，解决冲突方法为“线性探测再散列”，请按上述条件： （1）求出key中各值的地址，画出相应的哈希表；（2）求出key中各值查找成功时的查找次数

(1) 根据哈希函数H(key) = key % 7，可以得到key中各值的地址：

37 -> H(37) = 2

12 -> H(12) = 5

28 -> H(28) = 0

55 -> H(55) = 6

20 -> H(20) = 6 （冲突，线性探测再散列，H(20) = (H(20)+1) % 7 = 0）

39 -> H(39) = 4

9 -> H(9) = 2 （冲突，线性探测再散列，H(9) = (H(9)+1) % 7 = 3）

根据上述地址，可以画出哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| - | - | - | - | - | - | - |
|28 | |37 | 9 |39 |12 |55 |
|20 | | | | | | |

(2) 查找成功的平均查找次数为：

(1+1+1+2+1+1+2)/7 = 1.29

其中，37、12、28、55、39、9都只需要进行一次查找即可找到，平均查找次数为1；而20需要进行两次查找才能找到，平均查找次数为2。