Double hashing
unknown
c_cpp
3 years ago
2.8 kB
7
Indexable
#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(); }
Editor is loading...