hash表可以由2部分组成，第一部分为索引表；第二部分，以索引表为属性的，具有某种相同属性单链表。 以下述实例为例，索引：localDiscr为10001开始的递增会话表，最大为64条。用100个桶去装，最坏可能性为同时落到1个桶里，所以桶的深度为64。 性能：查找时，与单链表从头结点开始遍历，最坏情况遍历所有结点不同，hash表，通过先搜索索引表，再遍历单链表，最坏情况是遍历某个桶所有成员，所以当取的散列特点足够好，则可以减少遍历时间。 hash表参数定义
#define BFD_SIZE 64 //桶深度#define BFD_HASHSIZE 100 //桶个数#define BFD_HASHKEY(val) ((val) % BFD_HASHSIZE) //索引算法64个索引散列在100个桶里，这64个索引用单链表存储typedef struct _bfd{ int localDiscr; //索引 struct _bfd *discNext; //hash next表指针}BFD;typedef struct _bfd_cb{ int cnt; BFD *hash[BFD_HASHSIZE];//hash桶，共有BFD_HASHSIZE个}BFD_CB;hash表插入：
BFD_CB bfd_cb ;BFD *MatchByLd(int myDisc){ int hkey = BFD_HASHSIZE; BFD *bfd = NULL; hkey = BFD_HASHKEY(myDisc); for (bfd = bfd_cb.hash[hkey]; NULL != bfd ; bfd = bfd->discNext){ if (bfd->localDiscr == myDisc){ return bfd; } } return NULL;}BOOL DiscHashAdd(BFD *bfd){ int hkey = 0; if(NULL == bfd){ PRintf("DiscHashAdd : NULL == bfd./n"); return FALSE; } /* “头插法”插入到your disc hash表中 */ hkey = BFD_HASHKEY(bfd->localDiscr); bfd->discNext = bfd_cb.hash[hkey]; bfd_cb.hash[hkey] = bfd; return TRUE;}BOOL DiscHashDel(BFD *bfd){ int hkey = 0; BFD *prev = NULL; BFD *tmp = NULL; if(NULL == bfd){ printf("DiscHashDel :NULL == bfd./n"); return FALSE; } /* 从disc hash表中删除 */ hkey = BFD_HASHKEY(bfd->localDiscr); for (tmp = bfd_cb.hash[hkey]; tmp; tmp = tmp->discNext){ if (tmp->localDiscr == bfd->localDiscr){ if (prev){ prev->discNext = bfd->discNext; } else{ bfd_cb.hash[hkey] = bfd->discNext; } break; } prev = tmp; } return TRUE;}BFD *AllocDiscHash(int discrIn){ BFD *bfd = NULL; if (bfd_cb.cnt > BFD_SIZE){ printf("bfd_cb.cnt > BFD_SIZE/n"); return NULL; } /*需要判断是否存在于hash table中*/ if (0 != bfd_cb.cnt && NULL != MatchByLd(discrIn)){ printf("discr already Exists!!/n"); return NULL; } bfd = new BFD; bfd->localDiscr = discrIn; bfd_cb.cnt++; return bfd;}void FreeDiscHash(BFD *bfd){ if (NULL == bfd){ printf("FreeDiscHash ：NULL == bfd!!/n"); return; } delete bfd; if (bfd_cb.cnt < 1){ printf("bfd_cb.cnt < 1/n"); return ; } bfd_cb.cnt--; return;}void HashCreat(void){ BFD *bfd = NULL; bfd_cb.cnt = 0; bfd = AllocDiscHash(10001);// 插入单链表 if (NULL != bfd){ DiscHashAdd(bfd); //插入hash表 }}void HashDel(void){ BFD *bfd = NULL; bfd = MatchByLd(10002); DiscHashDel(bfd); FreeDiscHash(bfd);}也可以使用库文件操作单链表进行改造，参考《linux内核list代码queue.h实现“头插法”》一文。
新闻热点
疑难解答
