Untitled

#include <iostream>
#include <vector>
using namespace std;
//Open addressing

//Linear probing

class HashTableLinearProbing {
	vector<int> table;
	int size;
	
public:
	/*HashTableLinearProbing(int s) 
	{
		this->size = s;
		table.resize(size, -1);
	}*/
	//hoặc
	HashTableLinearProbing(int s) : size(s) { //size ở đây thì theo suy đoán là m trong slide của thầy dsa tại cùng dịch là kích cỡ
		table.resize(size, -1); // -1 indicates an empty slot
	}//Nên lưu ý là các vị trí trống được đánh dấu là -1 nên logic của code này sẽ sai nếu nhập vào có giá trị là -1

	int hashFunction(int key) //hàm băm
	{
		return key % size;
	}

	void insert(int key) //Thêm phần tử vào bảng
	{
		int index = hashFunction(key);// index này vị trí để nhét số vào bảng băm
		while (table[index] != -1)// đọc lưu ý về logic ở trên để hiểu tại sao lại khác -1
		{
			index = (index + 1) % size;
		}
		table[index] = key;
	}

	bool search(int key)
	{
		int index = hashFunction(key);
		int Startingindex = hashFunction(key); //đây là biến đánh dấu index lúc chưa băm để kiếm

		while (table[index] != -1)
		{
			if (table[index] == key)
			{
				return true;
			}
			index = (index + 1) % size;
			if (index == Startingindex)
			{
				return false;//lúc này lặp đến vị trí mà ban đầu mình đã tìm nên là false vì không tìm thấy
			}
		}
		return false;
	}

	void display() //biểu diễn cách các khóa i giữ các giá trị key như thế nào và ở các vị trí nào
	{
		for (int i = 0; i < size; i++)
		{
			if (table[i] != -1)
			{
				cout << i << " --> " << table[i] << "\n";
			}
			else
			{
				cout << i << " --> \n";
			}
		}
	}
};
//
//int main()
//{
//	HashTableLinearProbing ht(7);
//	ht.insert(10);
//	ht.insert(20);
//	ht.insert(5);
//	ht.insert(15);
//	
//	ht.display();
//
//	cout << "Search 10: " << (ht.search(10) ? "Found" : "Not Found") << "\n";
//	cout << "Search 21: " << (ht.search(21) ? "Found" : "Not Found") << "\n";
//
//	return 0;
//}

class HashTableQuadraticProbing {
	vector<int> table;
	int size;

public:
	HashTableQuadraticProbing(int s) : size(s)
	{
		table.resize(size, -1);
	}
	
	int hashFunction(int key)
	{
		return key % size;
	}

	void insert(int key)
	{
		int index = hashFunction(key);
		int i = 1;

		while (table[index] != -1)
		{
			index = (hashFunction(key) + i * i) % size;
			i++;
		}
		table[index] = key;
	}

	bool search(int key)
	{
		int index = hashFunction(key);
		int i = 1;

		while (table[index] != -1)
		{
			if (table[index] == key)
			{
				return key;
			}
			index = (hashFunction(key) + i * i) % size;
			i++;
			if (i > size)
			{
				return false;
			}
		}
		return false;
	}
	
	void display()
	{
		for (int i = 0; i < size; i++)
		{
			if (table[i] != -1)
			{
				cout << i << " --> " << table[i] << "\n";
			}
			else
			{
				cout << i << " --> \n";
			}
		}
	}
};

//int main()
//{
//	HashTableLinearProbing ht(7);
//	ht.insert(10);
//	ht.insert(20);
//	ht.insert(5);
//	ht.insert(15);
//	
//	ht.display();
//
//	cout << "Search 10: " << (ht.search(10) ? "Found" : "Not Found") << "\n";
//	cout << "Search 21: " << (ht.search(21) ? "Found" : "Not Found") << "\n";
//
//	return 0;
//}

class HashTableRehashing
{
	vector<int> table;
	int size;
public:
	class HashTableRehashing(int s) : size(s)
	{
		table.resize(size, -1);
	}
	int hashFunction(int key)
	{
		return key % size;
	}
	int rehashFunction(int key)
	{
		return (key / size) % size;
	}
	void insert(int key)
	{
		int index = hashFunction(key);
		int RehashIndex = rehashFunction(key);

		while (table[index] != -1)
		{
			index = (index + RehashIndex) % size;
		}
		table[index] = key;
	}
	void display()
	{
		for (int i = 0; i < size; i++)
		{
			if (table[i] != -1)
			{
				cout << i << " --> " << table[i] << endl;
			}
			else
			{
				cout << i << " --> \n";
			}
		}
	}
};