首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++ Hash表模板

C++ Hash表模板

作者头像
恋喵大鲤鱼
发布2018-08-03 10:58:48
2K0
发布2018-08-03 10:58:48
举报
文章被收录于专栏:C/C++基础C/C++基础

1.简介

利用C++类模板实现任意类型的Hash表,提供的功能有: (1)指定shmkey或内存地址创建Hash表; (2)获取指定key元素; (3)遍历指定范围的元素,进行指定操作。

备注:采用小于hash表大小的大质数尽量减少冲突,因为模的因子最少,冲突最少。因子最少的就是素数了。具体解释参见:算法分析:哈希表的大小为何是素数

缺点:该hash表模板未实现动态扩展,hash表容量不足时,需要重新指定空间后初始化。

源码也可以在 github地址 下载。

2.具体实现

实现代码写入头文件hashTableTemplate.h中。

//
//hashTableTemplate.h
//

/************************************************************
*@DESCRIPTION: hash table template
*@BIRTH:created by linchunlv
*@REVISION:last modified by dablelv on 20180326
*************************************************************/

#ifndef HASH_TABLE_TEMPLATE_H
#define HASH_TABLE_TEMPLATE_H

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <sys/shm.h>
#include <stdint.h>
#include <string.h>
#ifndef DDWORD
    #define DDWORD uint64_t
#endif
#ifndef DWORD
    #define DWORD uint32_t
#endif
#ifndef WORD
    #define WORD uint16_t
#endif
#ifndef BYTE 
    #define BYTE uint8_t
#endif

/************************************
*@brief:determine whether a number is a prime number
*************************************/
static int HashT_IsPrimeNum(uint32_t n)
{
    if(1==n)
    {
        return 0;
    }
    int i=0;
    double k = sqrt((double)n);
    for(i=2; i<= k; i++)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}

/**************************************************
*@brief:create or get shared memory segment
*@ret:return address of shared memory segment
***************************************************/
static char* HashT_GetShm(key_t iKey, size_t Size, int iFlag)
{
    int iShmID;
    char* sShm;
    char sErrMsg[128]={0};

    if((iShmID=shmget(iKey,Size,iFlag))<0)
    {
        snprintf(sErrMsg,sizeof(sErrMsg),"%s %s %u shmget key 0x%x %zu",__FILE__,__FUNCTION__,__LINE__,iKey,Size);
        perror(sErrMsg);
        return NULL;
    }

    if ((sShm = (char*)shmat(iShmID, NULL ,0)) == (char *) -1)
    {
        snprintf(sErrMsg,sizeof(sErrMsg),"%s %s %u shmat shmid %d",__FILE__,__FUNCTION__,__LINE__,iShmID);
        perror(sErrMsg);
        return NULL;
    }
    return sShm;
}

/***************************
*@brief:create or get shared memory segment version 2
*@ret:0 is returned on success, -1 on error
****************************/
static int HashT_GetShm2(void **pstShm, key_t iShmKey, size_t Size, int iFlag)
{
    char* sShm;

    //获取现有共享内存失败
    if(!(sShm = HashT_GetShm(iShmKey, Size, iFlag & (~IPC_CREAT))))
    {
        //不是创建标识,返回错误
        if(!(iFlag & IPC_CREAT)) return -1;

        //创建新共享内存
        if (!(sShm = HashT_GetShm(iShmKey, Size, iFlag))) return -1;
        memset(sShm, 0, Size);
    }
    *pstShm = sShm;
    return 0;
}

/************************************
*@brief:hash table template
*@param:Element_T:元素类型;Key_T:元素键值类型;nHashLen:hash表长度;nHashTime:hash表数量
*@author:anonymous person
*@date:unknown
*@revison:
************************************/
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
class CHashTable
{
public:
#pragma pack(1)
    typedef Element_T (* TableP_T)[nHashLen];
#pragma pack()
    typedef int (* ElementEmptyFunc_T)(Element_T* pE,void* pExt);
    typedef int (* ElementSameFunc_T)(Element_T* pE,Key_T key,void* pExt);
    typedef int (* ElementDoFunc_T)(Element_T* pE,void* pExt);

    CHashTable();
    ~CHashTable(){}
    int Initialize(int nHashKey,ElementSameFunc_T IfElementSameFunc=NULL,ElementEmptyFunc_T IfElementEmptyFunc=NULL);
    int Initialize(int nHashKey,DWORD ElementExpiredSec);
    int Initialize(void* pMem,size_t MemSize,ElementSameFunc_T IfElementSameFunc=NULL,ElementEmptyFunc_T IfElementEmptyFunc=NULL);
    int Initialize(void* pMem,size_t MemSize,DWORD ElementExpiredSec);
    size_t GetRequiredMemSize()
    {
        return nHashLen*nHashTime*sizeof(Element_T)+(size_t)32*sizeof(DWORD);
    }
    int AttachToMem(void* pMem, size_t MemSize);
    int Reset()
    {
        memset(m_TableP,0,nHashLen*nHashTime*sizeof(Element_T));
        return 0;
    }
    Element_T* GetElement(Key_T key,void* pExt=NULL);
    Element_T* GetNewSpace(Key_T key,void* pExt=NULL);
    int DoForEach(int* piBeginTimePos,int* piBeginLenPos,int iScanNodes,ElementDoFunc_T ElementDoFunc,void* pExt=NULL);

    TableP_T GetTableP()
    {
        return m_TableP;
    }
    int GetStat(DWORD* pdwStat)
    {
        *pdwStat=*m_pStat;
        return 0;
    }
    int SetStat(DWORD dwStat)
    {
        *m_pStat=dwStat;
        return 0;
    }

private:
    int Initialize(int nHashKey,void* pMem,size_t MemSize,ElementSameFunc_T IfElementSameFunc,ElementEmptyFunc_T IfElementEmptyFunc,DWORD ElementExpiredSec);

private:
    TableP_T m_TableP;
    ElementSameFunc_T m_IfElementSameFunc;
    ElementEmptyFunc_T m_IfElementEmptyFunc;
    DWORD m_ElementExpiredSec;
    int m_HashKey;
    DWORD m_HashBase[nHashTime];
    DWORD* m_pStat;
};

//构造函数
template<class Element_T,class Key_T,int nHashLen,int nHashTime> CHashTable<Element_T,Key_T,nHashLen,nHashTime>::CHashTable()
{
    m_IfElementSameFunc=NULL;
    m_IfElementEmptyFunc=NULL;
    m_HashKey=0;
    m_ElementExpiredSec=0;
}

//@brief:初始化Hash表
//@param:nHashKey:shmkey;ElementExpiredSec:生命周期
template<class Element_T,class Key_T,int nHashLen,int nHashTime> int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::Initialize(int nHashKey,DWORD ElementExpiredSec)
{
    return Initialize(nHashKey,NULL,0,NULL,NULL,ElementExpiredSec);
}

//@brief:初始化Hash表
//@param:nHashKey:shmkey;IfElementSameFunc:操纵符元素是否相等;IfElementEmptyFunc:操纵符元素是否为空
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::Initialize(int nHashKey,ElementSameFunc_T IfElementSameFunc,ElementEmptyFunc_T IfElementEmptyFunc)
{
    return  Initialize(nHashKey,NULL,0,IfElementSameFunc,IfElementEmptyFunc,0);
}

//@brief:初始化Hash表
//@param:pMem:内存地址;MemSize:内存空间大小;ElementExpiredSec:生命周期
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::Initialize(void* pMem,size_t MemSize,DWORD ElementExpiredSec)
{
    return Initialize(0,pMem,MemSize,NULL,NULL,ElementExpiredSec);
}

//@brief:初始化Hash表
//@param:pMem:内存地址;MemSize:内存空间大小;IfElementSameFunc:操纵符元素是否相等;IfElementEmptyFunc:操纵符元素是否为空
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::Initialize(void* pMem,size_t MemSize,ElementSameFunc_T IfElementSameFunc,ElementEmptyFunc_T IfElementEmptyFunc)
{
    return  Initialize(0,pMem,MemSize,IfElementSameFunc,IfElementEmptyFunc,0);
}

//@brief:初始化Hash表
//@param:nHashKey:shmkey;pMem:内存地址;MemSize:内存区域大小;IfElementSameFunc:操纵符元素是否相等;IfElementEmptyFunc:操纵符元素是否为空;ElementExpiredSec:生命周期
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::Initialize(int nHashKey,void* pMem,size_t MemSize,ElementSameFunc_T IfElementSameFunc,ElementEmptyFunc_T IfElementEmptyFunc,DWORD ElementExpiredSec)
{
    int nRet=0;
    if (nHashKey<=0 && (NULL==pMem || 0==MemSize)) return -1;
    if (nHashKey>0 && (NULL!=pMem && MemSize>0)) return -1;
    size_t RequiredMemSize=GetRequiredMemSize();

    m_HashKey=nHashKey;
    m_IfElementSameFunc=IfElementSameFunc;
    m_IfElementEmptyFunc=IfElementEmptyFunc;
    m_ElementExpiredSec=ElementExpiredSec;
    if (nHashKey>0)
    {
        if( HashT_GetShm2((void**)&m_TableP, m_HashKey, RequiredMemSize, 0600) < 0 )
        {
            if( HashT_GetShm2((void**)&m_TableP, m_HashKey, RequiredMemSize, 0600|IPC_CREAT) < 0 )
            {
                printf("GetShm2 %x Error\n",m_HashKey);
                return -1;
            }
            else
            {
                nRet=1;//first allocate the mem;
            }
        }
        m_pStat=(DWORD*)( (char*)m_TableP + nHashLen*nHashTime*sizeof(Element_T) );
    }
    else if (NULL != pMem && MemSize > 0)
    {
        if (MemSize < RequiredMemSize)
        {
            printf("hash_template init err: MemSize[%zu] < RequriedMemSize[%zu]\n", MemSize, RequiredMemSize);
            return -1;
        }
        m_TableP=(TableP_T)pMem;
        m_pStat=(DWORD*)( (char*)m_TableP + nHashLen*nHashTime*sizeof(Element_T) );
    }
    else
    {
        return -1;
    }

    //采用大质数作为hash表的模
    uint64_t ulStep=(nHashLen & 1)?nHashLen:(nHashLen-1);
    int nNum = nHashTime;
    for(; ; ulStep -=2)
    {
        if(nNum == 0)break;
        if(HashT_IsPrimeNum(ulStep))
        {
            m_HashBase[nHashTime-nNum]=ulStep;
            nNum--;
        }   
    }
    return nRet;
}

//@brief:获取元素
//@param:key:元素key;pExt:扩展参数
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
Element_T* CHashTable<Element_T,Key_T,nHashLen,nHashTime>::GetElement(Key_T key,void* pExt)
{
    int i, hash;
    Element_T* pE = NULL;

    for(i=0; i<nHashTime; ++i)
    {
        hash = key % m_HashBase[i];
        pE = &(m_TableP[i][hash]);
        if(m_IfElementSameFunc != NULL)
        {
            if(m_IfElementSameFunc(pE,key,pExt))return pE;
        }
        else
        {
            DWORD dwCurTime=time(NULL);
            Key_T* pcurkey=(Key_T*)pE;
            DWORD* pdwStartTime=(DWORD*)((char*)pE+sizeof(Key_T));
            if(*pcurkey == key && (m_ElementExpiredSec==0 || *pdwStartTime > dwCurTime - m_ElementExpiredSec))return pE;
        }
    }
    return NULL;
}

//@brief:获取新元素空间
//@param:key:元素key;pExt:扩展参数
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
Element_T* CHashTable<Element_T,Key_T,nHashLen,nHashTime>::GetNewSpace(Key_T key,void* pExt)
{
    int i, hash;
    Element_T *pE = NULL;

    for(i=0; i<nHashTime; ++i)
    {
        hash = key % m_HashBase[i];
        pE = &(m_TableP[i][hash]);
        if(m_IfElementEmptyFunc != NULL)
        {
            if(m_IfElementEmptyFunc(pE,pExt))return pE;
        }
        else
        {
            DWORD dwCurTime=time(NULL);
            Key_T* pcurkey=(Key_T*)pE;
            DWORD* pdwStartTime=(DWORD*)((char*)pE+sizeof(Key_T));
            if(*pcurkey == 0)return pE;
            if(m_ElementExpiredSec>0 && *pdwStartTime <= dwCurTime - m_ElementExpiredSec)return pE;
        }
    }

    return NULL;
}

//@brief:遍历指定的元素做相应的操作
//@param:piBeginTimePos:hash桶下标;piBeginLenPos:桶内元素下标;iScanNodes:扫描元素个数;ElementDoFunc:操纵符;pExt:扩展参数
template<class Element_T,class Key_T,int nHashLen,int nHashTime>
int CHashTable<Element_T,Key_T,nHashLen,nHashTime>::DoForEach(int* piBeginTimePos,int* piBeginLenPos,int iScanNodes,ElementDoFunc_T ElementDoFunc,void* pExt)
{
    Element_T *pE = NULL;
    if(piBeginTimePos==NULL || piBeginLenPos==NULL)return -1;
    if(*piBeginTimePos>=nHashTime || *piBeginLenPos>=nHashLen)return -2;
    if(ElementDoFunc==NULL)return -3;
    if(iScanNodes<=0)return -4;

    int iTimes=0;
    for( ; *piBeginTimePos < nHashTime; *piBeginTimePos=(*piBeginTimePos+1)%nHashTime )
    {
        for( ; *piBeginLenPos < nHashLen; ++(*piBeginLenPos) )
        {
            if ( ++iTimes > iScanNodes )
            {
                return 0;
            }
            pE = &(m_TableP[*piBeginTimePos][*piBeginLenPos]);
            ElementDoFunc(pE,pExt);
        }
        *piBeginLenPos=0;
    }
    return 0;
}
#endif  //HASH_TEMPLATE_H

3.使用demo

使用时,包含头文件即可。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#include <iostream>
using namespace std;

#include "hashTableTemplate.h"

#define UIN_HASH_SHMKEY         0x7ab90327
#define UIN_HASH_LEN            500000
#define UIN_HASH_TIME           20
#define UIN_HASH_CLEAR_TIME     (3600*2)

struct STUINElmt
{
    uint32_t    dwUIN;          //QQ
    uint32_t    dwStartTime;    //记录时间,注意,位置不能变,必须在key之后
    uint32_t    dwFlag;         //UIN标识
    uint32_t    dwReqCnt;       //请求的次数
};

typedef CHashTable<STUINElmt,uint32_t,UIN_HASH_LEN,UIN_HASH_TIME> UINHashTable_T;
UINHashTable_T objUinHashTab;

int main(int argc,char* argv[])
{
    //初始化Hash表
    int iRet = objUinHashTab.Initialize(UIN_HASH_SHMKEY,UIN_HASH_CLEAR_TIME);
    if (iRet < 0)
    {
        printf("UinHashTable Initialize Error %d\n", iRet);
        return -1;
    }

    //获取指定UIN对应的元素
    uint32_t dwUIN=1589276509U;
    STUINElmt *pUINElmt = objUinHashTab.GetElement(dwUIN);
    if (NULL == pUINElmt)
    {
        //元素不存在,则从Hash表中获取空闲空间
        pUINElmt = objUinHashTab.GetNewSpace(dwUIN);
        if (NULL != pUINElmt)
        {
            memset(pUINElmt,0,sizeof(STUINElmt));
            pUINElmt->dwUIN = dwUIN;
            pUINElmt->dwStartTime = time(NULL);
            pUINElmt->dwFlag = 0x0;
        }
    }

    if(NULL==pUINElmt)
    {
        printf("get element key %u failed\n",dwUIN);
        return -1;
    }

    //每一次执行程序,标识该UIN请求次数加一
    ++pUINElmt->dwReqCnt;

    //再次从Hash表获取指定key元素
    STUINElmt *pUINElmt1=objUinHashTab.GetElement(dwUIN);
    printf("dwUIN %u startT %u flag 0x%x reqCnt %u \n",pUINElmt1->dwUIN,pUINElmt1->dwStartTime,pUINElmt1->dwFlag,pUINElmt1->dwReqCnt);
}

参考文献

[1]算法分析:哈希表的大小为何是素数

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年03月27日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.简介
  • 2.具体实现
  • 3.使用demo
  • 参考文献
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档