编程手记之ANSI C篇-（二）哈希序列
哈希表的基本思路是：由关键码的哈希函数值来决定节点的存储地址，进而来存取节点。在我的应用中，要解决的是基于命名（字符串型关键码）来查找和存储节点，节点的内容是字符串或某个结构的指针。哈希表的结构有主散列和子序列构成，主散列是一线性数组，数组的大小为size，是一个素数，也是哈希函数的模基，数组序号[0...size]即哈希函数的值域，数组存储的是根连接件，由他维护着同义词关键码（哈希函数值相同）的节点链表。子序列是存储节点的有序序列，是按各节点关键码升序排列的，子序列主要是用于处理哈希冲撞的问题。查找的路径为，根据关键码的哈希函数值在主散列中取得根连接件，然后在此子序列中查找含该关键码的节点。
1、数据结构定义：
/*定义哈希表*/
typedef struct _HashTable{
LINK lk;/*哈希表自身连接件*/
LINKPTR pp;/*主散列线性数组指针*/
int size;/*数组大小*/
}HashTable;
/*定义节点*/
typedef struct _HashEntry{
LINK lk;/*节点自身连接件*/
TCHAR* szKey;/*关键码*/
TCHAR* szVal;/*节点字符串值*/
unsigned long data;/*节点长整型值*/
}HashEntry;
/*定义数据节点标识*/
#define lkHashEntry 1
#define lkHashTable 2
/*定义从连接件指针中恢复数据节点*/
#define HashTableFromLink(p) ((HashTable*)((unsigned int)p - (unsigned int)&(((HashTable*)0)->lk)))
#define HashEntryFromLink(p) ((HashEntry*)((unsigned int)p - (unsigned int)&(((HashEntry*)0)->lk)))
/*定义枚举哈希表节的回调函数*/
typedef int (*EnumHashEntryPtr)(TCHAR* szKey,int keylen,TCHAR* szVal,int vallen,void* pv);
2、哈希函数：
/*szKey: 关键码
keylen: 关键码长度
nPrim: 模基，一般为素数*/
static int HashCode(TCHAR* szKey,int keylen,int nPrim)
{
unsigned int sum;
int i;
assert(szKey);
assert(nPrim > 0);
/*keylen为-1指明szKey为'\0'结尾的字符串*/
if(keylen == -1)
keylen = _tcslen(szKey);
/*各字节取整求和*/
sum = 0;
for(i=0;i
{
sum += (int)(szKey[i]);
}
/*求余数*/
return sum % nPrim;
}
3、哈希表实现：
/*创建哈希表
nSize: 哈希函数的模基，即主散列数组的大小，一般取素数值*/
LINKPTR CreateHashTable(int nSize)
{
HashTable* pht;
int i;
assert(nSize > 0);
pht = (HashTable*)calloc(1,sizeof(HashTable));
pht->lk.tag = lkHashTable;
pht->size = nSize;
/*分配主散列数组空间*/
pht->pp = (LINKPTR)calloc(nSize,sizeof(LINK));
/*初始化每个根连接件*/
for(i = 0;i<size;i++)
InitRootLink(pht->pp + i);
return &(pht->lk);
}
/*销毁哈希表
ptr: 哈希表连接件指针*/
void DestroyHashTable(LINKPTR ptr)
{
HashTable* pht;
assert(ptr);
assert(ptr->tag == lkHashTable);
pht = HashTableFromLink(ptr);
/*清除所有子序列*/
ClearHashTable(ptr);
free(pht->pp);
free(pht);
}
/*清除所有子序列
ptr: 哈希表连接件指针*/
void ClearHashTable(LINKPTR ptr)
{
HashTable* pht;
HashEntry* phe;
LINKPTR plk,pre;
int i;
assert(ptr);
assert(ptr->tag == lkHashTable);
pht = HashTableFromLink(ptr);
/*清除每一个根连接件下的子序列*/
for(i=0;isize;i++)
{
plk = GetFirstLink(&(pht->pp[i]));
while(plk)
{
pre = plk;
plk = GetNextLink(plk);
phe = HashEntryFromLink(pre);
assert(phe->szKey);/*断言关键码不为空*/
free(phe->szKey);
if(phe->szVal)
free(phe->szVal);
free(phe);/*释放子节点*/
}
}
/*每个根连接件置为初始化态*/
for(i = 0;i<size;i++)
InitRootLink(pht->pp + i);
}
/*添加节点到哈希表中
ptr: 哈希表连接件指针
szKey: 关键码
keylen: 关键码长度
szVal: 值字符串
vallen: 值字符串长度*/
LINKPTR AddHashEntry(LINKPTR ptr,TCHAR* szKey,int keylen,TCHAR* szVal,int vallen)
{
HashTable* pht;
HashEntry* phe;
LINKPTR plk;
int nIndex;
assert(ptr);
assert(ptr->tag == lkHashTable);
pht = HashTableFromLink(ptr);
/*先查找是否存在同名关键码*/
plk = GetHashEntry(ptr,szKey,keylen);
if(plk != NULL)/*存在则进行值替换*/
{
phe = HashEntryFromLink(plk);
free(phe->szKey);
if(keylen == -1)
keylen = _tcslen(szKey);
phe->szKey = (TCHAR*)calloc(keylen + 1,sizeof(TCHAR));
_tcsncpy(phe->szKey,szKey,keylen);
if(phe->szVal != NULL)
{
free(phe->szVal);
phe->szVal = NULL;
}
if(szVal != NULL)
{
if(vallen == -1)
vallen = _tcslen(szVal);
phe->szVal = (TCHAR*)calloc(vallen + 1,sizeof(TCHAR));
_tcsncpy(phe->szVal,szVal,vallen);
}
}else/*否则添加新节点*/
{
phe = (HashEntry*)calloc(1,sizeof(HashEntry));
phe->lk.tag = lkHashEntry;
assert(szKey);
if(keylen == -1)
keylen = _tcslen(szKey);
phe->szKey = (TCHAR*)calloc(keylen + 1,sizeof(TCHAR));
_tcsncpy(phe->szKey,szKey,keylen);
if(szVal)
{
if(vallen == -1)
vallen = _tcslen(szVal);
phe->szVal = (TCHAR*)calloc(vallen + 1,sizeof(TCHAR));
_tcsncpy(phe->szVal,szVal,vallen);
}
/*由哈希函数值取得根连接件的位置*/
nIndex = HashCode(phe->szKey,keylen,pht->size);
plk = &((pht->pp)[nIndex]);
/*插入到该根连接件的链表中*/
OrderInsertEntry(plk,&phe->lk);
}
/*返回节点连接件指针*/
return &(phe->lk);
}
/*由关键码取得节点连接件指针
ptr: 哈希表连接件指针
szKey: 关键码
keylen: 关键码长度*/
LINKPTR GetHashEntry(LINKPTR ptr,TCHAR* szKey,int keylen)
{
int nIndex,rt;
HashEntry* phe;
HashTable* pht;
LINKPTR plk;
assert(ptr);
assert(ptr->tag == lkHashTable);
if(szKey == NULL)
return NULL;
pht = HashTableFromLink(ptr);
if(keylen == -1)
keylen = _tcslen(szKey);
/*由哈希函数值取得根连接件*/
nIndex = HashCode(szKey,keylen,pht->size);
plk = GetFirstLink(&((pht->pp)[nIndex]));
while(plk != NULL)
{
phe = HashEntryFromLink(plk);
rt = _tcsncmp(phe->szKey,szKey,keylen);
if(rt > 0)
return NULL;/*升序的后续节点中已无匹配的节点*/
else if(rt == 0 && (int)_tcslen(phe->szKey) == keylen)
break;/*两字符串的长度也应相等才匹配*/
plk = GetNextLink(plk);
}
return plk;
}
/*删除节点
elk: 节点连接件指针*/
void DeleteHashEntry(LINKPTR elk)
{
HashEntry* phe;
assert(elk);
assert(elk->tag == lkHashEntry);
phe = HashEntryFromLink(elk);
/*从根连接件链表中删除*/
assert(DeleteLinkAt(GetRootLink(elk),elk) == elk);
/*释放节点*/
free(phe->szKey);
if(phe->szVal)
free(phe->szVal);
free(phe);
}
/*取得节点的关键码字符串指针
elk: 节点连接件指针*/
TCHAR* GetHashEntryKeyPtr(LINKPTR elk)
{
HashEntry* phe;
assert(elk);
assert(elk->tag == lkHashEntry);
phe = HashEntryFromLink(elk);
return phe->szKey;
}
/*取得节点值的字符串指针
elk: 节点连接件指针*/
TCHAR* GetHashEntryValPtr(LINKPTR elk)
{
HashEntry* phe;
assert(elk);
assert(elk->tag == lkHashEntry);
phe = HashEntryFromLink(elk);
return phe->szVal;
}
/*设置节点的长整数值
elk: 节点连接件指针*/
void SetHashEntryData(LINKPTR elk,unsigned long data)
{
HashEntry* phe;
assert(elk);
assert(elk->tag == lkHashEntry);
phe = HashEntryFromLink(elk);
phe->data = data;
}
/*取得节点的长整数值
elk: 节点连接件指针*/
unsigned long GetHashEntryData(LINKPTR elk)
{
HashEntry* phe;
assert(elk);
assert(elk->tag == lkHashEntry);
phe = HashEntryFromLink(elk);
return phe->data;
}
/*枚举哈希表中的节点
ptr: 哈希表的连接件指针
pf: 调用者的回调函数
pv: 调用者的回传参数*/
int EnumHashEntry(LINKPTR ptr,EnumHashEntryPtr pf,void* pv)
{
HashTable* pht;
HashEntry* phe;
LINKPTR plk;
int i;
assert(ptr);
assert(ptr->tag == lkHashTable);
assert(pf);
pht = HashTableFromLink(ptr);
for(i=0;isize;i++)
{
plk = GetFirstLink(&((pht->pp)[i]));
while(plk != NULL)
{
phe = HashEntryFromLink(plk);
if((*pf)(phe->szKey,((phe->szKey)? _tcslen(phe->szKey) : 0),phe->szVal,((phe->szVal)? _tcslen(phe->szVal) : 0),pv))
return 1;/*如果调用者回调函数返回非零值则终止枚举*/
plk = GetNextLink(plk);
}
}
return 0;
}
/*将节点插入升序的链表
root: 根连接件指针
ptrEntry: 节点连接件指针*/
void OrderInsertEntry(LINKPTR root,LINKPTR ptrEntry)
{
HashEntry* pnew;
HashEntry* phe;
LINKPTR plk;
assert(root && root->tag == lkRoot);
assert(ptrEntry && ptrEntry->tag == lkHashEntry);
pnew = HashEntryFromLink(ptrEntry);
plk = GetFirstLink(root);
while(plk)
{
phe = HashEntryFromLink(plk);
if(_tcscmp(phe->szKey,pnew->szKey) > 0)
break;/*新节点应为当前plk的前驱*/
plk = GetNextLink(plk);
}
if(plk == NULL)
InsertLinkAt(root,LINK_LAST,ptrEntry);
else
InsertLinkBefore(plk,ptrEntry);
}
3、哈希表的基本算法分析：假设有N个节点插入到哈希表，哈希函数的模基为M，则负载因子D=N/M，由于该查找包括两步，查找主散列位置（检索长度为1）和子序列顺序查找（平均检索长度为D/2），可见该哈希表的平均检索长度为1+D/2。但我不满意的地方是在子序列中顺序表查找的中字符串比较是比较费时的，如果您有好的ideas请告诉吧！jdhot2003@hotmail.com
