散列表（二）：冲突处理的方法之链地址法的实现

首先需要澄清的一点是，这里讲的是hash table ，即数据项所存储的表要用数组来实现。

一、链地址法

这种基本思想：将所有哈希地址为i 的元素构成一个称为同义词链的链表，并将链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在

同义词链中进行。

该散列方法首先对关键码集合用某一个散列函数计算它们的存放位置。

若设散列表地址空间的所有位置是从0到m-1，则关键码集合中的所有关键码被划分为m个子集，具有相同地址的关键码归于同一子集。我们称同一子集

中的关键码互为同义词。每一个子集称为一个桶。

通常各个桶中的表项通过一个链表链接起来，称之为同义词子表。所有桶号相同的表项都链接在同一个同义词子表中，各链表的表头结点

组成一个向量。

假设给出一组表项，它们的关键码为 Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。采用的散列函数是：取其第一个字母在

字母表中的位置。

hash (x) = ord (x) - ord (‘A’)

这样，可得

hash (Burke) = 1 hash (Ekers) = 4

hash (Broad) = 1 hash (Blum) = 1

hash (Attlee) = 0 hash (Hecht) = 7

hash (Alton) = 0 hash (Ederly) = 4

1、通常，每个桶中的同义词子表都很短，设有n个关键码通过某一个散列函数，存放到散列表中的 m 个桶中。那么每一个桶中的同

义词子表的平均长度为 n / m。这样，以搜索平均长度为 n / m 的同义词子表代替了搜索长度为 n 的顺序表，搜索速度快得多（O(1)）。

2、应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上，由于开地址法必须保持大量的空闲空间以确保搜索

效率，如二次探查法要求装填因子，（a = n / m）而表项所占空间又比指针大得多，所以使用链地址法反而比开地址法节省存

储空间。

下面给出链地址法的实现，包括构造哈希表，释放哈希表，在哈希表中根据key查找一项，根据key 插入一项，根据key 删除一项等。链表节点用双向

链表实现。

common.h：

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br></nobr>

#ifndef_COMMON_H_ #define_COMMON_H_ #include<unistd.h> #include<sys/types.h> #include<stdlib.h> #include<stdio.h> #include<string.h> #defineERR_EXIT(m)\ do\ {\ perror(m);\ exit(EXIT_FAILURE);\ }\ while(0) #endif

hash_link.h：

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br> 20<br></nobr>

#ifndef_HASH_LINK_H_ #define_HASH_LINK_H_ #include"common.h" /*给定关键码key，经过哈希函数计算得到的是关键码对应的数据项在数组中的存储下标index/bucket *数据项所存储的表用数组实现，即hashtable */ typedefstructhashhash_t; typedefunsignedint(*hashfunc_t)(unsignedint,void*);//第一个参数是桶的个数(地址范围），第二个参数是key值指针 hash_t*hash_alloc(unsignedintbuckets,hashfunc_thash_func);//建立哈希表 voidhash_free(hash_t*hash);//释放哈希表 void*hash_lookup_entry(hash_t*hash,void*key,unsignedintkey_size);//在哈希表中查找一项key //在哈希表中添加一条记录 voidhash_add_entry(hash_t*hash,void*key,unsignedintkey_size,void*value,unsignedintvalue_size); voidhash_free_entry(hash_t*hash,void*key,unsignedintkey_size);//在哈希表中删除一条记录 #endif

hash_link.c：

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br> 20<br> 21<br> 22<br> 23<br> 24<br> 25<br> 26<br> 27<br> 28<br> 29<br> 30<br> 31<br> 32<br> 33<br> 34<br> 35<br> 36<br> 37<br> 38<br> 39<br> 40<br> 41<br> 42<br> 43<br> 44<br> 45<br> 46<br> 47<br> 48<br> 49<br> 50<br> 51<br> 52<br> 53<br> 54<br> 55<br> 56<br> 57<br> 58<br> 59<br> 60<br> 61<br> 62<br> 63<br> 64<br> 65<br> 66<br> 67<br> 68<br> 69<br> 70<br> 71<br> 72<br> 73<br> 74<br> 75<br> 76<br> 77<br> 78<br> 79<br> 80<br> 81<br> 82<br> 83<br> 84<br> 85<br> 86<br> 87<br> 88<br> 89<br> 90<br> 91<br> 92<br> 93<br> 94<br> 95<br> 96<br> 97<br> 98<br> 99<br> 100<br> 101<br> 102<br> 103<br> 104<br> 105<br> 106<br> 107<br> 108<br> 109<br> 110<br> 111<br> 112<br> 113<br> 114<br> 115<br> 116<br> 117<br> 118<br> 119<br> 120<br> 121<br> 122<br> 123<br> 124<br> 125<br> 126<br> 127<br> 128<br> 129<br> 130<br> 131<br> 132<br> 133<br> 134<br> 135<br> 136<br> 137<br> 138<br> 139<br> 140<br> 141<br> 142<br> 143<br> 144<br> 145<br> 146<br> 147<br> 148<br> 149<br> 150<br> 151<br> 152<br> 153<br> 154<br> 155<br> 156<br> 157<br> 158<br></nobr>

#include"hash_link.h" typedefstructhash_node { void*key;//无类型指针，故key可以是任意类型，value同 void*value;//有价值数据 structhash_node*prev;//前驱指针 structhash_node*next;//后继指针 }hash_node_t; structhash { unsignedintbuckets;//桶的个数 hashfunc_thash_func;//哈希函数 hash_node_t**nodes;//指向哈希表数组的指针，数组放的是hash_node_t* }; hash_node_t**hash_get_bucket(hash_t*hash,void*key); hash_node_t*hash_get_node_by_key(hash_t*hash,void*key,unsignedintkey_size); hash_t*hash_alloc(unsignedintbuckets,hashfunc_thash_func) { hash_t*hash=malloc(sizeof(hash_t)); hash->buckets=buckets; hash->hash_func=hash_func; intsize=buckets*sizeof(hash_node_t*);//哈希表数组的大小 hash->nodes=(hash_node_t**)malloc(size); memset(hash->nodes,0,size);//数组清0 printf("Thehashtablehasallocate.\n"); returnhash; } voidhash_free(hash_t*hash) { unsignedintbuckets=hash->buckets; inti; for(i=0;i<buckets;i++) { while(hash->nodes[i]!=NULL) { hash_node_t*tmp=hash->nodes[i]; hash->nodes[i]=tmp->next; if(tmp->next!=NULL) //也许只有一个节点 tmp->next->prev=tmp->prev; free(tmp->value); free(tmp->key); free(tmp); } } free(hash); printf("Thehashtablehasfree.\n"); } void*hash_lookup_entry(hash_t*hash,void*key,unsignedintkey_size) { hash_node_t*node=hash_get_node_by_key(hash,key,key_size); if(node==NULL) returnNULL; returnnode->value; } voidhash_add_entry(hash_t*hash,void*key,unsignedintkey_size,void*value,unsignedintvalue_size) { if(hash_lookup_entry(hash,key,key_size)) { //key值已经存在，直接返回 fprintf(stderr,"duplicatehashkey\n"); return; } hash_node_t*node=malloc(sizeof(hash_node_t)); node->prev=NULL; node->next=NULL; node->key=malloc(key_size); memcpy(node->key,key,key_size); node->value=malloc(value_size); memcpy(node->value,value,value_size); //插入第一个结点 hash_node_t**bucket=hash_get_bucket(hash,key); if(*bucket==NULL) *bucket=node; else//将新结点插入链表头部 { node->next=*bucket; (*bucket)->prev=node; *bucket=node; } } voidhash_free_entry(hash_t*hash,void*key,unsignedintkey_size) { hash_node_t*node=hash_get_node_by_key(hash,key,key_size); if(node==NULL) return; free(node->key); free(node->value); //双向链表的删除操作 if(node->prev!=NULL) node->prev->next=node->next; else { hash_node_t**bucket=hash_get_bucket(hash,key); *bucket=node->next; } if(node->next!=NULL) node->next->prev=node->prev; free(node); } hash_node_t**hash_get_bucket(hash_t*hash,void*key) { //通过哈希函数返回地址 unsignedintbucket=hash->hash_func(hash->buckets,key); if(bucket>=hash->buckets) { fprintf(stderr,"badbucketlookup\n"); exit(EXIT_FAILURE); } return&(hash->nodes[bucket]);//返回指向某个桶的指针 } hash_node_t*hash_get_node_by_key(hash_t*hash,void*key,unsignedintkey_size) { hash_node_t**bucket=hash_get_bucket(hash,key); hash_node_t*node=*bucket; if(node==NULL) { returnNULL; } while(node!=NULL&&memcmp(node->key,key,key_size)!=0) { //通过链表头指针不断查询是否匹配 node=node->next; } returnnode; }

hash_link_main.c：

C++ Code

<nobr>1<br> 2<br> 3<br> 4<br> 5<br> 6<br> 7<br> 8<br> 9<br> 10<br> 11<br> 12<br> 13<br> 14<br> 15<br> 16<br> 17<br> 18<br> 19<br> 20<br> 21<br> 22<br> 23<br> 24<br> 25<br> 26<br> 27<br> 28<br> 29<br> 30<br> 31<br> 32<br> 33<br> 34<br> 35<br> 36<br> 37<br> 38<br> 39<br> 40<br> 41<br> 42<br> 43<br> 44<br> 45<br> 46<br> 47<br> 48<br> 49<br> 50<br> 51<br> 52<br> 53<br> 54<br> 55<br> 56<br> 57<br> 58<br> 59<br> 60<br> 61<br> 62<br> 63<br> 64<br> 65<br> 66<br> 67<br> 68<br> 69<br> 70<br> 71<br></nobr>

/************************************************************************* >FileName:hash_table_main.c >Author:Simba >Mail:[e-mail] >CreatedTime:Fri22Mar201311:17:25AMCST ************************************************************************/ #include"hash_link.h" typedefstructstu { charnum[5]; charname[32]; intage; }stu_t; //使用学号来当作key进而产生hashindex/bucket //在这里学号是字符串，当然也可以将学号定义为int类型,此时要重新定义一个hash_int函数 unsignedinthash_str(unsignedintbuckets,void*key) { char*num=(char*)key; unsignedintindex=0; while(*num) { index=*num+4*index; num++; } returnindex%buckets; } //在这个例子中，key是学生学号，value是学生结构体 intmain(void) { stu_tstu_arr[]= { {"1234","AAAA",20}, {"6543","BBBB",23}, {"7657","AAAA",19}, }; hash_t*hash=hash_alloc(256,hash_str); intsize=sizeof(stu_arr)/sizeof(stu_arr[0]); inti; for(i=0;i<size;i++) { hash_add_entry(hash,stu_arr[i].num,strlen(stu_arr[i].num), &stu_arr[i],sizeof(stu_arr[i])); } stu_t*ptr=(stu_t*)hash_lookup_entry(hash,"6543",strlen("6543")); if(ptr) printf("%s%s%d\n",ptr->num,ptr->name,ptr->age); else printf("notfound\n"); hash_free_entry(hash,"1234",strlen("1234")); ptr=(stu_t*)hash_lookup_entry(hash,"1234",strlen("1234")); if(ptr) printf("%s%s%d\n",ptr->num,ptr->name,ptr->age); else printf("notfound\n"); hash_free(hash); return0; }

simba@ubuntu:~/Documents/code/struct_algorithm/search/hash_table/link_address$ ./hash_link_main

The hash table has allocate.
6543 BBBB 23

not found

The hash table has free.

上述程序中key 是学号，使用key 产生哈希地址，即桶号，每个结点所带有的有价值数据value 是一个学生结构体。

哈希数组中每一项存放的是链表的头指针（如果存在，否则为NULL）。每个节点的key 和 value 成员都是指针，在

free整个节点之前，需要先free 两个指针。节点的另外两个成员是前驱和后继指针。如下图所示：