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

javasogo

在实现web服务器系统的过程公有几个地方要用到特殊的hashtabke，以前发表的c实现的hashtable有个重要的缺点就是必须动态的为每一项分配数据容器，这样就会导致在内存分配上浪费大量时间，今天在网上再次参阅了.netjava的设计理念，发现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指向实体 HashNodeitems[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:netpetboy@163.com 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.key)
    {
      HashAdd(Tn,nodeT.key,nodeT.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.key)
  printf("当前引起的循环：%d:________________________\n",i);
  printf("%d本项：Key:%sPT:%p,Next:%p,%p\n",i, node.key,node.value,node.pt,node.next,node);
  node1=node.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:netpetboy@163.com 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 */

  如果遇到问题望指正。