HashTable简单实现，使用ELFHash 哈希
?
头文件
#ifndef __GHASH_H_#define __GHASH_H_#define HASHSIZE 512typedef struct _Item{ char * key; char * value; struct Item * next;} Item;void GHashInit();Item * HashInSert(char * key,char * value);int HashRemove(char * key);Item * HashSearch(char * key);void FreeGHash();void PrintGHash();#endif?
c文件
#include<stdio.h>#include<stdlib.h>#include<string.h>#include "GHash.h"static struct Item *hashtab[HASHSIZE];static void freeItem(Item * item);static unsigned int _Hash(char *key);static unsigned int _ELFHash(char *str);void GHashInit(){ int i=0; for(i=0; i<HASHSIZE; i++) { hashtab[i]=NULL; }}Item * HashInSert(char * key,char * value){ Item * np; unsigned int hashval; if((np=HashSearch(key))==NULL) { np=(Item *)malloc(sizeof(Item)); if(NULL==np || NULL ==(np->key = strdup(key)) || NULL ==(np->value = strdup(value)) ) { return NULL; } hashval = _Hash(key); np->next = (Item *)hashtab[hashval]; hashtab[hashval] = np; } else { free(np->value); if((np->value=strdup(value))== NULL) { return NULL; } } return np;}int HashRemove(char * key){}Item * HashSearch(char * key){ Item *np; for(np = (Item *)hashtab[_Hash(key)]; np != NULL; np = np->next) if(strcmp(key,np->key) == 0) return np; return NULL;}void FreeGHash(){ int i=0; for(i=0; i<HASHSIZE; i++) { if(hashtab[i]!=NULL) { Item * tmp; Item * deln; for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i]) { hashtab[i]=tmp->next; freeItem(tmp);} } }}void PrintGHash(){ printf("Print Hash:\n"); int i=0; for(i=0; i<HASHSIZE; i++) { if(hashtab[i] !=NULL ) { printf("%d---",i); Item * tmp; for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next) { printf("%s:%s;",tmp->key,tmp->value);}printf("\n"); } }}static unsigned int _Hash(char *key){ return _ELFHash(key)%HASHSIZE;}// ELF Hash Functionstatic unsigned int _ELFHash(char *str){ unsigned int hash = 0; unsigned int x = 0; while (*str) { hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash if ((x = hash & 0xF0000000L) != 0) {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。 //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位 hash ^= (x >> 24); //清空28-31位。 hash &= ~x; } } //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负) return (hash & 0x7FFFFFFF);}static void freeItem(Item * item){ free(item->key); free(item->value); free(item);}?
?
?使用代码
?
Item * np; GHashInit(); if((np=HashInSert("123","abc"))==NULL) { printf("Insert %s:%s wrong\n","123","abc"); } PrintGHash(); if((np=HashInSert("456","def"))==NULL) printf("Insert %s:%s wrong\n","456","def"); PrintGHash(); if((np=HashSearch("123")) ==NULL) {printf("not find 123\n"); } printf("find 123:%s\n",np->value); FreeGHash(); PrintGHash();??
?
?
说明：
?HashInSert 当哈希表中存在了对应的Key值时，则使用新插入的Value替换以前的Value，即覆盖模式类型
?
1 楼 deepfuture 2012-03-26 关于字符串hash,我刚看了一下lucene的算法，非常不错，你可以看下这里