Hello all,
Thought I'd get some quick input on this hash table. Especially on the const part (see Find, IFind and Delete), all of which I really don't know how to implement properly.
This is a rather naive implementation, but it works, and performance is reasonable, so I'm happy.
Suggestions are welcome.
Code:
Test program (for those who wish to compile and test):Code:#include <list>
#include <vector>
#include <utility>
#include <fstream>
#include <string>
#include <iostream>
#include "spooky.h"
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <exception>
#define BASIC_TYPE(type2) \
template<typename T> struct BasicType<type2 T> { typedef typename BasicType<T>::type type; }
template<typename T> struct BasicType { typedef T type; };
template<typename T> struct BasicType<T*> { typedef typename BasicType<T>::type type; };
BASIC_TYPE(const);
BASIC_TYPE(volatile);
#define IIS_PRIMITIVE_FLOAT(type) \
template<> struct IIsPrimitive<type> { static const bool value = true; }
#define IIS_PRIMITIVE(type) \
template<> struct IIsPrimitive<unsigned type> { static const bool value = true; }; \
template<> struct IIsPrimitive<signed type> { static const bool value = true; }
template<typename Key_t> struct IIsPrimitive { static const bool value = false; };
IIS_PRIMITIVE(char);
IIS_PRIMITIVE(short);
IIS_PRIMITIVE(int);
IIS_PRIMITIVE(long);
IIS_PRIMITIVE(long long);
IIS_PRIMITIVE_FLOAT(float);
IIS_PRIMITIVE_FLOAT(double);
IIS_PRIMITIVE_FLOAT(long double);
IIS_PRIMITIVE_FLOAT(void);
template<typename Key_t> struct IsPrimitive { static const bool value = IIsPrimitive<typename BasicType<Key_t>::type>::value; };
template<typename Key_t, typename Type_t>
class XHashTable
{
protected:
typedef std::pair<Key_t, Type_t> Pair_t;
typedef std::list<Pair_t> List_t;
typedef std::vector<List_t> Vector_t;
public:
XHashTable(float LoadFactor = 0.9): m_Items(0), m_Collisions(0), m_Values(100), m_LoadFactor(LoadFactor)
{
assert(LoadFactor > 0);
}
void Add(const Key_t& Key, const Type_t& Value)
{
assert(m_Items > 0);
if ((float)m_Items / m_Values.size() > m_LoadFactor)
{
m_Values.resize(m_Values.size() * 2);
Rehash();
}
bool success;
IFind(Key, success);
if (success)
return;
m_Items++;
auto Hash = GetHash<IsPrimitive<Key_t>::value>(Key);
auto pair = std::make_pair(Key, Value);
auto & list = m_Values.at(Hash);
if (list.size() > 0)
m_Collisions++;
assert(m_Collisions >= 0);
list.push_back(pair);
}
Type_t& Find(const Key_t& Key)
{
return (Type_t&)Find2(Key);
}
const Type_t& Find(const Key_t& Key) const
{
return Find2(Key);
}
bool Delete(const Key_t& key)
{
bool success;
auto ret = IFind(key, success);
if (!success)
return false;
auto it = ret.first;
auto list = (List_t*)ret.second;
list->erase(it);
m_Items--;
return true;
}
unsigned int GetCollisions() { return m_Collisions; }
std::size_t GetStorageSize() { return m_Values.size(); }
unsigned int GetMapSize() { return m_Items; }
protected:
const Type_t& Find2(const Key_t& Key) const
{
bool success;
auto ret = IFind(Key, success);
if (!success)
throw std::runtime_error("Key not found!");
return ret.first->second;
}
template<bool IsPrimitive /* = true */>
unsigned int GetHash(const Key_t& Key) const
{
return SpookyHash::Hash32(&Key, sizeof(Key), 0) % m_Values.size();
}
template<>
unsigned int GetHash<false>(const Key_t& Key) const //!IsPrimitive
{
return SpookyHash::Hash32(&Key[0], Key.size(), 0) % m_Values.size();
}
std::pair<typename List_t::const_iterator, const List_t*> IFind(const Key_t& Key, bool& Success) const
{
auto Hash = GetHash<IsPrimitive<Key_t>::value>(Key);
auto & list = m_Values.at(Hash);
auto list_end = list.end();
for (auto it = list.begin(); it != list_end; ++it)
{
if (it->first == Key)
{
Success = true;
return std::make_pair(it, &list);
}
}
Success = false;
return std::make_pair(list_end, &list);
}
void Rehash()
{
for (std::size_t it = 0; it < m_Values.size(); ++it)
{
auto & list = m_Values.at(it);
for (auto list_it = list.begin(); list_it != list.end();)
{
const auto & key = list_it->first;
const auto & value = list_it->second;
auto NewHash = GetHash<IsPrimitive<Key_t>::value>(key);
if (NewHash != it)
{
m_Values.at(NewHash).push_back(std::make_pair(key, value));
auto old_it = list_it++;
list.erase(old_it);
}
else
++list_it;
}
}
}
Vector_t m_Values;
int m_Items;
int m_Collisions;
float m_LoadFactor;
};
Code:template class XHashTable<std::string, int>;
int main()
{
int lines = 0;
XHashTable<std::vector<char>, int> HashTable;
std::vector<char> buf(1024);
{
std::ifstream testfile("Insert favorite file here", std::ios_base::binary);
while (testfile.read(&buf[0], buf.size()))
{
lines++;
HashTable.Add(buf, lines);
}
}
lines = 0;
{
std::ifstream testfile("Insert favorite file here", std::ios_base::binary);
while (testfile.read(&buf[0], buf.size()))
{
lines++;
if (HashTable.Find(buf) != lines)
std::cout << "MISMATCH AT ROW " << lines << ".\n";
}
}
std::cout << "Collisions: " << HashTable.GetCollisions() << " (" << (float)HashTable.GetCollisions() / HashTable.GetMapSize() * 100 << "%)\n";
std::cout << "Number of items in map: " << HashTable.GetMapSize() << "\nSize of internal vector: " << HashTable.GetStorageSize() << "\n";
return 0;
}
