ハッシュテーブルの衝突数をどのように数えることができますか？

Question

私のinsert関数はすでに衝突を正しく処理していますが、私は、それぞれ異なるハッシュ方法（連鎖、線形プロービング、二次プロービング）で衝突数を数えたいと思っています。これをどうやってやるの？

この今のところ私のコード：

#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 
#include <iterator> 
#include <ctime> 
#include "Chaining.h" 
#include "QuadraticProbing.h" 
#include "LinearProbing.h" 

using namespace std; 

int main() 
{ 
    int collision_count = 0; 
    float diff = 0.0; 
    clock_t tStart, tStop; 
    string ITEM_NOT_FOUND = "ITEM_NOT_FOUND"; 
    std::vector<std::string> DataArray; 
    std::copy(std::istream_iterator<std::string>(std::ifstream("OHenry.txt")),istream_iterator<string>(),back_inserter(DataArray)); 
    std::vector<std::string> QueryArray; 
    std::copy(std::istream_iterator<std::string>(std::ifstream("queries.txt")),istream_iterator<string>(),back_inserter(QueryArray)); 

    cout << "Testing chaining probing...\n"; 
    HashTable_chaining ChainingHT(ITEM_NOT_FOUND, 101); 
    int i = 0; 
    double average_c = 0.0; 
    double total_c = 0.0; 
    double temp_c = 0.0; 
    while(i != DataArray.size()) 
    { 
     tStart = clock(); 
     ChainingHT.insert(DataArray[i]); 
     tStop = clock(); 
     total_c = tStop - tStart; 
     temp_c = total_c + temp_c; 
     average_c = total_c/DataArray.size(); 
     if(DataArray[i] != DataArray[NULL]) 
     { 
      collision_count++; 
     } 
     i++; 
    } 

    cout<<"The number of collisions using Chaining is: "<<collision_count<<endl; 
    cout<<"The average time per insertion using Chaining is: "<<average_c<<endl; 
    system("pause"); 
    // Quadratic Probing 
    cout << "Testing quadratic probing...\n"; 
    HashTable_chaining QuadraticProbingHT(ITEM_NOT_FOUND, 101); 
    int j = 0; 
    int collision_count_quadratic = 0; 
    double average_qp = 0; 
    while(j != DataArray.size()) 
    { 
     clock_t tStartq = clock(); 
     QuadraticProbingHT.insert(DataArray[j]); 
     if(DataArray[j] != DataArray[NULL]) 
     { 
      collision_count_quadratic++; 
     } 
     j++; 
     average_qp = (((double)(clock() - tStartq)/CLOCKS_PER_SEC) + average_qp)/DataArray.size(); 

    } 
    cout<<"The number of collisions using Quadratic is: "<<collision_count<<endl; 
    cout<<"The average time per insertion using Quadratic is: "<<average_qp<<endl; 

Answer 1

ハッシュテーブル自体は、それがすべてでその内部実装を公開せずに見ているcolissionsの数を報告することが可能です。

（任意の種類の）プロービングを使用するハッシュテーブルの場合、colissionsの数は、インデックスに配置された要素の数がハッシュコードと一致しない場合（つまり、通常格納されていた位置がすでに占有されている）。

連鎖を使用するハッシュテーブルの場合、照合の数はハッシュテーブル内のアイテムの数から占有されたバケットの数を差し引いたものになります（つまり、各バケットの最初のアイテムを除くすべての挿入アイテムをカウントします）。これも非常に直感的です。

だから私はあなたの靴の中で、対応するメソッドを使ってO（n）時間にcolissionsの数を計算し、それを返すcount_colissions()メソッドを各ハッシュテーブルに与えます。