HashTable

// 39241.sdizo.lab06.main.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
#include "cstdlib"
#include "time.h"
#include "fstream"
#include "HashTable.h"

using namespace std;

int main()
{
    srand(time(NULL));

    clock_t start, stop;
    double time_spent;

    fstream file;
    file.open("inlab06.txt", ios::in);
    if (!file.good()) return -1;

    int X;
    int k1, k2, k3, k4;

    file >> X;
    file >> k1;
    file >> k2;
    file >> k3;
    file >> k4;

    start = clock();
    HashTable lP(false);
    lP.deleteKey(k1);
    lP.add(k1);
    lP.display(0, 100);
    lP.addFew(X);
    lP.display(0, 100);
    lP.add(k2);
    lP.add(k3);
    lP.add(k4);
    lP.display(0, 100);
    lP.display(500, 600);
    lP.deleteKey(k3);
    lP.deleteKey(k4);
    lP.display(0, 100);
    lP.display(500, 600);
    stop = clock();
    time_spent = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "Czas wykonania dla metody adresowania liniowego: " << time_spent << "s.\n";

    start = clock();
    HashTable dH(true);
    dH.deleteKey(k1);
    dH.add(k1);
    dH.display(0, 100);
    dH.addFew(X);
    dH.display(0, 100);
    dH.add(k2);
    dH.add(k3);
    dH.add(k4);
    dH.display(0, 100);
    dH.display(500, 600);
    dH.deleteKey(k3);
    dH.deleteKey(k4);
    dH.display(0, 100);
    dH.display(500, 600);
    stop = clock();
    time_spent = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "Czas wykonania dla metody mieszania podwojnego: " << time_spent << "s.\n";

    system("pause");
    return 0;
}

#pragma once
class HashTable
{
private:
    int hashArray[997] = { 0 }; // Tablica mieszająca
    int keysArray[20001] = { 0 }; // Tablica powtórzeń - indeksowanie: key - 20000
    bool dH; // Mieszanie podwójne
    int arraySize; // Rozmiar tablicy - tutaj na sztywno 997
    int hash1(int key); // Główna funkcja mieszająca.
    int hash2(int key); // Dodatkowa funkcja mieszająca.
    bool linearProbingAdd(int key, int index);
    bool doubleHashingAdd(int key, int index);
    int linearProbingSearch(int key, int index); // Zwraca indeks jeżeli znalazł, jeżeli nie znalazł to -1;
    int doubleHashingSearch(int key, int index); // Zwraca indeks jeżeli znalazł, jeżeli nie znalazł to -1;
public:
    HashTable(bool dH, int arraySize = 997); // Konstruktor - inicjacja tablicy.
    bool add(int key); // Dodaj jeden element.
    void addFew(int amount); // Dodaj kilka elementów.
    int search(int key); // Zwraca indeks jeżeli znalazł, jeżeli nie znalazł to -1;
    bool deleteKey(int key);
    void display(int start, int end);
    ~HashTable();
};

#include "stdafx.h"
#include "iostream"
#include "math.h"
#include "cstdlib"
#include "HashTable.h"

using namespace std;


HashTable::HashTable(bool dH, int arraySize)
    : dH(dH), arraySize(arraySize)
{
    cout << "Inicjacja tablicy mieszajacej.\n";
}

int HashTable::hash1(int key)
{
    int hash = ((key % 1000) + pow(2, (key % 10)) + 1);
    return (hash % 997);
}

int HashTable::hash2(int key)
{
    int hash = ((3 * key) % 19 + 1);
    return hash;
}

bool HashTable::linearProbingAdd(int key, int index)
{
    bool pass = false;

    do
    {
        index++;
        if (index >= arraySize)
        {
            cout << arraySize << endl;
            if (pass) return false;
            pass = true;
            index = 0;
        }
    } while (hashArray[index] != 0 && hashArray[index] != -1);

    hashArray[index] = key;
    return true;
}

bool HashTable::doubleHashingAdd(int key, int index)
{
    bool pass = false;

    do
    {
        index += hash2(key);
        if (index >= arraySize)
        {
            if (pass) return false;
            pass = true;
            index -= arraySize;
        }
    } while (hashArray[index] != 0 && hashArray[index] != -1);

    hashArray[index] = key;
    return true;
}

bool HashTable::add(int key)
{
    bool ok;
    int index = hash1(key);

    if (hashArray[index] != 0 && hashArray[index] != -1)
    {
        if (dH) ok = doubleHashingAdd(key, index);
        else ok = linearProbingAdd(key, index);
    }
    else
    {
        hashArray[index] = key;
        ok = true;
    }

    if (ok) keysArray[key - 20000] = 1;
    else cout << "Nie mozna dodac elementu!\n";

    return ok;
}

void HashTable::addFew(int amount)
{
    for (int i = 0; i < amount; i++)
    {
        int key;

        do
        {
            key = (((2 * rand()) % 20001) + 20000);
        } while (keysArray[key - 20000]);

        add(key);
    }
}

int HashTable::linearProbingSearch(int key, int index)
{
    bool pass = false;

    do
    {
        index++;
        if (index >= arraySize)
        {
            if (pass) return -1;
            pass = true;
            index = 0;
        }
    } while (hashArray[index] != key);

    return index;
}

int HashTable::doubleHashingSearch(int key, int index)
{
    bool pass = false;

    do
    {
        index += hash2(key);
        if (index >= arraySize)
        {
            if (pass) return -1;
            pass = true;
            index -= arraySize;
        }
    } while (hashArray[index] != 0);

    return index;
}

int HashTable::search(int key)
{
    int index = hash1(key);

    if (hashArray[index] != key)
    {
        if (dH) index = doubleHashingSearch(key, index);
        else index = linearProbingSearch(key, index);
    }

    if (index != -1) cout << "Element zostal odnaleziony.\n";
    else cout << "Element nie zostal odnaleziony.\n";

    return index;
}

bool HashTable::deleteKey(int key)
{
    int index = search(key);
    if (index != -1)
    {
        hashArray[index] = -1;
        keysArray[key - 20000] = 0;
        return true;
    }
    else return false;
}

void HashTable::display(int start, int end)
{
    if (start < 0 || end > arraySize) cout << "Zle indeksy!\n";
    else
    {
        cout << "Wyswietlanie od indeksu " << start << " do indeksu " << end << ":\n";
        for (int i = start; i < end; i++)
        {
            cout << hashArray[i] << endl;
        }
        cout << "Koniec wyswietlania.\n";
    }
}

HashTable::~HashTable()
{
    cout << "Cala tablica zostala usunieta." << endl;
}