Как я могу посчитать количество коллизий в хеш-таблице? - PullRequest
Новая
       9

Как я могу посчитать количество коллизий в хеш-таблице?

4 голосов
/ 05 декабря 2011

Моя функция вставки уже правильно обрабатывает коллизии, но я хочу иметь возможность подсчитывать количество коллизий в каждом отдельном способе хеширования (связывание, линейное зондирование и квадратичное зондирование). Как мне это сделать?

Это мой код: 

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

1 Ответ

6 голосов
/ 05 декабря 2011

Можно иметь саму хеш-таблицу, сообщающую о количестве обнаруженных коллизий, вообще не раскрывая ее внутреннюю реализацию.

Для хеш-таблиц, в которых используется зондирование (любого типа), количество коллизий равно количеству элементов, размещенных в индексе, не совместимом с их хэш-кодом (то есть потому, что позиция, в которой они обычно хранятся, уже была занято).

Для хеш-таблиц, в которых используется сцепление, количество коллизий равно количеству элементов в хеш-таблице за вычетом количества занятых сегментов (другими словами, считайте все вставленные элементы, кроме первого в каждом блоке). Это также довольно интуитивно понятно.

То, что я бы сделал на вашем месте, - это дал бы каждой хеш-таблице метод count_colissions(), который вычисляет количество коллизий за O (n) раз, используя соответствующий метод, и возвращает его.

...