一个简单的HASH表,用链表实现,有兴趣的朋友可以看看.

用到的宏typedef int    BOOL;
typedef void * HID;
//.h
////////////////////////////////////////////////////////////////////////////////////////////////////////////////class CfKeyPtrDeque  
{
protected:
////
struct tagNode  
{
void * pData;
GUID   stKey;
tagNode *pstPrev;  
tagNode *pstNext;
};
public:
CfKeyPtrDeque();
virtual ~CfKeyPtrDeque();

protected:
//申请
void * AllocNode();
//释放
void   FreeNode(void * pNode);
protected:
//剪切
void  CutNode(tagNode * pNode );
public:
//添加到头
HID AddHead(const GUID & stKey,void * pnewElement);
//添加到尾
HID AddTail(const GUID & stKey,void * pnewElement);
//查找
HID FindKey(const GUID & stKey);
//头
HID GetHeadPosition();
//尾
HID GetTailPosition();
//写
BOOL SetAt(HID pNode,void * pnewElement,GUID * pstKey = NULL);
//取值
BOOL GetAt(HID pNode,GUID & stKey,void *& poldElement);
//移除,返回移除的值
BOOL RemoveAt(HID pNode);
//自头向尾枚举
BOOL GetNext(HID& pNextNode,GUID & stKey,void *& poldElement); 
//自尾向头枚举
BOOL GetPrev(HID& pPrevNode,GUID & stKey,void *& poldElement); 
//移除所有
void RemoveAll();
public:
//长度
int GetCount();

protected:
//头
tagNode* m_pHead ;
//尾
tagNode* m_pTail ;
protected:
//计数器
int m_nCount ; // num 1,2,3........
};class CfPtrHash  
{
public:
CfPtrHash();
virtual ~CfPtrHash();
public:
//
BOOL Create(int nBulkSize);
//
    BOOL SetAt(const GUID & stKey,void* pnewElement);
//
    BOOL RemoveKey(const GUID & stKey);
//
    BOOL Lookup(const GUID & stKey,void*& poldElement);
//
BOOL ElementFirst(GUID & stKey,void*& poldElement);
//
BOOL ElementNext(GUID & stKey,void*& poldElement);
//
    void RemoveAll();
//
    int  GetBulkSize()  ;
//
    int  GetCount() ;
protected:
//
    virtual UINT  KeyValue(const GUID & stKey);protected:
//
CfKeyPtrDeque * m_pHashBulk;
//
int m_nBulkSize;
//
int m_nCount;
//
HID m_pEnumHID;
//
int m_nEnumHashValue;};
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//*.cpp
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
CfKeyPtrDeque::CfKeyPtrDeque()
{
m_pHead = NULL;
m_pTail = NULL;
m_nCount = 0; 
}CfKeyPtrDeque::~CfKeyPtrDeque()
{
RemoveAll();
}
void* CfKeyPtrDeque::AllocNode()
{
tagNode* pNode =(tagNode*)::fMalloc(sizeof(tagNode));
if( NULL != pNode )
{
memset(pNode,0,sizeof(tagNode));
}
return pNode;
}
void CfKeyPtrDeque::FreeNode(void * pVoid)
{
tagNode*  pNode = (tagNode*)pVoid;
if( pNode )
{
::fFree(pNode);
}
}void  CfKeyPtrDeque::CutNode(tagNode * pNode )
{
//A <--->B<--->C
//分离节点B,使A和C以相连 A<--->C
if(pNode->pstNext)
pNode->pstNext->pstPrev = pNode->pstPrev;
if(pNode->pstPrev)
pNode->pstPrev->pstNext = pNode->pstNext;

//是头节点
if( pNode == m_pHead )
{
m_pHead = pNode->pstNext;
if( m_pHead )
m_pHead->pstPrev = NULL;
}
//是尾节点
if( pNode == m_pTail )
{
m_pTail = pNode->pstPrev;
if( m_pTail )
m_pTail->pstNext = NULL;
}
//清除分离后的节点
FreeNode(pNode);
//记数器减1
m_nCount--;

}
HID CfKeyPtrDeque::AddHead(const GUID & stKey,void * pnewElement)
{
tagNode* pNewNode = NULL;

if(  m_pHead )
{
if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;
pNewNode->stKey = stKey;

//添加到开头
m_pHead->pstPrev = pNewNode;
pNewNode->pstNext = m_pHead;
m_pHead = pNewNode;

m_nCount++;
}
}
else
{
pNewNode = (tagNode*)AddTail(stKey,pnewElement);
}


return pNewNode;
}
HID CfKeyPtrDeque::AddTail(const GUID & stKey,void * pnewElement)
{
tagNode* pNewNode = NULL;

if( pNewNode = (tagNode*)AllocNode() )
{
pNewNode->pData = pnewElement;
pNewNode->stKey = stKey;

if( NULL == m_pHead )
{
m_pHead = pNewNode;
m_pTail = pNewNode;
}
else
{
//添加到末尾
m_pTail->pstNext = pNewNode;
pNewNode->pstPrev = m_pTail; 
m_pTail = pNewNode;
}

m_nCount++;

}

return pNewNode;
}
//查找
HID CfKeyPtrDeque::FindKey(const GUID & stKey)
{
tagNode * pFind = NULL;

tagNode * pFindHead = m_pHead; //头
tagNode * pFindTail = m_pTail;//尾
//查找次数
int nHalf = (m_nCount/2)+(m_nCount%2);

for( int nIndex = 0 ; nIndex < nHalf ; nIndex++ )
{

if( pFindHead )
{
if( pFindHead->stKey == stKey )
{
pFind = pFindHead;
break;
}
//下一条
pFindHead = pFindHead->pstNext;
}


if( pFindTail )
{
if( pFindTail->stKey == stKey )
{
pFind = pFindTail;
break;
}
//上一条
pFindTail = pFindTail->pstPrev;
}
}

return pFind;
}//头
HID CfKeyPtrDeque::GetHeadPosition()
{
return m_pHead;
}
//尾
HID CfKeyPtrDeque::GetTailPosition()
{
return m_pTail;
}
//写
BOOL CfKeyPtrDeque::SetAt(HID pNode,void * pnewElement,GUID * pstKey /*= NULL*/)
{
BOOL bResult  = FALSE;

if( bResult  = (NULL != pNode) )
{
((tagNode*)pNode)->pData = pnewElement;

if( pstKey )
((tagNode*)pNode)->stKey = *pstKey;
}

return bResult;
}
BOOL CfKeyPtrDeque::GetAt(HID pNode,GUID & stKey,void *& poldElement)
{
BOOL bResult  = FALSE;

if( bResult  = (NULL != pNode) )
{
//
poldElement = ((tagNode*)pNode)->pData;
//
stKey = ((tagNode*)pNode)->stKey;
} return bResult;
}//
BOOL CfKeyPtrDeque::GetNext(HID& pNextNode,GUID & stKey,void *& poldElement)
{
BOOL bResult  = FALSE; if( bResult  = (NULL != pNextNode) )
{
//
poldElement = ((tagNode*)pNextNode)->pData;
//
stKey = ((tagNode*)pNextNode)->stKey;
//
pNextNode = ((tagNode*)pNextNode)->pstNext; }
return bResult;
}//
BOOL CfKeyPtrDeque::GetPrev(HID& pPrevNode,GUID & stKey,void *& poldElement)
{
BOOL bResult  = FALSE; if( bResult  = (NULL != pPrevNode) )
{
//
poldElement = ((tagNode*)pPrevNode)->pData;
//
stKey = ((tagNode*)pPrevNode)->stKey;
//
pPrevNode = ((tagNode*)pPrevNode)->pstPrev;

}
return bResult;
}BOOL CfKeyPtrDeque::RemoveAt(HID pNode)
{
BOOL bResult  = FALSE; if( bResult  = (NULL != pNode) )
{
CutNode((tagNode*)pNode);
} return bResult;
}
void CfKeyPtrDeque::RemoveAll()
{
tagNode* pCfr = m_pHead; while(pCfr)
{
m_pHead = pCfr->pstNext;
FreeNode( pCfr);
pCfr=m_pHead;
} m_pHead = NULL;
m_pTail = NULL;
m_nCount = 0;
}int CfKeyPtrDeque::GetCount()
{
return m_nCount;
}//////////////////////////////////////////////////////////////////////
CfPtrHash::CfPtrHash()
{
m_pHashBulk = NULL;
m_nBulkSize = 0;
m_nCount = 0; 
m_pEnumHID = NULL;
m_nEnumHashValue = 0;
}CfPtrHash::~CfPtrHash()
{
RemoveAll();
}
BOOL CfPtrHash::Create(int nBulkSize)
{


if( nBulkSize > 0  && m_pHashBulk == NULL )
{
m_nBulkSize = nBulkSize;
m_pHashBulk = new CfKeyPtrDeque[m_nBulkSize];
} return (m_pHashBulk != NULL);
}//
BOOL CfPtrHash::SetAt(const GUID & stKey,void* pnewElement)
{
BOOL bResult = FALSE; if( m_pHashBulk )
{
int nHash = (KeyValue(stKey)%m_nBulkSize);

HID pID = m_pHashBulk[nHash].FindKey(stKey);
if( pID )
{
//新值
bResult = m_pHashBulk[nHash].SetAt(pID,pnewElement);
}
else
{
if( bResult = (NULL != m_pHashBulk[nHash].AddTail(stKey,pnewElement)) )
m_nCount++;

}
}
return bResult;
}//
BOOL CfPtrHash::RemoveKey(const GUID & stKey)
{


BOOL bResult = FALSE; if( m_pHashBulk )
{
int nHash = (KeyValue(stKey)%m_nBulkSize);

HID pID = m_pHashBulk[nHash].FindKey(stKey);
if( pID )
{
//如果当前项为枚举项,则跳过
if( m_pEnumHID == pID )
{
GUID  s = {0};
void * p = NULL;

m_pHashBulk[m_nEnumHashValue].GetNext(m_pEnumHID,s,p);

}

//删除
if( bResult = m_pHashBulk[nHash].RemoveAt(pID) )
m_nCount--;
}
}
return bResult;
}//
BOOL CfPtrHash::Lookup(const GUID & stKey,void*& poldElement)
{
BOOL bResult = FALSE; if( m_pHashBulk )
{
int nHash = (KeyValue(stKey)%m_nBulkSize);

HID pID = m_pHashBulk[nHash].FindKey(stKey);
if( pID )
{
GUID s = {0};
bResult = m_pHashBulk[nHash].GetAt(pID,s,poldElement);
}
} return bResult;
}
//
BOOL CfPtrHash::ElementFirst(GUID & stKey,void*& poldElement)
{
BOOL bResult = FALSE; if( m_pHashBulk )
{
//初始化
m_pEnumHID = NULL;
m_nEnumHashValue = m_nBulkSize;

for( int n = 0; n < m_nBulkSize ; n++ )
if( m_nEnumHashValue = n,m_pEnumHID = m_pHashBulk[n].GetHeadPosition() )
break;

if( m_pEnumHID && m_nEnumHashValue < m_nBulkSize )
bResult =  m_pHashBulk[m_nEnumHashValue].GetNext(m_pEnumHID,stKey,poldElement);
} return bResult;
}
//
BOOL CfPtrHash::ElementNext(GUID & stKey,void*& poldElement)
{
BOOL bResult = FALSE;

if( m_pHashBulk )
{
//
if( m_pEnumHID == NULL )
for( int n = m_nEnumHashValue+1; n < m_nBulkSize ; n++ )
if( m_nEnumHashValue = n,m_pEnumHID = m_pHashBulk[n].GetHeadPosition() )
break;

if( m_pEnumHID && m_nEnumHashValue < m_nBulkSize )
bResult =  m_pHashBulk[m_nEnumHashValue].GetNext(m_pEnumHID,stKey,poldElement);
} return bResult;
}
//
void CfPtrHash::RemoveAll()
{
if(m_pHashBulk)
{
for( int n = 0; n < m_nBulkSize ; n++ )
 m_pHashBulk[n].RemoveAll();
delete []m_pHashBulk;
}
m_pHashBulk = NULL;
m_nBulkSize = 0;
m_nCount = 0; 
m_pEnumHID = NULL;
m_nEnumHashValue = 0;
}//
int  CfPtrHash::GetBulkSize() 
{


return m_nBulkSize;
}//
int  CfPtrHash::GetCount() 
{


return m_nCount;
}UINT CfPtrHash::KeyValue(const GUID & stKey)
{
return stKey.Data1;
}
///////////////////////////////////////////////////////////////////////////////////////////////