c++ - vector 未正确填充

Question

我试图使用线性探测公式(h(k) = k%T，其中 T 是表大小)计算指定大小的哈希表中发生冲突之前的平均插入次数。我正在做 100 个“实验”来计算碰撞前的平均插入次数。下面是我为 23 号表编写的代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>

using namespace std;


int main()
{
    int sizeArray[7] = { 7, 11, 13, 17, 19, 23, 29 }; // ignore for now
    double resultArray[7] = { 0 }; // ignore for now
    vector<double> hashNumVec; // stores hash keys
    int hashValue = 0;
    int count = 0;
    double average;
    vector<double> resultVec;
    int randNum; 

    srand(time(NULL));

    for (int k = 0; k < 100; k++){ // 100 experiments

        randNum = rand() % 100 + 1; // generate random number
        hashValue = (randNum) % 23; // hash value for T = 23


        vector<double>::iterator it;
        it = find(hashNumVec.begin(), hashNumVec.end(), hashValue);

        if (it == hashNumVec.end()){  //no collision

            count++;
            hashNumVec.push_back(hashValue);

        }
        else 
        {
            resultVec.push_back(count); // add the amount of insertions to vector
            break;
        }


    }


    for (auto i = resultVec.begin(); i != resultVec.end(); ++i)
        cout << *i << ' ';


    return 0;
}

我希望我的 vector 填充 100 个值。它们中的每一个都将是发生碰撞所需的插入次数的计数值。但是当我打印出来时，它只显示我在 vector 中有一个值。我做错了什么？

编辑:我只是想存储每次发生碰撞所需的插入次数。所以假设第一次在碰撞前需要 6 次插入，然后在碰撞前需要 5 次插入，在碰撞前需要 4 次插入......等等我希望我的 vector 读取 6 5 4 ...

Answer 1

那是因为那段代码:

    {
        resultVec.push_back(count); // add the amount of insertions to vector
        break;
    }

它会在第一次检测到碰撞时中断 for 循环。所以你在 resultVec 中只有一个值被显示。

编辑

I am expecting my vector to populate with 100 values.

目前的代码不会这样做。您随机化并创建一个包含 100 个值的散列。然后，当检测到碰撞时，您只将碰撞计数器存储在 resultVec 中。 100 次随机化中发生 100 次碰撞的概率为 0。

将 break; 替换为 count=0;。它将打印碰撞之间的插入次数。换句话说，在下一次碰撞发生之前，有多少没有碰撞的插入。

EDIT2

如果您要查找第一次 碰撞之前的插入次数，那么您需要将break 替换为

count = 0;
hashNumVec.clear();

您需要清除散列 vector 和计数器，因为每次碰撞后您都希望从头开始测量(否则计数器将显示第二次碰撞之前的插入次数，然后是第三次，依此类推。 .)