C++ Hash表模板

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]算法分析:哈希表的大小为何是素数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习原理

图数据库neo4j介绍(3)——CypherCreateMatchSetDELETE REMOVE

Match (n:Person {id:'baba'}) set n.name='张三',n.age=50 return n

772
来自专栏JavaQ

温故而知新-MySQL数据类型

选择数据类型的原则 MySQL支持多种数据类型,选择合适的数据类型存储数据对MySQL存储引擎来说至关重要,下面的一些原则可以在选择数据类型的时候做出更合适的选...

3107
来自专栏开发与安全

从零开始学C++之对象的使用(三):static 与单例模式、auto_ptr与单例模式、const 用法小结、mutable修饰符

一、static 与单例模式 单例模式也就是简单的一种设计模式,它需要: 保证一个类只有一个实例,并提供一个全局访问点 禁止拷贝 #include <i...

2120
来自专栏乐沙弥的世界

PL/SQL 集合的方法

    PL/SQL中提供了常用的三种集合联合数组、嵌套表、变长数组,而对于这几个集合类型中元素的操作,PL/SQL提供了相应的函数或过程来操 纵数组中的元素...

823
来自专栏desperate633

第14课 组合查询创建组合查询union的使用规则

组合查询很容易理解就是讲多个查询的结果放在一起显示 使用UNION关键字进行查询的组合

722
来自专栏Python

表的数据类型

一 介绍 存储引擎决定了表的类型,而表内存放的数据也要有不同的类型,每种数据类型都有自己的宽度,但宽度是可选的 详细参考: http://www.runoob....

2107
来自专栏Clive的技术分享

PHP实现单例模式

<?php /** * 单例模式实现 */ class Singleton { //静态变量保存全局实例 private static $ins...

3007
来自专栏jeremy的技术点滴

实例变量的懒初始化

3214
来自专栏xiaoxi666的专栏

Trie树/字典树题目(2017今日头条笔试题:异或)

关于trie数的其他应用,可参见http://www.cnblogs.com/dlutxm/archive/2011/10/26/2225660.html,感觉...

1943
来自专栏企鹅号快讯

谈谈 MySQL 隐式类型转换

来源:andyqian www.andyqian.com/2017/11/11/database/MySQLConvert/ 前言 今天我们继续回到MySQL系...

45311

扫码关注云+社区

领取腾讯云代金券