http://codecapsule.com/2013/05/13/implementing-a-key-value-store-part-5-hash-table-implementations/
http://preshing.com/20110603/hash-table-performance-tests/

兩個超級棒的網站, 關於 hash table 的例子/研究 很值得讀 !!

拿 preshing.com 裡面的 stringhashtable 修改如下 :  // stringhashtable.hpp

class StringHashTable
{
public:
    struct Bucket
    {
        char *key;
        uint value;
        Bucket *next;

        Bucket() : key(), value(), next() {}
        void setKey(const char *k) {
            key = (char *) malloc(strlen(k) + 1); strcpy(key, k);
        }
        ~Bucket() { free(key); }
    };

    uint m_tableSize;
    Bucket *m_table;
    uint m_blockSize;
    uint m_blockPos;
    uint m_numKeys;
    vector<Bucket *> m_blocks;

    StringHashTable(uint tableSize, uint blockSize = 256)
    {
        assert((tableSize & (tableSize - 1)) == 0);// Must be a power of two.
        m_table = new Bucket[tableSize];
        m_tableSize = tableSize;
        m_blockPos = m_blockSize = blockSize;
        m_numKeys = 0;
    }

    ~StringHashTable()
    {
        delete[] m_table;
        for (uint i = 0; i < m_blocks.size(); i++)
        {
            delete[] m_blocks[i];
        }
    }

    static uint fnv1Hash(const char *key)
    {
        uint hash = 2166136261;
        for (const char *s = key; *s; s++)
        hash = (16777619 * hash) ^ (*s);
        return hash;
    };

    uint &operator[](const char *key)
    {
        uint hash = fnv1Hash(key) & (m_tableSize - 1);
        Bucket *firstBucket = m_table + hash;
        Bucket *b = firstBucket;
        if (b->key)
        {
            do
            {
                if (strcmp(b->key, key) == 0)
                    return b->value;// Found existing bucket
                b = b->next;
            } while (b);
        }
        // Add it
        m_numKeys++;
        if (!firstBucket->key)
        {
            firstBucket->setKey(key);// Use bucket in table
            return firstBucket->value;
        }
        // Allocate a new bucket
        if (m_blockPos >= m_blockSize)
        {
            Bucket *block = new Bucket[m_blockSize];
            m_blocks.push_back(block);
            m_blockPos = 0;
        }
        b = m_blocks.back() + m_blockPos;
        m_blockPos++;
        b->setKey(key);
        b->next = firstBucket->next;
        firstBucket->next = b;
        return b->value;
    }
};

//teststringhashtable.cpp

using namespace std ;

FILE   *fp1  ;

typedef StringHashTable::Bucket Bucket;

int main()
{
    StringHashTable m_wordCount(1024) ;

    char filename[128] ;
    sprintf(filename,"/home/informix/mars/test/hash/dictionary.txt") ;
    fp1 = fopen(filename,"r");

    char strx[181];
    while (1)
    {
        if(fgets(strx,181,fp1)==NULL)
            break ;
        strx[strlen(strx)-2]=0x00 ;
        m_wordCount[strx] += 1;
    }

    uint i;
    for (i = 0; i < m_wordCount.m_tableSize; i++)
    {
        Bucket *b = m_wordCount.m_table + i;
        if (b->key)
            printf("1(%d)(%s)\n",b->value, b->key);
    }
    for (i = 0; i < m_wordCount.m_blocks.size(); i++)
    {
        Bucket *block = m_wordCount.m_blocks[i];
        for (uint j = 0; j < m_wordCount.m_blockSize; j++)
        {
            if (block[j].key)
                printf("2(%d)(%s)\n",block[j].value, block[j].key);
        }
    }

    printf("(%d) \n",m_wordCount["123zzz"]) ;
    m_wordCount["123zzz"] = 123456 ;
    printf("(%d) \n",m_wordCount["123zzz"]) ;
}

g++ --std=c++0x teststringhashtable.cpp -o teststringhashtable.exe

 

全站熱搜

hedgezzz 發表在 痞客邦 留言(0) 人氣()