非同步的hash结构的简单实现。
根据不同的key用hash函数计算出在数组中的位置，数组中保存的是一个链表结构的结构，不同key在hash值相同的情况下，可以用链表来控制在内存中的位置。
hashtable.h文件.
/*****************************************
* FILE : hashtable.h
* DATE : 2008/01/06
* AUTHOR : ZhangLiHai
* ***************************************/
#ifndef HASHTABLE_H_
#define HASHTABLE_H_
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct __hash_entry hash_entry;
typedef struct __hash_entry* p_hash_entry;
typedef struct __hash_table hashtable;
typedef struct __hash_table* p_hashtable;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
struct __hash_entry{
p_hash_entry next;//next entry
unsigned int hash_code;//key hash_code...
const char* key; //key..
const void* value;//value object
int klen; //entry size.
};
struct __hash_table{
int capacity;// array length.
int size;//cur size
unsigned int (*hash_code_fp)(const char*);//hash_code function pointer.
void (*value_free_fp)(void*);
void (*key_free_fp)(char*);
p_hash_entry *array; //entry array;
};
//foreach function pointer.
typedef BOOL (*hash_foreach_fp)(p_hash_entry);
/***********************
*
* 创建一个hashtable指针
*
* *********************/
p_hashtable new_hashtab();
p_hash_entry new_entry();
/***************************************
*
* 将key,value放入hash结构里面
*
* *************************************/
BOOL hash_put(p_hashtable,const char*, const void*);
/******************************************
*
*
* 根据key返回一个void *
*
*
* ******************************************/
void* hash_get(p_hashtable,const char*);
/*****************************************
*
* 重新分配hash空间
*
* 重新规划元素的位置
* ***************************************/
BOOL hash_resize(p_hashtable );
/****************************************
*
*
* hash code算法的默认实现~
*
*
* **************************************/
unsigned int hash_code_fp_default(const char*);
/**************
*
*
* 删除某个key下的值
*
*
*
* **********************/
BOOL hash_remove_key(p_hashtable, const char*);
/********************
*
* 清除hash里面的所有数据，但是保存hashtable本身
*
* **********************/
BOOL hash_data_clear(p_hashtable );
/*****************
*
* 看某个key是否在hash里面
*
* ************************/
BOOL hash_contains_key(p_hashtable, const char*);
/**************************
* 迭代函数
* 一个是清楚数据，另一个没有清除
* ******************/
void hash_foreach_no_clear(p_hashtable,hash_foreach_fp);
void hash_foreach_clear(p_hashtable,hash_foreach_fp);
/********************************
*
* 两个默认的free方法，调用stdlib的free函数
*
* *******************************/
void std_key_free(char *);
void std_value_free(void *);
/************************
*
* 回收一个hashtable指针
*
* 如果里面的value需要回收，则传入一个函数指针
*
* ************************/
BOOL free_hashtab(p_hashtable );
#endif /*HASHTABLE_H_*/
hashtable.c文件包含测试
/*****************************************
* FILE : hashtable.c
* DATE : 2008/01/06
* AUTHOR : ZhangLiHai
* ***************************************/
#include "hashtable.h"
#define MAX_SIZE 1024
#define HASH_IND(h,n) ((h)%(n))
p_hashtable new_hashtab(){
p_hashtable tab;
tab = (p_hashtable)malloc(sizeof(struct __hash_table));
printf("new hashtable \n");
tab->size=0;
tab->capacity=MAX_SIZE;
tab->array=(p_hash_entry*)calloc(tab->capacity,sizeof(p_hash_entry));
printf("new hashtable->array pointer. \n");
tab->hash_code_fp=&hash_code_fp_default;
tab->value_free_fp=NULL;
tab->key_free_fp=NULL;
return tab;
}
p_hash_entry new_entry(){
p_hash_entry this;
this = (p_hash_entry)malloc(sizeof(struct __hash_entry));
this->hash_code=0;
this->key=NULL;
this->klen=0;
this->next=NULL;
this->value=NULL;
printf("new entry . \n");
return this;
}
unsigned int hash_code_fp_default(const char* key){
register unsigned int hash;
for(hash=0;*key;key++)
hash = *key+hash*31;
return abs(hash);
}
void std_key_free(char *p){
if(p)
free(p);
}
void std_value_free(void *p){
if(p)
free(p);
}
BOOL hash_remove_key(p_hashtable tab, const char* key)
{
void* value;
p_hash_entry e,prev,next;
int hash,ind;
if(!tab||!key)return FALSE;
hash=tab->hash_code_fp(key);
ind=HASH_IND(hash,tab->capacity);
e=tab->array[ind];
prev=e;
next=NULL;
while(e)
{
next=e->next;
if(e->hash_code==hash && !strcmp(key,e->key))
{
tab->size--;
if(e==prev)
tab->array[ind]=next;
else
prev->next=next;
break;
}else{
prev=e;
e=next;
}
}
if(e){
if(tab->key_free_fp)tab->key_free_fp((char *)e->key);
if(tab->value_free_fp)tab->value_free_fp((void *)e->value);
free(e);
printf("free entry\n");
return TRUE;
}
return FALSE;
}
BOOL hash_data_clear(p_hashtable tab)
{
p_hash_entry p;
p_hash_entry q;
int i=0;
if(!tab)return FALSE;
for(i=0;i<tab->capacity;i++)
{
for(p=tab->array[i];p;p=q)
{
q=p->next;
if(tab->key_free_fp)tab->key_free_fp((char*)p->key);
if(tab->value_free_fp)tab->value_free_fp((void*)p->value);
free(p);
printf("free hash entry \n");
}
tab->array[i]=0;
}
tab->size=0;
return TRUE;
}
BOOL free_hashtab(p_hashtable tab)
{
hash_data_clear(tab);
free(tab->array);
printf("free--hash->array.\n");
tab->array=NULL;
tab->capacity=0;
free(tab);
printf("free--hashtab.\n");
tab=NULL;
return TRUE;
}
void* hash_get(tab,key)
p_hashtable tab;
const char* key;
{
p_hash_entry e;
int hash;
if(!tab||!key)return NULL;
hash=tab->hash_code_fp(key);
for(e=tab->array[HASH_IND(hash,tab->capacity)];e;e=e->next)
{
if(e->hash_code==hash&&!strcmp(e->key,key))
{
return ((void *)e->value);
}
}
return NULL;
}
BOOL hash_put(p_hashtable tab,const char* key, const void* value){
int hash ;
int ind;
p_hash_entry next_entry;
p_hash_entry entry;
if(!tab||!key||!value)return FALSE;
hash = tab->hash_code_fp(key);
ind = HASH_IND(hash,tab->capacity);
next_entry=tab->array[ind];
entry=new_entry();
entry->hash_code=hash;
entry->key=key;
entry->value=value;
entry->next=next_entry;
entry->klen=strlen(key);
tab->array[ind]=entry;
tab->size++;
if((tab->size*3/2)>tab->capacity)
hash_resize(tab);
return TRUE;
}
BOOL hash_resize(p_hashtable tab){
p_hash_entry* new_array;
p_hash_entry entry,next;
int new_capacity,i,ind;
new_capacity=tab->capacity*2;
new_array=(p_hash_entry*)calloc(new_capacity,sizeof(p_hash_entry));
for(i=0;i<tab->capacity;i++){
if(entry=tab->array[i]){
do{
tab->array[i]=0;
next = entry->next;
ind=HASH_IND(entry->hash_code,new_capacity);
entry->next=new_array[ind];
new_array[ind]=entry;
entry=next;
}while(entry);
}
}
free(tab->array);
printf("resize free old array \n");
printf("hash_resize to %d\n",new_capacity);
tab->array=new_array;
tab->capacity=new_capacity;
return TRUE;
}
BOOL hash_contains_key(p_hashtable tab, const char* key){
if(!tab||!key)return FALSE;
return (hash_get(tab,key)!=NULL);
}
void hash_foreach_no_clear(p_hashtable tab,hash_foreach_fp fp){
int i;
if(!tab||!fp)return;
for(i=0;i<tab->capacity;i++)
{
if(tab->array[i])
if(!fp(tab->array[i]))
return;
}
}
void hash_foreach_clear(p_hashtable tab,hash_foreach_fp fp)
{
p_hash_entry p;
p_hash_entry q;
int i=0;
if(!tab||!fp)return;
for(i=0;i<tab->capacity;i++)
{
for(p=tab->array[i];p;p=q)
{
q=p->next;
fp(p);
if(tab->key_free_fp)tab->key_free_fp((char*)p->key);
if(tab->value_free_fp)tab->value_free_fp((void*)p->value);
free(p);
printf("free hash entry \n");
}
tab->array[i]=0;
}
tab->size=0;
}
unsigned int hash_code_fp_simple(const char* key){
return 101;
}
BOOL hash_foreach_fp_simple(p_hash_entry e){
printf("foreach : key=%s,value=%s\n",e->key,e->value);
return TRUE;
}
int main(){
int i;
char *key,*value;
char key_buf[11];
p_hashtable tab = new_hashtab();
tab->key_free_fp=&std_key_free;
tab->value_free_fp=&std_value_free;
tab->hash_code_fp=&hash_code_fp_default;
for(i=0;i<100;i++)
{
key=(char *)malloc(sizeof(char)*11);
value=(char *)malloc(sizeof(char)*11);
memset(key,0,11);
memset(value,0,11);
sprintf(key,"key_%d",i);
sprintf(value,"val_%d",i);
hash_put(tab,key,value);
}
hash_foreach_no_clear(tab,&hash_foreach_fp_simple);
hash_remove_key(tab,"key_2");
for(i=10;i<tab->size;i++)
{
memset(key_buf,0,11);
sprintf(key_buf,"key_%d",i);
printf("get==>key=%s,val=%s\n",key_buf,hash_get(tab,key_buf));
}
hash_data_clear(tab);
printf("hash.size : %d\n",tab->size);
free_hashtab(tab);
return 0;
}