DoubleHashing.cpp

#include "DoubleHashing.hpp"

DoubleHashTable::DoubleHashTable(int initialCapacity) : capacity(initialCapacity), size(0) {
	table = new Entry[capacity]();								//inicjalizacja tablicy wpisów (wszystkie wpisy są początkowo nie zajęte i nie usunięte)
}

DoubleHashTable::~DoubleHashTable() {
	delete[] table;												//zwolnienie pamięci zajmowanej przez tablicę wpisów
}

int DoubleHashTable::hash1(int key) {
	return key % capacity;										//prosta funkcja hashująca (modulo pojemności tablicy)
}

int DoubleHashTable::hash2(int key) {
	return 1 + (key % (capacity - 1));							//druga funkcja hashująca (nie może zwracać 0, dlatego dodajemy 1)
}

bool DoubleHashTable::isPrime(int n) {							//sprawdzenie czy liczba jest pierwsza (używane do obliczania rozmiaru tablicy)
	if (n < 2) return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

int DoubleHashTable::nextPrime(int n) {							//znalezienie następnej liczby pierwszej (używane do obliczania rozmiaru tablicy)
	while (!isPrime(n)) n++;
	return n;
}

void DoubleHashTable::insertWithoutRehash(int key, int value) {	//wstawianie elementu bez sprawdzania rehashowania (używane podczas rehashowania)
	int h1 = hash1(key);
	int h2 = hash2(key);

	for (int i = 0; i < capacity; i++) {
		int index = (h1 + i * h2) % capacity;

		if (table[index].occupied && table[index].key == key) {
			table[index].value = value;
			return;
		}

		if (!table[index].occupied || table[index].deleted) {
			table[index].key = key;
			table[index].value = value;
			table[index].occupied = true;
			table[index].deleted = false;
			return;
		}
	}
}

void DoubleHashTable::insert(int key, int value) {				//wstawianie elementu (sprawdzenie czy trzeba rehashować przed wstawieniem)
	if ((double)size / capacity > 0.7) {						//jeśli współczynnik obciążenia przekracza 0.7, rehashuj
		rehash();
	}

	int h1 = hash1(key);
	int h2 = hash2(key);

	for (int i = 0; i < capacity; i++) {
		int index = (h1 + i * h2) % capacity;					//obliczenie indeksu za pomocą podwójnego hashowania

		if (!table[index].occupied || table[index].deleted) {	//jeśli pozycja jest wolna lub oznaczona jako usunięta, wstaw nowy element
			table[index].key = key;
			table[index].value = value;
			table[index].occupied = true;
			table[index].deleted = false;
			size++;
			return;
		}
		if (table[index].key == key) {							//jeśli klucz już istnieje, zaktualizuj wartość
			table[index].value = value;
			return;
		}
	}
	rehash();													//jeśli tablica jest pełna, rehashuj i spróbuj ponownie
	insert(key, value);											//ponowne wstawienie po rehashowaniu
}

void DoubleHashTable::remove(int key) {							//usuwanie elementu (oznaczenie pozycji jako usuniętej, ale nie zwalnianie jej, aby zachować ciągłość poszukiwań)
	int h1 = hash1(key);
	int h2 = hash2(key);

	for (int i = 0; i < capacity; i++) {
		int index = (h1 + i * h2) % capacity;

		if (!table[index].occupied && !table[index].deleted) {
			return;												//jeśli napotkamy wolną pozycję, oznacza to, że klucz nie istnieje w tablicy, więc możemy zakończyć poszukiwania
		}
		if (table[index].occupied && table[index].key == key) {
			table[index].occupied = false;
			table[index].deleted = true;
			size--;
			return;
		}
	}
}

void DoubleHashTable::rehash() {								//rehashowanie tablicy (podwajanie pojemności i przenoszenie elementów)
	int oldCapacity = capacity;
	Entry* oldTable = table;

	capacity = nextPrime(capacity * 2);							//podwojenie pojemności i znalezienie następnej liczby pierwszej

	table = new Entry[capacity]();
	size = 0;

	for (int i = 0; i < oldCapacity; i++) {
		if (oldTable[i].occupied && !oldTable[i].deleted) {
			insertWithoutRehash(oldTable[i].key, oldTable[i].value);
			size++;
		}
	}

	delete[] oldTable;
}