hashtable.cpp

// Hash table
// 
// Simplified code as example for the hash table.
//
// by feyd//godX.de
 
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
 
class CHashKeyString
{
public:
    CHashKeyString(const char* pText)
    {
        m_nHash = 0;
        while(*pText)
        {
            m_nHash *= 0x4e4b7b35;
            m_nHash += *(const unsigned char*)pText++;
        }
    }
    virtual ~CHashKeyString() {}
 
    size_t GetHash(size_t nSize) const
    {
        return m_nHash%nSize;
    }
private:
    size_t m_nHash;
};
 
template <class _KEY, class _TYPE>
class CHashTable
{
public:
    CHashTable(size_t nSize) : m_table(nSize)
    {
        // initialization needed for native types in _TYPE
        for(size_t n=0; n<m_table.size(); n++)
            m_table[n] = 0;
    }
    virtual ~CHashTable() {}
 
    _TYPE& Find(const _KEY& key)
    {
        return m_table[key.GetHash(m_table.size())];
    }
private:
    std::vector<_TYPE> m_table;
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Hash table test...\r\n\r\n");
 
    if(argc>2)
    {
        CHashTable<CHashKeyString, int> hash(128);
        for(int n=1; n<argc-1; n++)
        {
            int& nTest = hash.Find(argv[n]);
            if(nTest!=0)
            {
                printf("collision with key %d\r\n", nTest);
            } else {
                nTest = n;
            }
        }
        int& nSearch = hash.Find(argv[argc-1]);
        if(nSearch!=0)
        {
            printf("'%s' has same hash as key %d\r\n", argv[argc-1], nSearch);
        } else {
            printf("'%s' was not found\r\n", argv[argc-1]);
        }
    } else {
        printf("not enough arguments\r\n");
    }
    return 0;
}