CuckooHashing.cpp

#include "CuckooHashing.hpp"
#include <iostream>

CuckooHashTable::CuckooHashTable(int initialCapacity) : capacity(initialCapacity), table1(initialCapacity), table2(initialCapacity) {}	//Konstruktor inicjalizujący pojemność i tworzący dwie tablice o tej samej pojemności

int CuckooHashTable::hash1(int key) const{	//Pierwsza funkcja hashująca, która zwraca indeks dla klucza w pierwszej tablicy
	return key % capacity;
}

int CuckooHashTable::hash2(int key) const{	//Druga funkcja hashująca, która zwraca indeks dla klucza w drugiej tablicy
	return 1 + (key % (capacity - 1));
}

bool CuckooHashTable::place(int key, int value, int depthStart) {	// Funkcja pomocnicza do umieszczania elementu, która próbuje umieścić element w jednej z tablic, a jeśli jest zajęta, wypycha istniejący element i próbuje umieścić go w drugiej tablicy. Jeśli po określonej liczbie prób nadal nie uda się umieścić elementu, zwraca false, co sygnalizuje potrzebę rehashowania.
	int maxDepth = 2 * capacity;	// maksymalna liczba prób, aby uniknąć nieskończonych cykli
	int depth = depthStart;			// aktualna głębokość prób
	int curKey = key;				// aktualny klucz do umieszczenia
	int curValue = value;			// aktualna wartość do umieszczenia
	bool inTable1 = true;			// zaczynamy od pierwszej tablicy

	while (depth <= maxDepth) {		// Dopóki nie przekroczymy maksymalnej liczby prób
		if (inTable1) {							// Próba umieszczenia w pierwszej tablicy
			int idx1 = hash1(curKey);			// Obliczamy indeks dla klucza w pierwszej tablicy
			if (!table1[idx1].occupied) {		// Jeśli miejsce jest wolne, umieszczamy element i kończymy
				table1[idx1].key = curKey;
				table1[idx1].value = curValue;
				table1[idx1].occupied = true;
				return true;
			}
			std::swap(curKey, table1[idx1].key);		// Jeśli miejsce jest zajęte, wypychamy istniejący element i próbujemy umieścić go w drugiej tablicy
			std::swap(curValue, table1[idx1].value);	// Zamieniamy klucz i wartość z elementem, który jest wypychany
			inTable1 = false;
		}
		else {
			int idx2 = hash2(curKey);					// Próba umieszczenia w drugiej tablicy
			if (!table2[idx2].occupied) {				// Jeśli miejsce jest wolne, umieszczamy element i kończymy
				table2[idx2].key = curKey;
				table2[idx2].value = curValue;
				table2[idx2].occupied = true;
				return true;
			}
			std::swap(curKey, table2[idx2].key);		// Jeśli miejsce jest zajęte, wypychamy istniejący element i próbujemy umieścić go w pierwszej tablicy
			std::swap(curValue, table2[idx2].value);	// Zamieniamy klucz i wartość z elementem, który jest wypychany
			inTable1 = true;							// Przełączamy się z powrotem na pierwszą tablicę
		}
		++depth;		// Zwiększamy głębokość prób, aby monitorować, ile razy próbowaliśmy umieścić element
	}
	return false; // sygnał do rehashu
}

void CuckooHashTable::rehash() {	// Funkcja do rehashowania, która podwaja pojemność tablic i przenosi istniejące elementy do nowych tablic
	int oldCapacity = capacity;
	capacity *= 2;

	DynamicArray<CuckooEntry> oldTable1 = table1;	// Przechowujemy stare tablice
	DynamicArray<CuckooEntry> oldTable2 = table2;

	table1 = DynamicArray<CuckooEntry>(capacity);	// Tworzymy nowe tablice o podwojonej pojemności
	table2 = DynamicArray<CuckooEntry>(capacity);

	for (int i = 0; i < oldCapacity; i++) {	// Przenosimy elementy z pierwszej starej tablicy do nowych tablic
		if (oldTable1[i].occupied) {
			insert(oldTable1[i].key, oldTable1[i].value);
		}
		if (oldTable2[i].occupied) {	// Przenosimy elementy z drugiej starej tablicy do nowych tablic
			insert(oldTable2[i].key, oldTable2[i].value);
		}
	}
}

void CuckooHashTable::insert(int key, int value) {	// Wstawianie elementu do tablicy
	if (!place(key, value, 0)) {	// Próba umieszczenia elementu, jeśli nie uda się (z powodu cyklu), rehashujemy i próbujemy ponownie
		rehash();
		insert(key, value);
	}
}

void CuckooHashTable::remove(int key) {	// Usuwanie elementu z tablicy
	int index1 = hash1(key);
	if (table1[index1].occupied && table1[index1].key == key) {	// Sprawdzamy pierwszą tablicę
		table1[index1].occupied = false;
		return;
	}
	int index2 = hash2(key);
	if (table2[index2].occupied && table2[index2].key == key) {	// Sprawdzamy drugą tablicę
		table2[index2].occupied = false;
		return;
	}
}

bool CuckooHashTable::contains(int key) const {
	int index1 = hash1(key);
	if (table1[index1].occupied && table1[index1].key == key) return true;

	int index2 = hash2(key);
	if (table2[index2].occupied && table2[index2].key == key) return true;

	return false;
}