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
留言列表