我如何計算散列表中的衝突數？

Question

我的插入函數已經正確處理了碰撞，但是我希望能夠計算每個不同哈希方式（鏈接，線性探測和二次探測）中的碰撞次數。我將如何去做這件事？

這是我到目前爲止的代碼：

#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的數量等於哈希表中的項目數量減去佔用的bucket數量（換句話說，計算除了每個bucket中的第一個項目之外的所有插入項目）。這也很直觀。

因此，我會在你的鞋子中做的每個散列表一個count_colissions()方法，它使用相應的方法計算O（n）時間內的聚集數並返回它。