Double hashing

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.8 kB
7
Indexable
Never
#include <iostream>

/*
  Collision step function = (Hash1() + i * Hash2()) % TABLE_SIZE
 */

struct Vec3D
{
	int m_X, m_Y, m_Z;

	Vec3D()
		: m_X(INT_MIN), m_Y(INT_MIN), m_Z(INT_MIN)
	{
		
	}

	Vec3D(int x, int y, int z)
		: m_X(x), m_Y(y), m_Z(z)
	{
		
	}

	friend bool operator!= (const Vec3D& first, const Vec3D& second)
	{
		return first.m_X != second.m_X && first.m_Y != second.m_Y && first.m_Z != second.m_Z;
	}

	friend std::ostream& operator<< (std::ostream& COUT, const Vec3D& vector)
	{
		if (vector.m_X != INT_MIN)
			std::cout << "(" << vector.m_X << "," << vector.m_Y << "," << vector.m_Z << ")";
		else
			std::cout << "";

		return COUT;
	}
};

template<typename T>
class HashTable
{
private:
	T* m_Table;
	bool* m_Taken;
	int m_Current;
	int m_Size;

	int Hash1(const T& key)
	{
		return -1;
	}

	int Hash2(const T& key)
	{
		return -1;
	}
public:
	HashTable(int size = 15)
		: m_Current(0), m_Size(size)
	{
		m_Table = new T[size];
		m_Taken = new bool[size]{false};
	}

	~HashTable()
	{
		delete[] m_Table;
		delete[] m_Taken;
	}

	void Add(const T& element)
	{
		if (m_Current == m_Size)
		{
			std::cout << "Table is full!" << std::endl;
			return;
		}

		int index = Hash1(element);

		if (m_Taken[index])
		{
			int index2 = Hash2(element);
			int i = 1;

			while (true)
			{
				int newIndex = (index + i * index2) % m_Size;

				if (!m_Taken[newIndex])
				{
					m_Table[newIndex] = element;
					m_Taken[newIndex] = true;
					break;
				}

				i++;
			}
		}

		else
		{
			m_Table[index] = element;
			m_Taken[index] = true;
		}

		m_Current++;
	}

	bool Remove(const T& element)
	{
		int index = Hash1(element);
		int index2 = Hash2(element);
		int i = 0;

		while (m_Table[index] != element)
		{
			if (i > m_Size)
			{
				std::cout << "Element could not be found!" << std::endl;
				return false;
			}
			index += i * index2;
			index %= m_Size;
			i++;
		}

		m_Taken[index] = false;
		return true;
	}

	void Print() const
	{
		for (int i = 0; i < m_Size; i++)
		{
			if (m_Taken[i])
				std::cout << i << " --> " << m_Table[i] << std::endl;
			else
				std::cout << i << " --> " << std::endl;
		}
	}
};

template<>
int HashTable<Vec3D>::Hash1(const Vec3D& vector)
{
	return sqrt(pow(vector.m_X + vector.m_Y + vector.m_Z, 2));
}

template<>
int HashTable<Vec3D>::Hash2(const Vec3D& vector)
{
	return sqrt(pow(vector.m_X, 2) / 3 + pow(vector.m_Y, 2) / 3 + pow(vector.m_Z, 2) / 3);
}

int main()
{
	HashTable<Vec3D> table;

	table.Add(Vec3D(2, 2, 2));
	table.Add(Vec3D(5, 4,2));
	table.Add(Vec3D(7, 3, 1));
	table.Add(Vec3D(8, 8, 8));

	table.Print();

	std::cout << "-------------------------------------\n";

	table.Remove(Vec3D(2, 2, 2));
	table.Remove(Vec3D(5, 4,2));
	table.Remove(Vec3D(7, 3, 1));
	table.Remove(Vec3D(8, 8, 8));

	table.Print();
}