// ConsoleTest.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
const int primes[] = {2009,3009,4009,5009,6009,7009,8009,16009};
template<class T>
int hash(T t){return t.hashCode();}
template <class KeyT,class ValT>
struct MyPair
{
typedef KeyT TypeKey;
typedef ValT TypeVal;
KeyT key;
ValT value;
};
template <class Pair>
struct BucketNode
{
typedef Pair DataType;
Pair PairValue;
BucketNode* pNext;
};
template <class DataType>
struct Bucket
{
typedef DataType Pair ;
typedef BucketNode<Pair> NodeType;
BucketNode<Pair>* pHead;
};
template<class Bucket>
class HashMap
{
public:
typedef typename Bucket::Pair MapPairType;
typedef typename MapPairType::TypeKey KeyT;
typedef typename MapPairType::TypeVal ValT;
HashMap();
const typename MapPairType* GetValue(KeyT key);
void insert(MapPairType data);
void rehash();
unsigned int HashValue(unsigned int hashCode);
float fHashFacil;
int nContOfContent;
int indexCapbility;
Bucket** pContent;
};
template<class Bucket>
const typename HashMap<Bucket>::MapPairType* HashMap<Bucket>::GetValue(KeyT key)
{
int indexOfFind = HashValue(hash(key));
Bucket::NodeType* pNode = pContent[indexOfFind]->pHead;
while (pNode != NULL)
{
if (pNode->PairValue.key == key)
{
return &(pNode->PairValue);
}
else
{
pNode = pNode->pNext;
}
}
return NULL;
}
template<class Bucket>
void HashMap<Bucket>::rehash()
{
Bucket** oldContent = pContent;
int oldIndexCapbility = indexCapbility;
if (indexCapbility >= sizeof(primes)/sizeof(primes[0]) - 1)
{
return;
}
while ((int)(fHashFacil*primes[indexCapbility]) < nContOfContent)
{
if (indexCapbility >= sizeof(primes)/sizeof(primes[0]) - 1)
{
break;
}
indexCapbility ++;
}
//
//Rehash the table.
//
//Reset the Count to zero.
nContOfContent = 0;
//Insert old data to new table;
pContent = new Bucket* [primes[indexCapbility]];
memset(pContent, 0, primes[indexCapbility]*sizeof(Bucket*));
for (int i = 0; i<primes[oldIndexCapbility]; i ++)
{
if (oldContent[i] != NULL)
{
Bucket::NodeType* pNode = oldContent[i]->pHead;
while (pNode)
{
insert(pNode->PairValue);
Bucket::NodeType* oldNode = pNode;
pNode = pNode->pNext;
delete oldNode;
}
}
}
delete[] oldContent;
}
template<class Bucket>
void HashMap<Bucket>::insert(MapPairType data)
{
if ((int)(fHashFacil*primes[indexCapbility]) < nContOfContent)
{
//std::cout<<"The current conten is "<<mapHash.nContOfContent<<std::endl;
std::cout<<"Rehash:The current capbility is"<<primes[indexCapbility]<<std::endl;
std::cout<<"Rehash:The current count is"<<nContOfContent<<std::endl;
rehash();
}
int hashVal = HashValue(hash(data.key));
std::cout<<hashVal<<"\t"<<data.key.m_strValue.data()<<"\t"<<data.value<<std::endl;
if (pContent[hashVal] == NULL)
{
Bucket* pBucket = new Bucket;
pBucket->pHead = new Bucket::NodeType;
pBucket->pHead->PairValue = data;
pBucket->pHead->pNext = NULL;
pContent[hashVal] = pBucket;
//delete pBucket;
}
else
{
Bucket::NodeType* pNode = pContent[hashVal]->pHead;
while (pNode->pNext!= NULL)
{
pNode = pNode->pNext;
}
Bucket* pBucket = new Bucket;
pNode->pNext = new Bucket::NodeType;
pNode->pNext->pNext = NULL;
pNode->pNext->PairValue = data;
}
nContOfContent ++;
}
template<class Bucket>
HashMap<Bucket>::HashMap()
{
fHashFacil = 0.75;
indexCapbility = 0;
nContOfContent = 0;
pContent = NULL;
pContent = new Bucket* [primes[indexCapbility]];
memset(pContent, 0, primes[indexCapbility]*sizeof(Bucket*));
}
template<class Bucket>
unsigned int HashMap<Bucket>::HashValue(unsigned int hashCode)
{
return hashCode%(primes[indexCapbility]);
}
//下面是测试程序。
//作为hashmap的（key，value)对中key必须定义==操作符和HashCode方法。
class HashString
{
friend bool operator== (const HashString& keyLeft, const HashString& keyRight);
public:
HashString(const std::string& strValue)
{
m_strValue = strValue;
}
HashString()
{
m_strValue = ("");
}
operator std::string()
{
return m_strValue;
}
int hashCode()
{
register unsigned int h;
register unsigned char *p;
for(h=0, p = (unsigned char *)m_strValue.data(); *p ; p++)
h = 31 * h + *p;
return h;
}
std::string m_strValue;
};
bool operator== (const HashString& keyLeft, const HashString& keyRight)
{
return keyLeft.m_strValue == keyRight.m_strValue;
}
int _tmain(int argc, _TCHAR* argv[])
{
HashMap<Bucket<MyPair<HashString, unsigned int>>> mapHash;
for(int i = 0; i< 1000; i++)
{
MyPair<HashString, unsigned int> pairValue1;
std::string strValue("XiongBei");
char buffer[33];
_itoa_s(i,buffer,33,10);
pairValue1.key = strValue.append(buffer);
pairValue1.value = i;
mapHash.insert(pairValue1);
}
//std::cout<<"The current conten is "<<mapHash.nContOfContent<<std::endl;
std::cout<<"The current capbility is"<<primes[mapHash.indexCapbility]<<std::endl;
std::cout<<"The current count is"<<mapHash.nContOfContent<<std::endl;
return 0;
}
