矢量沒有正確填充

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; 
} 

我期待我的矢量與100點的值來填充。它們中的每一個都是計算碰撞次數的計數值。但是，當我打印出來時，它只顯示我在矢量中有一個值。我究竟做錯了什麼？

編輯：我只是試圖存儲每次碰到碰撞所需的插入次數。因此，讓我們說第一次碰撞前需要6次插入，然後碰撞前需要5次插入，碰撞前需要4次插入..等等我想讓我的向量讀取6 5 4 ...

Answer 1

那是因爲該代碼：

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

打破上檢測到的第一碰撞for循環。所以你在resultVec中只有一個值被顯示。

編輯

我期待我的矢量與100點的值來填充。

當前的代碼不會這樣做。您隨機化並創建一個包含100個值的哈希值。然後當檢測到碰撞時，您只在resultVec中存儲碰撞計數器。從100個隨機化中有100個碰撞的概率是0.

用count=0;代替break;。它將打印碰撞之間的插入次數。換句話說，在下一次碰撞發生之前沒有碰撞的插入有多少。

EDIT2

萬一第一碰撞前的您正在尋找插入的數目，那麼你需要更換break與

count = 0; 
hashNumVec.clear(); 

你需要清除哈希向量以及計數器，因爲每次碰撞後你都希望從頭開始測量（否則計數器將顯示第二次碰撞之前的插入次數，然後第三次等......）

Answer 2

您的程序會檢查100次插入內是否發生碰撞。它沒有進行100次試驗，其中計算了實現碰撞所需的插入次數。要做到這一點，你需要一個二級循環：

for (int k = 0; k < 100; k++){ // 100 experiments 
    for(;;) { // Each experiment continues until the "break" statement in your else clause. 
     // The loop body, exactly as you currently have it written. 
    } 
    count = 0; // Reset for the next experiment! 
}