[原创]空间换速度，c实现自连接Hashtable实现高性能数据存储

在实现web服务器系统的过程公有几个地方要用到特殊的hashtabke，以前发表的c实现的hashtable有个重要的缺点就是必须动态的为每一项 分配数据容器，这样就会导致在内存分配上浪费大量时间，今天在网上再次参阅了.net java的设计理念，发现java2。0中推出了新的Dictionary容器，但是java实现的方法是两个独立的容器，这还是会增加一次内存分配，对 于c，我们有更好的方法。
c是不会检查数组越界的，这既是缺点也是优点，当你确信分配的内存足够大时就可以在结构体中定一个1个长度的项数组，实际使用中照常按照常规数据就可以了。所以可以将两个数组合并到一个结构体中，我的hashtable定义是这样的：
typedef struct _HashNode HashNode;
typedef struct _hashTable HashTable;
struct _HashNode{ //散列表结点类型
char * key;
void * value; //此类依赖于应用
HashNode *next;//第一个表的连表指针
HashNode *pt;//单独的第二个hashindex项
};

struct _hashTable
{
unsigned int size;
unsigned int current;
HashNode items[1];
};
这样在分配hash结构题的过程中就可以malloc一次，比如：
HashTable *hs=(HashTable *)calloc(1,HashDefaultlength*(sizeof(HashNode))+sizeof(HashTable));从而实现动 态长度的分配，数组的组织是在hashNode线此性增加的，HashNode *next;//第一个表的连表指针 HashNode *pt;//单独的第二个hashindex项指针，这样就可以用一个结构体实现HashTable，pt记录第一个hashcode值，遇到冲突就将 pt指向实体 HashNode items[1]的index，多次冲突就记录在next指针中，也就是说pt充当冲突的head指针地址，后面是一个链表（以前就是每次需要项的时候增 加一个连表内存分配），连表以next指针维护，实际上pt完全可以看作一个新的数组列，他跟主HashNode数组长度完全一致。
当然，在java中Dictionary的Load Factor = 1，但我实现的是一个Hashtable，原理大致一致，但是还是采用0。75作为Load Factor，这样才会减少链表的长度，增加寻址速度。
以下是我的实现代码，经过简单的压力测试，500万次增加读取时间空间在1秒以内，性能还算满意：
/*
* File: hashtable.c 哈希表的实现
* Author: netpet
* Flower net server
* 关于本程序：为了避免堆栈内存的释放不可区分导致的错误，这里要求所有name和key都必须是堆内存
* 该hash表的hash函数是java的hash函数，所以增长因子也是hash的0.75
* 本程序是为一体化web server产品专用设计，具有部分代码为具体产品优化而不代表普遍通用性的特性
* 程序在linux 2.46下调试通过，编辑工具netbeans 6.1 for c
* 联系方式：Email:[e-mail] QQ:51977431
* Created on 2008年6月3日, 下午4:14
*/
#include "hashtable.h"
#include <stdio.h>
unsigned int GethashValue(char *key)
{
unsigned int hash;
unsigned char *p;
for(hash=0, p = (unsigned char *)key; *p ; p++)
hash = 31 * hash + *p;
hash=hash & 0x7FFFFFFF;
return hash;
}

/*
*功能：指定大小的新哈希表
*参数：length：用给定的长度建立一个hashtable表
*返回：hash表
*/
HashTable * HashTableNew(int length)
{
HashTable *hs=(HashTable *)calloc(1,length*(sizeof(HashNode))+sizeof(HashTable));
hs->size=length;
hs->current=0;
return hs;
}
/*
*功能：固定初始大小的哈希表
*参数：无
*返回：返回系统默认容积的hash表
*/
HashTable * NewHashTable(void)
{
HashTable *hs=(HashTable *)calloc(1,HashDefaultlength*(sizeof(HashNode))+sizeof(HashTable));
hs->size=HashDefaultlength;
hs->current=0;
return hs;
}
/*
*功能：取得给定key的值
*参数： T：hash表指针 key：名称字符串
*返回：如果不存在就返回空
*/
void * HashGet(HashTable *T,char * key)
{
unsigned int hash=GethashValue(key);
int index=hash%T->size;
HashNode *node=T->items[index].pt;
while(node) {
if(!strcmp(key, node->key))
return node->value;
node=node->next;
}
return NULL;
}
/*
*功能：设置一个项，不确定该项是否已经存在，如果存在就将它覆盖
*参数： T：hash表指针地址 key：名称 value：值
*返回：void
*/
void HashSet(HashTable **To,char * key,void *value)
{
HashTable * T=*To;
if((T->size*75)<(T->current*100))/**大于边界0.75就扩展*/ {
HashExpend(To);
T=*To;
}

unsigned int hash=GethashValue(key);
int index=hash%T->size;
HashNode *node=T->items[index].pt;
if(!node)
T->items[index].pt=&T->items[T->current];
else {

while(node){
if(!strcmp(key, node->key)) {
node->value=value;
return;
}
if(node->next)
node=node->next;
else
break;
}
node->next=&T->items[T->current];
node=node->next;
node->next=NULL;

}
T->items[T->current].key=key;
T->items[T->current].value=value;
T->current++;
}
/*
*功能：新增一个项，可能会导致重复，但速度较快
*参数： T：hash表指针地址 key：名称 value：值
*返回：void
*/
void HashAdd(HashTable **To,char * key,void *value)
{
HashTable * T=*To;
if((T->size*75)<(T->current*100))/**大于边界0.75就扩展*/ {
HashExpend(To);
T=*To;
}
unsigned int hash=GethashValue(key);
int index=hash%T->size;
HashNode *node;
T->items[T->current].key=key;
T->items[T->current].value=value;
if(T->items[index].pt)
{
node=T->items[index].pt;
while(node->next)
node=node->next;
node->next=&T->items[T->current];
node=node->next;
node->next=NULL;
}
else
T->items[index].pt=&T->items[T->current];
T->current++;
}
/*
*功能：移出指定项
*参数：T：hash表指针 key：要移出的名称
*返回：void
*/
void HashRemove(HashTable *T, char * key) {
unsigned int hash=GethashValue(key);
int index=hash%T->size;
HashNode *node=T->items[index].pt, *node1;
node1=node;
while(node) {
if(!strcmp(key, node->key)) {
node->key=NULL;
node->value=NULL;
if(node==T->items[index].pt)
T->items[index].pt=NULL;
else
node1->next=node->next;
return;
}
node1=node;
node=node->next;
}
}
/*
*功能：是否包含指定项
*参数：T：hash表指针 key：名称
*返回：void
*/
int HashContainKey(HashTable *T,char * key)
{
unsigned int hash=GethashValue(key);
int index=hash%T->size;
HashNode *node=T->items[index].pt;
while(node) {
if(!strcmp(key, node->key))
return 1;
node=node->next;
}
return 0;
}
/**拷贝两个hash表*/
void HashCopy(HashTable **Tn,HashTable *To)
{
unsigned int i;
HashTable *T=*Tn;
HashNode * node=T->items;
HashNode * nodeT=To->items;
for(i=0;i<To->size;i++)
{
if(nodeT[i].key)
{
HashAdd(Tn,nodeT[i].key,nodeT[i].value);
}
}
}
/*
*功能：扩展现有的表
*参数：T；hash表指针地址
*返回：hash表
*/
HashTable * HashExpend(HashTable ** To)
{
HashTable *T=*To;
unsigned int length =(T->current) * 2 + 1;
HashTable *hs=(HashTable *)calloc(1, length*(sizeof(HashNode))+sizeof(HashTable));
hs->size=length;
hs->current=0;
HashCopy(&hs, T);

free(*To);
*To=hs;
return hs;
}
/*
*功能：打印hash表
*参数：T：hash表指针
*返回：void
*/
void PrintHash(HashTable *T)
{
HashNode *node=T->items,*node1;
int i;
for(i=0;i<T->size;i++) {
//if(node[i].key)
printf("当前引起的循环：%d:________________________\n",i);
printf("%d本项：Key:%sPT:%p,Next:%p,%p\n",i, node[i].key,node[i].value,node[i].pt,node[i].next,node[i]);
node1=node[i].pt;
while(node1)
{
printf("%d含有项：Key:%s \tPT:%p,\tNext:%p,%p\n",i, node1->key,node1->value,node1->pt,node1->next,node1);
node1=node1->next;
}
}
}
/*
*功能：释放一个hash表
*参数：T：hash表指针
*返回：void
*/
void HashFree(HashTable *T)
{
free(T);

}



/*
* File: hashtable.h 哈希表的定义
* Author: netpet
* Flower net server
* 关于本程序：为了避免堆栈内存的释放不可区分导致的错误，这里要求所有name和key都必须是堆内存
* 该hash表的hash函数是java的hash函数，所以增长因子也是hash的0.75
* 本程序是为一体化web server产品专用设计，具有部分代码为具体产品优化而不代表普遍通用性的特性
* 程序在linux 2.46下调试通过，编辑工具netbeans 6.1 for c
* 联系方式：Email:[e-mail] QQ:51977431
* Created on 2008年6月3日, 下午4:14
*/

#ifndef _HASHTABLE_H
#define _HASHTABLE_H

#ifdef __cplusplus
extern "C" {
#endif

#define NIL -1 //空结点标记依赖于关键字类型，本节假定关键字均为非负整数
#define HashDefaultlength 11 //表长度依赖于应用，但一般应根据。确定m为一素数
#include <stdlib.h>
typedef struct _HashNode HashNode;
typedef struct _hashTable HashTable;
struct _HashNode{ //散列表结点类型
char * key;
void * value; //此类依赖于应用
HashNode *next;//第一个表的连表指针
HashNode *pt;//单独的第二个hashindex项
};

struct _hashTable
{
unsigned int size;
unsigned int current;
HashNode items[1];
};
/*
*功能：Hash函数
*参数：str：要转换的字符串
*返回：经过转换的无符号的int值结果
*/
extern unsigned int GethashValue(char *key);
/*
*功能：取得给定key的值
*参数： T：hash表指针 key：名称字符串
*返回：void
*/
extern void * HashGet(HashTable *T,char * key);//HashSearch
/*
*功能：设置一个项，不确定该项是否已经存在，如果存在就将它覆盖
*参数： T：hash表指针地址 key：名称 value：值
*返回：void
*/
extern void HashSet(HashTable **To,char * key,void *value);
/*
*功能：增加一个确信是新的项，速度比较快，不做检查，可能会导致重复
*参数： T：hash表指针地址 key：名称 value：值
*返回：void
*/
extern void HashAdd(HashTable **To,char * key,void *value);
/*
*功能：移出指定项
*参数：T：hash表指针 key：要移出的名称
*返回：void
*/
void HashRemove(HashTable *T,char * key);
/*
*功能：是否包含指定项
*参数：T：hash表指针 key：名称
*返回：void
*/
int HashContainKey(HashTable *T,char * key);
/*
*功能：指定大小的新哈希表
*参数：length：用给定的长度建立一个hashtable表
*返回：hash表
*/
HashTable * HashTableNew(int length);
/*
*功能：固定初始大小的哈希表
*参数：无
*返回：返回系统默认容积的hash表
*/
HashTable * NewHashTable(void);
/*
*功能：扩展现有的表
*参数：T；hash表指针地址
*返回：hash表
*/
HashTable * HashExpend(HashTable ** T);
/*
*功能：打印hash表
*参数：T：hash表指针
*返回：void
*/
void PrintHash(HashTable *T);
/*
*功能：释放一个hash表
*参数：T：hash表指针
*返回：void
*/
void HashFree(HashTable *T);


#ifdef __cplusplus
}
#endif

#endif /* _HASHTABLE_H */

如果遇到问题望指正。