HashTable.h

Go to the documentation of this file.

#ifndef ULT_HASH_TABLE_H_INCLUDED
#define ULT_HASH_TABLE_H_INCLUDED
 
#include <string>
#include <vector>
 
namespace Ult
{

template<typename T>
class HashItem
{
public:
    HashItem() :
        mKey(0)
    {}

    ~HashItem()
    {}
    
    int GetKey() const { return mKey; }
    void SetKey(int k) { mKey = k; }
    
    T GetObject() { return mObj; }
    void SetObj(T obj) { mObj = obj; }
    
    bool operator==(const HashItem& item) {
        return (mKey == item.mKey);
    }

    HashItem& operator=(const HashItem& item) {
        mKey = item.mKey;
        mObj = item.mObj;
        return *this;
    }
 
private:
    int mKey;
    T mObj;
};

template<typename T>
class HashTable
{
public:
    HashTable(int size) :
        mSize(0),
        mTable(nullptr)
    {
        if (size > 0) {
            mSize = size;
            mTable = new std::vector<HashItem<T>>[mSize];
        }
    }

    ~HashTable()
    {
        mSize = 0;
        if (mTable) {
            delete[] mTable;
            mTable = nullptr;
        }
    }
    
    void Insert(const HashItem<T>& obj) {
        int hash = HashFunction(obj.GetKey());
        mTable[hash].push_back(obj);
    }

    void Delete(const int key) {
        HashItem<T> item;
        item.SetKey(key);
        int hash = HashFunction(key);
        std::vector<HashItem<T>>* ptr = &mTable[hash];
        for (auto it = ptr->begin(); it != ptr->end(); it++) {
            if (*it == item) {
                ptr->erase(it);
                break;
            }
        }
    }
    
    HashItem<T> Find(int key) {
        HashItem<T> item, tmp;
        item.SetKey(key);
        int hash = HashFunction(key);
        std::vector<HashItem<T>>* ptr = &mTable[hash];
        for (int i = 0; i<(int)ptr->size(); i++) {
            tmp = (*ptr)[i];
            if (tmp == item) {
                return tmp;
            }
        }
        item.SetKey(-1);
        return item;
    }
    
    int HashFunction(const int key) const {
        return key % mSize;
    }

    int HashFunction(const std::string& str) {
        // book
        /*int hash = 0;
        for (int i = 0; i<(int)str.size(); i++) {
            int val = (int)str[i];
            hash = (hash * 256 + val) % mSize;
        }
        return hash;*/
        // https://stackoverflow.com/questions/8317508/hash-function-for-a-string
        unsigned long hash = 0;
        for (int i=0; i<(int)str.size(); i++) {
            hash = (hash * 131) + str[i];
        }
        return int(hash % mSize);
    }
    
    int GetSize() const { return mSize; }
    
private:
    int mSize;
    std::vector<HashItem<T>>* mTable;
};
    
} // namespace Ult
 
#endif // ULT_HASH_TABLE_H_INCLUDED