ADS/P2/ADS_P2_2_Hashtable/hashtable.cpp

#include "hashtable.h"
#include <iostream>
#include <cmath> // Für std::ceil


using namespace std;

HashTable::HashTable(int size, double threshhold, int methode) {
	hashTable = new vector<int>(size, -1);
	this->size = size;
	this->threshhold_rehashing = threshhold;
	this->m_sondierMethode = methode;
	this->elements = 0;
	this->collisionCount = 0;
}

HashTable::~HashTable() {
	this->size = 0;
	this->elements = 0;
	this->collisionCount = 0;
	this->hashTable->clear();
	delete hashTable;
}

int get_next_prime(int x) {
	x = x + 1;
	bool found = true;
	while (true) {
		found = true;
		for (int i = 2; i <= sqrt(x); i++) {
			if (x % i == 0) {
				found = false;
				break;
			}
		}
		if (found) {
			return x;
		}
		x += 1;
	}
}

int get_last_prime(int x) {
	x = x - 1;
	bool found = true;
	while (true) {
		found = true;
		for (int i = 2; i <= sqrt(x); i++) {
			if (x % i == 0) {
				found = false;
				break;
			}
		}
		if (found) {
			return x;
		}
		x -= 1;
	}
}

// Berechnung des Hashwertes 
int HashTable::hashValue(int item) {
	switch (m_sondierMethode) {
	case (1): {
		// Lineares Sondieren
		int i = 0;
		int index = (item + i) % getSize();

		while (hashTable->at(index) != -1) {
			collisionCount++;
			i++;
			index = (item + i) % getSize();
		}

		return index;
	}
	case (2): {
		// Quadr. Sondieren
		int i = 0;
		int index = (item + (i * i)) % getSize();

		while (hashTable->at(index) != -1) {
			collisionCount++;
			i++;
			index = (item + (i * i)) % getSize();
		}

		return index;
	}
	case (3): {
		// Doppeltes Hashing
		int R = get_last_prime(getSize());

		int i = 0;
		int index = (item + i * (R - (item % R))) % getSize();

		while (hashTable->at(index) != -1) {
			collisionCount++;
			i++;
			index = (item + i * (R - (item % R))) % getSize();
		}

		return index;
	}
	default: {
		break;
	}
	}
	return -1;
}


void HashTable::rehashing() {
	int newSize = get_next_prime(2 * getSize());
	if (newSize < 1000) {
		vector<int>* newTable = new vector<int>(newSize, -1);
		collisionCount = 0;
		
		for (int i = 0; i < getSize(); i++) {
			if (hashTable->at(i) != -1) {
				int newIndex = hashTable->at(i) % newSize;
				int j = 0;
				while (newTable->at(newIndex) != -1) {
					j++;
					collisionCount++;

					// Neue Hash Funktion für das Rehashing
					// h(k_i) = k_i mod neueGröße
					newIndex = (newIndex + j) % newSize;
				}
				newTable->at(newIndex) = hashTable->at(i);
			}
		}

		hashTable = newTable;
		size = newSize;
	}
	else
		return;

}

int HashTable::insert(int item) {
	elements++;
	double resizeLimit = getSize() * threshhold_rehashing;

	if (getElements() >= resizeLimit) {
		rehashing();
	}

	int index = hashValue(item);
	hashTable->at(index) = item;

	return index;
}


int HashTable::at(int i) {
	return hashTable->at(i);
}

int HashTable::getCollisionCount() {
	return this->collisionCount;
}

int HashTable::getSize() {
	return this->size;
}

int HashTable::getElements() {
	return this->elements;
}