基本概念

 所谓完美哈希函数，就是指没有冲突的哈希函数，即对任意的 key1 != key2 有h(key1) != h(key2)。

 设定义域为X，值域为Y, n=|X|,m=|Y|，那么肯定有m>=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2)，那么称h为完美哈希函数，当m=n时，h称为最小完美哈希函数（这个时候就是一一映射了）。

 

 在处理大规模字符串数据时，经常要为每个字符串分配一个整数ID。这就需要一个字符串的哈希函数。怎么样找到一个完美的字符串hash函数呢？

 
有一些常用的字符串hash函数。像BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。都是比较经典的。
 
常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
 
 常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。
 
 
 
 Hash函数
 数据1
 数据2
 数据3
 数据4
 数据1得分
 数据2得分
 数据3得分
 数据4得分
 平均分
 BKDRHash
 2
 0
 4774
 481
 96.55
 100
 90.95
 82.05
 92.64
 APHash
 2
 3
 4754
 493
 96.55
 88.46
 100
 51.28
 86.28
 DJBHash
 2
 2
 4975
 474
 96.55
 92.31
 0
 100
 83.43
 JSHash
 1
 4
 4761
 506
 100
 84.62
 96.83
 17.95
 81.94
 RSHash
 1
 0
 4861
 505
 100
 100
 51.58
 20.51
 75.96
 SDBMHash
 3
 2
 4849
 504
 93.1
 92.31
 57.01
 23.08
 72.41
 PJWHash
 30
 26
 4878
 513
 0
 0
 43.89
 0
 21.95
 ELFHash
 30
 26
 4878
 513
 0
 0
 43.89
 0
 21.95
 
 其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

 

 

 经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

 
 

unsigned int SDBMHash(char *str)
{
    unsigned int hash = 0;
 
    while (*str)
    {
        // equivalent to: hash = 65599*hash + (*str++);
        hash = (*str++) + (hash << 6) + (hash << 16) - hash;
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int RSHash(char *str)
{
    unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;
 
    while (*str)
    {
        hash = hash * a + (*str++);
        a *= b;
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned int hash = 1315423911;
 
    while (*str)
    {
        hash ^= ((hash << 5) + (*str++) + (hash >> 2));
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
    unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
    unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
    unsigned int OneEighth        = (unsigned int)(BitsInUnignedInt / 8);
    unsigned int HighBits         = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
    unsigned int hash             = 0;
    unsigned int test             = 0;
 
    while (*str)
    {
        hash = (hash << OneEighth) + (*str++);
        if ((test = hash & HighBits) != 0)
        {
            hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
        }
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int ELFHash(char *str)
{
    unsigned int hash = 0;
    unsigned int x    = 0;
 
    while (*str)
    {
        hash = (hash << 4) + (*str++);
        if ((x = hash & 0xF0000000L) != 0)
        {
            hash ^= (x >> 24);
            hash &= ~x;
        }
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
 
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned int hash = 5381;
 
    while (*str)
    {
        hash += (hash << 5) + (*str++);
    }
 
    return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned int hash = 0;
    int i;
 
    for (i=0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
    }
 
    return (hash & 0x7FFFFFFF);
}

 
编程珠玑中的一个hash函数

 
 

//用跟元素个数最接近的质数作为散列表的大小
#define NHASH 29989
#define MULT 31

unsigned in hash(char *p)
{
    unsigned int h = 0;
    for (; *p; p++)
        h = MULT *h + *p;
    return h % NHASH;
}

 

 

散列（哈希）：
 
    是在记录的存储位置和它的关键字之间建立一个确定的映射关系f,使得每个关键字key对应一个存储位置（参考大话数据结构8.9-8.12）。
    存储位置=f(key)f称为散列函数，又称为哈希函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。
    哈希是用来解决查找与给定值相等的位置。
    设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
    散列冲突：两个key1 != key2,但是f(key1) == f(key2),不同的key值对应相同的位置，称为散列冲突。
散列函数的构造方法：
 
1.直接定址法：关键字的某个线性函数值为散列地址，即f(key) = a*key+b。
   优点是简单，均匀，也不会产生散列冲突（f(key)与key从二维坐标来看是线性关系，自然不会冲突）。
   但是需要预先知道key值的分布情况（比如key_1=1000,key_2=2000,如果不根据分布情况来设计散列函数，会造成存储空间的极大浪费）。
 2.数字分析法、平方取中法、除留取余法、随机数法。
 
处理散列冲突的方法：
 
1.开放定址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表够大，就不会出现散列冲突。也称为线性探测法。在此基础上增加平方运算称为二次探测法。
 2.再散列函数法：准备多个散列函数，当发生冲突时，就换一个散列函数计算（增加计算成本，有概率还是会出现散列冲突）。
 3.链地址法：将f(key)相等的key放在一个链表里，冲突一次就增加一个节点。
 4.公共溢出区法
 

散列表查找性能分析：
 
如果没有冲突，时间复杂度O(1)。
 平均查找查找长度取决于：
 1.散列函数是否均匀。
 2.处理冲突的方式    
 3.散列表的装填因子=表中的记录个数/散列表的长度。表示着散列表的装满程度。这个值越大，再次填入时产生冲突的可能性越高。
 通常会将散列表的空间设置的比查找集合大一些，通过空间换时间的方式降低平均查找长度。
 
C语言代码实现如下：
 
将人的id作为key值，体重作为待查找数据，实现哈希。注意，这块代码大话数据结构里面写的不好，没有插入实际数据，自己基于理解进行了代码实现。
 
哈希函数使用除留取余法。注意在hash create时和search时对冲突的处理。
 
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<signal.h>  
#include<string.h>
#include<sys/stat.h>
#include<time.h>
#include<stdarg.h>

#if 1
#define INFO_DEBUG    "%d lines in "__FILE__", complie time is "__TIME__" "__DATE__" \n",__LINE__
#define ADI_RUN_ERROR      1
#define ADI_NULL_POINTER  -1
#define ADI_OK             0
#define ADI_PRINT         printf("[%s][%d]:",__FUNCTION__,__LINE__);printf
#define ADI_ASSERT(c,prt,ret)       if(c) {printf(prt);return ret;}
#endif

#define PARAM_FAIL -1
#define P_NULL -2
#define SUCCESS 0
#define NUllKEY -32768

/*将id作为hash的key值，weight作为每个id的体重，实现根据ID查找对应的体重*/
typedef struct{
    int id;       //每个人的id
    float weight; //每个人的体重
}ELE;

typedef struct{
    ELE *elem;   //数据元素存储基地址， 
    int size;    //哈希表大小
}HashTable;

int hashSize = 12;
/*初始化hash表,num表示hash表的表长*/
int InitHashTable(HashTable *H,int num)
{
        H->size = num;
	H->elem = (ELE*)malloc(num*sizeof(ELE));
	if(NULL == H->elem)
	{
		ADI_PRINT("malloc return NULL !\n");
		return P_NULL;
	}
	for(int i=0;i<num;i++)
	{
		H->elem[i].id = NUllKEY;
	}
	return SUCCESS;
}

/*散列函数*/
int Hash(int key)
{
    return key%hashSize;//除留取余法，除数为HASH_SIZE
}

/*创建哈希表*/
int CreateHash(HashTable *H,int key,float data)
{
	int addr = Hash(key);
	while(NUllKEY != H->elem[addr].id)
	{
	    ADI_PRINT("hash hit,key = %d\n",key);//发生哈希冲突
	    addr = (addr+1)%H->size;//发生哈希冲突时，使用开放定址法解决冲突
	    /*这段代码是一个动态扩容的实现，但是如果在create hash时有动态扩容的操作，在查找时并不能知道当时动态扩容的hashsize,导致找不到对应的位置
	      比如原来hash表的size是12，因为冲突扩容到13,再14,当查找如果发生冲突并不知道扩容时的hashsize,会比较麻烦，所以通常通过申请较大的哈希表（相比于要存储的数据）来避免这个问题
	      当然我觉得在ELE中增加一个变量存储扩容时的hashsize也是一个解决方案*/
//		if(addr>(H->size-1))//addr是从0开始
//		{
//		    /*超过原有hash表内存，需要动态扩容*/
//		    ADI_PRINT("beyond hashSize, need reinit\n");
//		    int *temp = realloc((addr+1)*sizeof(ELE));//realloc 会将原内存块里的内容复制到新的内存指针中
//			if(NULL == temp)
//			{
//				ADI_PRINT("malloc return NULL !\n");
//				return P_NULL;
//			}
//	        H->elem = temp;
//	        for(int i=H->size-1;i<addr;i++)
//	        {H->elem[i].id = NUllKEY;}
//	        H->size = addr+1;
//		}	    
	}
    H->elem[addr].id = key;
    H->elem[addr].weight = data;

    return SUCCESS;
}

/*
基于hash的查找
在Hash表中，基于给定的key值，返回对应的data 
*/
int searchHash(HashTable *H,int key, float *data)
{
    int pos = Hash(key);
    while(key != H->elem[pos].id)//!=说明发生过散列冲突或者key值不存在
    {
		pos = (pos+1)%H->size;
		if(NUllKEY == H->elem[pos].id || pos == Hash(key))//key值不存在,pos == Hash(key)说明已经轮询哈希表一遍都没有
		{
			 ADI_PRINT("hash no key = %d\n",key);
		     return PARAM_FAIL;
		}
    }
    *data = H->elem[pos].weight;
    
    return SUCCESS;
}

void printHash(HashTable *H)
{
    for(int i=0;i<H->size;i++)
    {
		if(NUllKEY != H->elem[i].id)
		{
			ADI_PRINT("i = %d,id = %d,weight = %f\n",i,H->elem[i].id,H->elem[i].weight);
		}
    }
}

int main()
{
    ELE test[12] = {12,70.2,  67,71.5,  56,72.4,  16,81.5,  25,96.5,  37,98.5,  22,88.5,  29,69.5,  15,98.5,  47,77.6,  48,98.5,  34,77.6};
    HashTable hash;
    int ret = 0;
    
    ret = InitHashTable(&hash,12);
    ADI_ASSERT(ret!=SUCCESS, "init fail!\n", PARAM_FAIL);

    for(int i=0;i<12;i++)
    {
        ADI_PRINT("i=%d,test[i].id = %d, test[i].weight = %f\n",i,test[i].id,test[i].weight);
		ret = CreateHash(&hash, test[i].id, test[i].weight);
		ADI_ASSERT(ret!=SUCCESS, "create fail!\n", PARAM_FAIL);
    }
    printHash(&hash);

    int test_id = 34;
    float test_float = 0;
    ret = searchHash(&hash,test_id,&test_float);
    ADI_ASSERT(ret!=SUCCESS, "search fail!\n", PARAM_FAIL);
    ADI_PRINT("test_id = %d 's weight = %f\n",test_id,test_float);

    test_id = 100;
    ret = searchHash(&hash,test_id,&test_float);
    ADI_ASSERT(ret!=SUCCESS, "search fail!\n", PARAM_FAIL);

    return SUCCESS;
}



 
输出结果如图：
 
 
 

哈希表
 
哈希表，又称散列表，常用于在海量数据中查找数据
 
哈希表中元素是由哈希函数确定的。将数据元素的关键字key作为自变量，通过一定的函数关系H(称为哈希函数)，计算出的值，即为该元素的存储地址。其优点是：运算速度快；缺点是：基于数组、难于扩展，不可遍历。
 
在建立一个哈希表之前需要解决两个主要问题:
 
构造均匀的哈希函数 
 使H(key)均匀分布在哈希表中，以提高地址计算的速度。 
 构造哈希函数的方法：直接定址法，数字分析法，平法折中法，折叠法，除留余数法，随机数法等。
处理冲突 
 冲突是指在哈希表中，不同的关键字值对应到同一个存储位置的现象。即存在K1≠K2，但H(K1)=H(K2)。 
 再均匀的哈希函数都只能可减少冲突，但不可能避免冲突。 
 发生冲突后，必须解决，即必须寻找下一个可用地址。 
 解决冲突的方法:开放地址法（包括线性探测，二次探测，随机探测），再哈希法，链地址法，建立公共溢出区等。
 
C语言实现
 
哈希表的数据结构
 
typedef struct HashNode_Struct HashNode;  
struct HashNode_Struct  {  
    char* sKey;//键值指针
    int nValue;  //键值
    HashNode* pNext; //指向下一个哈希结构
};   
 
定义最大哈希长度及哈希数组
 
#define HASH_TABLE_MAX_SIZE 10000
HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //哈希数组
int hash_table_size;  //当前哈希长度 
 
哈希表初始化函数
 
void hash_table_init()  
{  
    hash_table_size = 0;  
    memset(hashTable, 0 , sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
    //memset(void *s,int c,size_t n); 
    //将s中后n个字节换成c所代表的内容 
    //该函数是对较大结构体或数组进行清零操作的一种最快的方法 
} 
 
去符号化函数
 
unsigned int hash_table_hash_str(const char* skey)  
{  //无符号unsigned能保存2倍与有符号类型的正整型数据 
    const signed char *p = (const signed char*)skey; //常量 
    unsigned int h = *p;  
    if(h)
    {  
        for(p += 1; *p != '\0'; ++p)  
            h = (h << 5) - h + *p;  
    }  
    return h;  
}
 
插入函数
 
void hash_table_insert(const char* skey, int nvalue)  
{  
    if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度 
    {  
        printf("内存溢出!\n");
        return;  
    }  

    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
  //用于解决冲突，pos为哈希函数 
    HashNode* pHead = hashTable[pos];
    while(pHead)
    {  
        if(strcmp(pHead->sKey, skey) == 0)  
        {  
            printf("%s发生冲突!\n", skey);
            return ;  
        }  
        pHead = pHead->pNext;  
    }  
    //动态建立结点，初始化，分配内存空间 
    HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));  
    memset(pNewNode, 0, sizeof(HashNode));  
    pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));  
    strcpy(pNewNode->sKey, skey);  
    pNewNode->nValue = nvalue;  

    //指针后移 
    pNewNode->pNext = hashTable[pos];  
    hashTable[pos] = pNewNode;  
    //表长增加 
    hash_table_size++;  
}  
 
删除函数
 
void hash_table_remove(const char* skey)  
{  
    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE; 

    if(hashTable[pos])  
    {  
        HashNode* pHead = hashTable[pos];  
        HashNode* pLast = NULL;  
        HashNode* pRemove = NULL;  
        while(pHead)  
        {  
            if(strcmp(skey, pHead->sKey) == 0)  
            {   //若str1==str2，则返回零;
                //若str1>str2，则返回正数;
                //若str1<str2，则返回负数。 
                pRemove = pHead;//若相等，用pRemove记录  
                break; 
            }  
            pLast = pHead;  //若不相等，不断后移 
            pHead = pHead->pNext;  
        }  
        if(pRemove)  
        {  
            if(pLast)
                pLast->pNext = pRemove->pNext;//实现删除1 
            else  
                hashTable[pos] = NULL;//实现删除2

            free(pRemove->sKey);  
            free(pRemove);  
        }  
    }  
}  
 
查找函数
 
HashNode* hash_table_lookup(const char* skey)  
{  
    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  

    if(hashTable[pos])  
    {  
        HashNode* pHead = hashTable[pos];  
        while(pHead)  
        {  
            if(strcmp(skey, pHead->sKey) == 0)  
                return pHead;//查找成功 

            pHead = pHead->pNext;  
        }  
    }  
    return NULL;  
}  
 
打印哈希表函数
 
void hash_table_print()  
{ 
    int i;  
    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
        if(hashTable[i])//表不空 
        {  
            HashNode* pHead = hashTable[i];  
            printf("%d=>", i);  
            while(pHead)  
            {  
                printf("%s:%d  ", pHead->sKey, pHead->nValue);  
                pHead = pHead->pNext;  
            }  
            printf("\n");  
        }  
}  
 
释放内存函数
 
void hash_table_release()  
{  
    int i;  
    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
    {  
        if(hashTable[i])  
        {  
            HashNode* pHead = hashTable[i];  
            while(pHead)  
            {  
                HashNode* pTemp = pHead;  
                pHead = pHead->pNext;  
                if(pTemp)  
                {  
                    free(pTemp->sKey);  
                    free(pTemp);  
                }  
                //逐个释放 
            }  
        }  
    }  
}  
 
随机生成函数
 
#define MAX_STR_LEN 20  
#define MIN_STR_LEN 10  
void rand_str(char r[])  
{  
    int i;  
    int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);  
    for(i = 0; i < len - 1; ++i)  
        r[i] = 'a' + rand() % ( 'z' - 'a');  
    r[len - 1] = '\0';  
}
 
具体代码如下：
 
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <time.h>  

#define HASH_TABLE_MAX_SIZE 10000  
typedef struct HashNode_Struct HashNode;  
struct HashNode_Struct  {  
    char* sKey;  
    int nValue;  
    HashNode* pNext;  
};  //哈希表数据结构 

HashNode* hashTable[HASH_TABLE_MAX_SIZE]; 
int hash_table_size;  //哈希表中键值对的数量 

//初始化哈希表 
void hash_table_init()  
{  
    hash_table_size = 0;  
    memset(hashTable, 0, sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
    //memset(void *s,int c,size_t n); 
    //将s中后n个字节换成c所代表的内容 
    //该函数是对较大结构体或数组进行清零操作的一种最快的方法 
}  


//去符号化哈希表  
unsigned int hash_table_hash_str(const char* skey)  
{  //无符号unsigned能保存2倍与有符号类型的正整型数据 
    const signed char *p = (const signed char*)skey; //常量 
    unsigned int h = *p;  
    if(h)
    {  
        for(p += 1; *p != '\0'; ++p)  
            h = (h << 5) - h + *p;  
    }  
    return h;  
}
//插入 
void hash_table_insert(const char* skey, int nvalue)  
{  
    if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度 
    {  
        printf("内存溢出!\n");
        return;  
    }  

    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
  //用于解决冲突，pos为哈希函数 
    HashNode* pHead = hashTable[pos];
    while(pHead)
    {  
        if(strcmp(pHead->sKey, skey) == 0)  
        {  
            printf("%s发生冲突!\n", skey);
            return ;  
        }  
        pHead = pHead->pNext;  
    }  
    //动态建立结点，初始化，分配内存空间 
    HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));  
    memset(pNewNode, 0, sizeof(HashNode));  
    pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));  
    strcpy(pNewNode->sKey, skey);  
    pNewNode->nValue = nvalue;  

    //指针后移 
    pNewNode->pNext = hashTable[pos];  
    hashTable[pos] = pNewNode;  
    //表长增加 
    hash_table_size++;  
}  
//删除 
void hash_table_remove(const char* skey)  
{  
    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE; 

    if(hashTable[pos])  
    {  
        HashNode* pHead = hashTable[pos];  
        HashNode* pLast = NULL;  
        HashNode* pRemove = NULL;  
        while(pHead)  
        {  
            if(strcmp(skey, pHead->sKey) == 0)  
            {   //若str1==str2，则返回零;
                //若str1>str2，则返回正数;
                //若str1<str2，则返回负数。 
                pRemove = pHead;//若相等，用pRemove记录  
                break; 
            }  
            pLast = pHead;  //若不相等，不断后移 
            pHead = pHead->pNext;  
        }  
        if(pRemove)  
        {  
            if(pLast)
                pLast->pNext = pRemove->pNext;//实现删除1 
            else  
                hashTable[pos] = NULL;//实现删除2

            free(pRemove->sKey);  
            free(pRemove);  
        }  
    }  
}  

//查找 
HashNode* hash_table_lookup(const char* skey)  
{  
    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  

    if(hashTable[pos])  
    {  
        HashNode* pHead = hashTable[pos];  
        while(pHead)  
        {  
            if(strcmp(skey, pHead->sKey) == 0)  
                return pHead;//查找成功 

            pHead = pHead->pNext;  
        }  
    }  
    return NULL;  
}  

//打印 
void hash_table_print()  
{ 
    int i;  
    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
        if(hashTable[i])//表不空 
        {  
            HashNode* pHead = hashTable[i];  
            printf("%d=>", i);  
            while(pHead)  
            {  
                printf("%s:%d  ", pHead->sKey, pHead->nValue);  
                pHead = pHead->pNext;  
            }  
            printf("\n");  
        }  
}  

//释放内存 
void hash_table_release()  
{  
    int i;  
    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
    {  
        if(hashTable[i])  
        {  
            HashNode* pHead = hashTable[i];  
            while(pHead)  
            {  
                HashNode* pTemp = pHead;  
                pHead = pHead->pNext;  
                if(pTemp)  
                {  
                    free(pTemp->sKey);  
                    free(pTemp);  
                }  
                //逐个释放 
            }  
        }  
    }  
}  


/* ============================主测试函数============================*/  
#define MAX_STR_LEN 20  
#define MIN_STR_LEN 10  
void rand_str(char r[])  
{  
    int i;  
    int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);  
    for(i = 0; i < len - 1; ++i)  
        r[i] = 'a' + rand() % ( 'z' - 'a');  
    r[len - 1] = '\0';  
}  

int main(int argc, char** argv)  
{  
    srand(time(NULL));  
    hash_table_init();     
    int n = 10;  
    char str[MAX_STR_LEN + 1]; 
    const char *key1 = "aaa111";  
    const char *key2 = "bbb222";  
    const char *key3 = "ccc333";

    while(n--)  
    {  
        rand_str(str);  
        hash_table_insert(str, n);  
    }
    printf("插入前\n");
    hash_table_print(); 

    hash_table_insert(key1, 1);  
    hash_table_insert(key2, 2);  
    hash_table_insert(key3, 2);   

    printf("插入后\n");
    hash_table_print();  

    HashNode* pNode = hash_table_lookup(key1);  
    printf("查找结果:%d\n", pNode->nValue);  
    pNode = hash_table_lookup(key2);  
    printf("查找结果:%d\n", pNode->nValue);

    printf("删除之前:\n");  
    hash_table_print();  
    hash_table_remove(key3);  
    printf("删除之后:\n");  
    hash_table_print();  

    hash_table_release();  

    return 0;  
}  

目录
 
1、数据结构
 
2、操作函数声明
 
3、具体实现
 

1、数据结构
 
#define HASH_TABLE_MALLOC(size)    rt_malloc(size);
#define HASH_TABLE_REALLOC(p,size) rt_realloc(p,size);
#define HASH_TABLE_CALLOC(n,size)  rt_calloc(n,size);
#define HASH_TABLE_FREE(p)         rt_free(p);

struct hash_table_node;
struct hash_table;

/* 哈希函数,根据key计算哈希值 */
typedef int (*hash_fun)(struct hash_table *table, const void *key);
/* 
 *哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key
 * hash桶中的元素是从小到大排列的，
 * 返回值 > 0 : key_cmp > key_becmp
 * 返回值 = 0 : key_cmp = key_becmp
 * 返回值 < 0 : key_cmp < key_becmp
*/
typedef int (*hash_keycmp)(struct hash_table *table, const void *key_cmp, const void *key_becmp);
/* hash桶中的节点数据删除函数,如果插入节点为动态分配,则需要在该函数中释放节点空间 */
typedef int (*node_value_free)(struct hash_table_node *node);

struct hash_table_node
{
    void *key;
    void *value;
    struct hash_table_node *next; /*哈希桶节点下个节点*/
};

struct hash_table
{
    int size; /*哈希桶的大小,即数组的大小*/
    int num;  /*各个哈希桶中节点个数的总和*/
    hash_fun hashfun; /*哈希函数*/
    hash_keycmp keycmp; /*哈希key比较*/
    node_value_free valuefree; /*哈希桶节点数据删除*/
    struct hash_table_node **tables; /*哈希桶,其实就是一个数组*/
};

/*根据当前结构体元素的地址，获取到结构体首地址*/
//#define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
//#define container(ptr,type,member) ({\
//  const typeof( ((type *)0)->member) *__mptr = (ptr);\
//  (type *) ((char *)__mptr - OFFSETOF(type,member));})

#define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
#define container(ptr,type,member) ((type *) ((char *)ptr - OFFSETOF(type,member)))
 
2、操作函数声明
 
 
 
extern struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree);
extern struct hash_table *hash_table_creat_default(int size, node_value_free valuefree);
extern int    hash_table_insert(struct hash_table *hashtable, void *key, void *value);
extern int    hash_table_delete(struct hash_table *hashtable, void *key);
extern int    hash_table_modify(struct hash_table *hashtable, void *key, void *value);
extern void * hash_table_search(struct hash_table *hashtable, void *key);

extern void hash_table_sample(void);
 
3、具体实现
 
#include "algo_hash_table.h"
/**
 * 默认使用的哈希函数.
 * 
 * @return 哈希值
 */
static int hash_fun_default(struct hash_table *table, const void *key)
{
    unsigned int hash = 0;
    unsigned int seed = 131;
    char *temp = NULL;
    
    temp = (char*)key;
    while(*temp)
    {
        hash = hash * seed + *temp++;
    }
    
    hash &= 0x7FFFFFFF;
    hash %= table->size;

    return hash;
}

/**
 * 哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key
 * 
 * @return > 0 : key_cmp > key_becmp
 * @return = 0 : key_cmp = key_becmp
 * @return < 0 : key_cmp < key_becmp
 * 
 */
static int hash_keycmp_default(struct hash_table *table, const void *key_cmp, const void *key_becmp)
{
    return strcmp(key_cmp, key_becmp);
}

/**
 * 动态创建一个哈希表.
 * 
 * @return NULL:创建失败
 *        !NULL:创建成功
 */
struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree)
{
    struct hash_table *hashtable = NULL;
    struct hash_table_node **tables = NULL;
    int i = 0;

    if (size < 0 || hashfun == NULL || keycmp == NULL)
        return NULL;

    /*申请哈希表结构空间*/
    hashtable = HASH_TABLE_MALLOC(sizeof(*hashtable));
    if (hashtable == NULL)
        return NULL;
    
    /*申请哈希桶数据空间,实际就是申请size大小的数组空间*/
    tables = (struct hash_table_node**)HASH_TABLE_MALLOC(size * sizeof(tables));
    if (tables == NULL)
        return NULL;

    hashtable->num       = 0;
    hashtable->size      = size;
    hashtable->tables    = tables;
    hashtable->hashfun   = hashfun;
    hashtable->keycmp    = keycmp;
    hashtable->valuefree = valuefree;

    /*清零哈希桶(数组)空间*/
    for (i = 0; i < size; i++)
    {
        hashtable->tables[i] = NULL;
    }
    
    return hashtable;
}

/**
 * 使用默认的函数函数、key比较函数、节点删除函数 动态创建一个哈希表.
 * 
 * @return NULL:创建失败
 *        !NULL:创建成功
 */
struct hash_table *hash_table_creat_default(int size, node_value_free valuefree)
{
    return hash_table_creat(size, hash_fun_default, hash_keycmp_default, valuefree);
}

/**
 * 向一个哈希桶插入一个节点,有3种情况:
 * 1、prev==NULL,插入位置是头结点 2、key小于cur->key 3、cur==NULL,链表尾插入
 * 
 * @param hashtable: 散列表
 * @param key: 关键值
 * @param value: 节点数据
 * @param value: 节点数据大小
 * 
 * @return 0:插入成功
 *        -1:哈希表不存在 或 key为空 或 value为空
 *        -2:节点已经存在
 */
int hash_table_insert(struct hash_table *hashtable, void *key, void *value)
{
    struct hash_table_node *prev = NULL;
    struct hash_table_node *cur = NULL;
    struct hash_table_node *new_node = NULL;
    int hvalue = 0;

    if (hashtable == NULL || key == NULL || value == NULL)
        return -1;

    /*根据key计算出哈希值*/
    hvalue = hashtable->hashfun(hashtable, key);
    cur = hashtable->tables[hvalue];

    /*hash桶中的元素是从小到大排列的,查找要插入的位置*/
    while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) > 0))
    {
        prev = cur;
        cur = cur->next;
    }

    /*如果key相同,表示节点以及存在,直接返回*/
    if ((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) == 0))
        return -2;

    /*插入新增节点*/
    new_node = (struct hash_table_node*)HASH_TABLE_MALLOC(sizeof(*new_node));
    if (new_node == NULL)
        return NULL;

    new_node->key = key;
    new_node->value = value;
    if (prev == NULL) /*第1种情况*/
    {
        new_node->next = NULL;
        hashtable->tables[hvalue] = new_node;/*这里不能为cur = new_node,因为此时的cur和table[hvalue]都是无效的*/
    }
    else /*第2、3种情况*/
    {
        new_node->next = cur;
        prev->next = new_node;
    }
    
    hashtable->num ++;

    return 0;
}


/**
 * 删除一个节点.
 * 
 * @param hashtable: 散列表
 * @param key: 删除节点关键值
 * 
 * @return 0:删除成功
 *        -1:哈希表不存在 或 key为空
 *        -2:节点不存在
 */
int hash_table_delete(struct hash_table *hashtable, void *key)
{
    struct hash_table_node *prev = NULL;
    struct hash_table_node *cur = NULL;
    int hvalue = 0;

    if (hashtable == NULL || key == NULL)
        return -1;

    /*根据key计算出哈希值*/
    hvalue = hashtable->hashfun(hashtable, key);
    cur = hashtable->tables[hvalue];

    /*hash桶中的元素是从小到大排列的,查找要删除的位置*/
    while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
    {
        if (hashtable->keycmp(hashtable, key, cur->key) == 0)
        {
            if (prev == NULL)/*如果删除的是头结点*/
            {
                hashtable->tables[hvalue] = cur->next;
            }
            else
            {
                prev->next = cur->next;
            }
            /*若节点所指向的数据(包括key和value)为动态分配,则需要在这里释放*/
            hashtable->valuefree(cur);
            HASH_TABLE_FREE(cur);

            hashtable->num --;
            return 0;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }

    return -2;
}

/**
 * 修改一个节点.注意事项:
 * 1、会先释放节点指向的就数据空间(这里如果是realloc更大的数据空间,容易造成指针泄露,且是不知道整个数据结构的大小的) 
 * 2、修改的节点必须为新动态分配的空间
 *
 * @param hashtable: 散列表
 * @param key: 修改节点关键值
 * @param value: 修改节点数据
 * 
 * @return 0:修改成功
 *        -1:哈希表不存在 或 key为空 或value为空
 *        -2:节点不存在
 */
int hash_table_modify(struct hash_table *hashtable, void *key, void *value)
{
    struct hash_table_node *cur = NULL;
    int hvalue = 0;

    if (hashtable == NULL || key == NULL || value == NULL)
        return -1;

    /*根据key计算出哈希值*/
    hvalue = hashtable->hashfun(hashtable, key);
    cur = hashtable->tables[hvalue];

    /*hash桶中的元素是从小到大排列的,查找要修改的位置*/
    while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
    {
        if (hashtable->keycmp(hashtable, key, cur->key) == 0)
        {
            hashtable->valuefree(cur);
            cur->key = key;
            cur->value = value;
            return 0;
        }
        else
        {
            cur = cur->next;
        }
    }

    return -2;
}

/**
 * 根据key查找节点数据.
 * 
 * @param hashtable: 散列表
 * @param key: 查找节点关键值
 * @param value: 查找节点数据
 * 
 * @return NULL:查找失败
 *        !NULL:查找成功
 */
void * hash_table_search(struct hash_table *hashtable, void *key)
{
    struct hash_table_node *cur = NULL;
    int hvalue = 0;

    if (hashtable == NULL || key == NULL)
        return NULL;

    /*根据key计算出哈希值*/
    hvalue = hashtable->hashfun(hashtable, key);
    cur = hashtable->tables[hvalue];

    /*hash桶中的元素是从小到大排列的,查找要查找的位置*/
    while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
    {
        if (hashtable->keycmp(hashtable, key, cur->key) == 0)
        {
            return cur->value;
        }
        else
        {
            cur = cur->next;
        }
    }

    return NULL;
}


/*******************************************************************************************
 *                                          使用示例
 *******************************************************************************************/
struct test_node
{
    char key[10];
    char value[10];
};

int node_value_free_sample(struct hash_table_node *node)
{
    struct test_node *node_temp = NULL;

    /*根据key在test_node结构体中的偏移地址,找到散列表节点实际指向的结构体首地址*/
    node_temp = container(node->key, struct test_node, key);
    /*如果节点所指向数据空间为动态申请的则需要释放*/
    HASH_TABLE_FREE(node_temp);
    
    return 0;
}

struct hash_table *hash_table_test;
char table_node_read[5][10];

void hash_table_sample(void)
{
    int i = 0;
    struct test_node *node_temp = NULL;
    char rd_key[10] = {10}, del_key[10] = {0};
    char *temp = NULL;
    
    hash_table_test = hash_table_creat_default(5, node_value_free_sample);
    
    /*插入 -- 查询*/
    for (i=0; i<5; i++)
    {
        node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp));
        memset(node_temp, 0, sizeof(*node_temp));
        sprintf(node_temp->key, "AAA%d", i);
        sprintf(node_temp->value, "%d", i+10);
        hash_table_insert(hash_table_test, node_temp->key, node_temp->value);
    }
    for (i=0; i<5; i++)
    {
        sprintf(rd_key, "AAA%d", i);
        temp = hash_table_search(hash_table_test, rd_key);
        memcpy(table_node_read[i], temp, 10);
    }
    
    /*修改 -- 查询*/
    for (i=0; i<5; i++)
    {
        node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp));
        memset(node_temp, 0, sizeof(*node_temp));
        sprintf(node_temp->key, "AAA%d", i);
        sprintf(node_temp->value, "%d", i+20);
        hash_table_modify(hash_table_test, node_temp->key, node_temp->value);
    }
    for (i=0; i<5; i++)
    {
        sprintf(rd_key, "AAA%d", i);
        temp = hash_table_search(hash_table_test, rd_key);
        memcpy(table_node_read[i], temp, 10);
    }
    
    /*删除 -- 查询*/
    for (i=0; i<3; i++)
    {
        sprintf(del_key, "AAA%d", i);
        hash_table_delete(hash_table_test, del_key);
    }
    for (i=0; i<5; i++)
    {
        temp = NULL;
        memset(table_node_read[i], 0, 10);
        sprintf(rd_key, "AAA%d", i);
        temp = hash_table_search(hash_table_test, rd_key);
        if (temp != NULL)
        {
            memcpy(table_node_read[i], temp, 10);
        }
    }
}