一个通用HASH算法的实现

一个通用HASH算法的实现

由于在项目中需要使用到不同关键字类型（整数，字符串等）来构建hash表，可以使用一个较为通用的hash表操作算法来实现。

1：支持多种关键字类型。

2：支持hash表的动态扩大。

3：通过双向链表链接所有元素，方便hash表的动态扩展和清空。

 一个实例：hash值1、3、5、7中存在对应的元素节点，这些元素节点又互相链接并由一个pHead节点指向。

数据结构定义：

每个元素是双向链表的节点。

pFirstElem是链表的头结点，通过该节点可以快速遍历所有元素。

View Code

#define STR_TYPE 0
#define INT_TYPE 1

typedef struct elem_s elem_t, *elemPtr_t;
struct elem_s
{
    void* pData;
    void* pKey;
    int nkey;
    elemPtr_t pNext;
    elemPtr_t pPre;
};

typedef struct hashBucket_s hashBucket_t, *hashBucketPtr_t;
struct hashBucket_s
{
    int eCount;           // number of entries with the bucket
    elemPtr_t pChain; // pointer to the first entry with the hash
};

typedef struct hash_s hash_t,*hashPtr_t;
struct hash_s
{
    int keyType;    // hash key type
    int eCount;       // number of entries in this table
    int bSize;         // number of buckets in this table
    elemPtr_t pFirstElem; //the first element in this table
    hashBucketPtr_t pHashTable; //the hash table
};

hash表的初始化：

增加了关键字的hash类型，目前支持int和string。

View Code

void InitHashTable(hashPtr_t pHash, int keyType)
{
    assert(pHash);
    assert((STR_TYPE==keyType) ||(INT_TYPE==keyType));
    
    pHash->bSize = 0;
    pHash->eCount =0;
    pHash->keyType = keyType;
    pHash->pFirstElem = NULL;
    pHash->pHashTable = NULL;

    return;
}

数据插入hash表中：

不允许插入相同的关键字数据

表的初始bucket个数为8，当数据个数超过bucket的个数对原有表的bucket个数扩大一倍，并将老表中的数据重新散列到新表。

View Code

int InsertHashElem(hashPtr_t pHash, const void* pKey, int nKey, const void* pData)
{
    int hashValue                         = 0;
    hashBucket_t hashBucket         = {0};
    elemPtr_t pNewElem                = NULL;
    
    assert(pHash && pKey && pData && nKey);
    
    if(FindHashElem(pHash,pKey,nKey))
    {
        return HASH_FALSE;
    }
    
    initNewElem(&pNewElem,pKey,nKey,pData);

    if(NULL == pHash->pHashTable)
    {
        /*initial bucket number is 8*/
        resizeHashTable(pHash, 8);
    }
    
    hashValue = getHashValue(pHash,pKey,nKey);
    insertElem(pHash,pNewElem,hashValue);

    if(pHash->eCount >= pHash->bSize)
    {
         resizeHashTable(pHash, 2*pHash->bSize);
    }

    return HASH_TRUE;
}

在hash表中查找指定的数据：

根据hash的关键字类型返回对应的比较函数，这里采用了工厂模式的思想，这样设计有助于算法只关注本身的逻辑，算法本身符合开闭原则。

View Code

void* FindHashElem(const hash_t *pHash, const void *pKey, int nKey)
{
    hashFun xHashFun                   = NULL;
    compareFun xCompareFun    = NULL;
    hashBucket_t hashBucket      = {0};
    elemPtr_t pElem                       = NULL;
    void *pData                                = NULL;
    int hashValue                             = 0;
    int count                                      = 0;
    
    assert(pHash && pKey && nKey);

    if(NULL == pHash->pHashTable)
    {
        return NULL;
    }

    hashValue = getHashValue(pHash,pKey,nKey);
    
    hashBucket = pHash->pHashTable[hashValue];
    pElem = hashBucket.pChain;
    count = hashBucket.eCount;

    xCompareFun = getCompareFun(pHash->keyType);
    while(pElem && count--)
    {
        if(HASH_TRUE == xCompareFun(pElem->pKey,pElem->nkey,pKey,nKey))
        {
            pData = pElem->pData;
            break;
        }

        pElem = pElem->pNext;
    }

    return pData;
}

移除hash表中指定的元素：

主要是一个双向链表的操作和bucket指针的调整

View Code

void RemoveElem(hashPtr_t pHash, const void* pKey, int nKey)
{
    int hashValue                           = 0;
    int eCount                                 = 0;           
    elemPtr_t pChain                    = NULL; 
    compareFun  xCompareFun = NULL;

    assert(pHash && pKey);
    
    hashValue = getHashValue(pHash,pKey,nKey);
    xCompareFun = getCompareFun(pHash->keyType);

    eCount = pHash->pHashTable[hashValue].eCount;
    pChain = pHash->pHashTable[hashValue].pChain;

    while((eCount--) && pChain)
    {
        if(HASH_TRUE == xCompareFun(pChain->pKey,pChain->nkey,pKey,nKey))
        {
            if(pChain == pHash->pFirstElem)
            {
                pHash->pFirstElem = pChain->pNext;
                pHash->pHashTable[hashValue].eCount--;
                if(0 == pHash->pHashTable[hashValue].eCount)
                {
                    pHash->pHashTable[hashValue].pChain = NULL;
                }
            }else
            {
                pChain->pPre->pNext = pChain->pNext;
                pChain->pNext->pPre = pChain->pPre;
                pHash->pHashTable[hashValue].eCount--;
                if(0 == pHash->pHashTable[hashValue].eCount)
                {
                    pHash->pHashTable[hashValue].pChain = NULL;
                }else
                {
                     if(pChain == pHash->pHashTable[hashValue].pChain)
                     {
                         pHash->pHashTable[hashValue].pChain = pChain->pNext;
                     }
                }
            }
            free(pChain);
            pChain = NULL;
            pHash->eCount--;
            break;
        }
        pChain = pChain->pNext;
    }

    return;
}

释放hash表：

由于所有的元素在一个双向链表中，释放数据十分简单

View Code

void ClearHash(hash_t *pHash)
{
    int eCount                                   = 0;
    elemPtr_t pElem                       = NULL;
    elemPtr_t pNextElem               = NULL;
    
    assert(pHash && pHash->pHashTable && pHash->pFirstElem);

    eCount = pHash->eCount;
    pElem = pHash-> pFirstElem;
    while((eCount--) && pElem)
    {
        pNextElem = pElem->pNext;
        free(pElem);
        pElem = pNextElem;
    }

    free(pHash->pHashTable);
    pHash->pHashTable = NULL;
    pHash-> pFirstElem = NULL;
    pHash->eCount = 0;
    pHash->bSize = 0;
    return;
}

转载请注明原始出处：http://www.cnblogs.com/chencheng/archive/2012/08/13/2637216.html