在实现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: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[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: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 */
如果遇到问题望指正。
分享到:
相关推荐
Hashtable存储数据例子,希望大家多多指教
c语言实现hashtable,一个key可以对应多个data,c语言实现
哈希表 哈希表_使用C语言实现哈希表数据结构_HashTable
用c语言实现的hash表,,c程序员数据结构必备。。
C/C++语言 hashtable代码 .c文件 适用于linux ubuntu unix等平台 terminal中操作
实现了链表法(Chaining)和开放地址寻址(Open Addressing)中的Hash表实现,开放地址寻址采用双重散列解决冲突
HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。 一,访问接口 创建一个hashtable. hashtable hashtable_new(int size) /其中size表示包含的接点个数。...
哈希表效率高,众所周知。应用广泛,php中大部分存储使用的都是hashtable,包括变量,数组…如何使用c语言实现hashtable呢,现提供自己的思路,如有不妥之处,敬请赐教
易语言 HashTable 数据效验算法,使用内联汇编,数次优化。速度快且稳定
简单HashTable c实现,基本功能都已经实现,可以自己扩充hash函数和key比较方法。简单实用。
一个简单的hash table实现类,实现了插入删除查询操作
比较分析Vector、ArrayList和hashtable hashmap数据结构
hashtable购物车Session+Hashtable实现。实现的方式多种多样,
数据结构(C语言版)实习,哈希表,取余,二次散列法解决冲突
HashTable源码
c语言Hashtable表的实现,和部分函数。仅供参考。
HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)实现,它通过散列算法将键值对映射到数组中。在HashMap中,每个键值对...
C#之Json字符串转换Hashtable,DataTable,DataSet方法和反转换方法.
基于C语言的数据结构-哈希表hashTable