[转]libhash中的哈希函数

随便贴一个libhash中的hash函数，写的貌似不错，贴出来玩玩。

hash.h

/*
*AustralianPublicLicenceB(OZPLB)
*
*Version1-0
*
*Copyright(c)2004NationalICTAustralia
*
*Allrightsreserved.
*
*Developedby:Embedded,Real-timeandOperatingSystemsProgram(ERTOS)
*NationalICTAustralia
*http://www.ertos.nicta.com.au
*/

#ifndef_HASH_H
#define_HASH_H

#include<stdint.h>

structhashtable{
structhashentry**table;
unsignedintsize;
structhashentry*spares;
};

structhashentry{
structhashentry*next;
uintptr_tkey;
void*value;
};

structhashtable*hash_init(unsignedintsize);
voidhash_free(structhashtable*tablestruct);
uintptr_thash_hash(uintptr_tkey);
void*hash_lookup(structhashtable*tablestruct,uintptr_tkey);
inthash_insert(structhashtable*tablestruct,uintptr_tkey,void*value);
voidhash_remove(structhashtable*tablestruct,uintptr_tkey);

#endif/*!_HASH_H*/

hash.c

#include<stdint.h>
#include<stdlib.h>
#include<assert.h>

#include"hash.h"

structhashtable*
hash_init(unsignedintsize)
{
structhashtable*tablestruct;
intcounter;

/*Ourhashfunctiononlyworkswithpower-of-2bucketsizesforspeed.*/
assert((size&(size-1))==0);

tablestruct=malloc(sizeof(structhashtable));assert(tablestruct);
if(!tablestruct){
returnNULL;
}
tablestruct->table=malloc(size*sizeof(structhashentry*));
if(!tablestruct->table){
returnNULL;
}
for(counter=0;counter<size;counter++){
tablestruct->table[counter]=NULL;
}
assert(tablestruct->table);
tablestruct->size=size;
tablestruct->spares=NULL;

returntablestruct;
}

/*Refhttp://www.concentric.net/~Ttwang/tech/inthash.htm*/
uintptr_t
hash_hash(uintptr_tkey)
{
#if(UINTPTR_MAX==UINT32_MAX)
key+=~(key<<15);
key^=(key>>10);
key+=(key<<3);
key^=(key>>6);
key+=~(key<<11);
key^=(key>>16);
#elif(UINTPTR_MAX==UINT64_MAX)
key+=~(key<<32);
key^=(key>>22);
key+=~(key<<13);
key^=(key>>8);
key+=(key<<3);
key^=(key>>15);
key+=~(key<<27);
key^=(key>>31);
#else
#errorunsupportedwordsize
#endif
//printf("newkeyis%d ",key);
returnkey;
}

void*
hash_lookup(structhashtable*tablestruct,uintptr_tkey)
{
uintptr_thash;
structhashentry*entry;

hash=hash_hash(key)&(tablestruct->size-1);
for(entry=tablestruct->table[hash];entry!=NULL;entry=entry->next){
if(entry->key==key){
returnentry->value;
}
}
returnNULL;
}

/*Addthekeytothehashtable.Assumesthekeyisnotalreadypresent.*/
int
hash_insert(structhashtable*tablestruct,uintptr_tkey,void*value)
{
uintptr_thash;
structhashentry*entry;

hash=hash_hash(key)&(tablestruct->size-1);
//printf("bucketis%d ",hash);

entry=malloc(sizeof(structhashentry));
if(!entry){
return-1;
}
entry->key=key;
entry->value=value;
entry->next=tablestruct->table[hash];

tablestruct->table[hash]=entry;
return0;
}

/*Removesthekeyfromthehashtable.Doesnotsignalanerrorifthekey
*wasnotpresent.*/
void
hash_remove(structhashtable*tablestruct,uintptr_tkey)
{
uintptr_thash;
structhashentry*entry,*tmpentry;

hash=hash_hash(key)&(tablestruct->size-1);
entry=tablestruct->table[hash];
/*Ifthisisthefirstentrythenitneedsspecialhandling.*/
if(entry&&entry->key==key){
tmpentry=entry->next;
free(entry);
tablestruct->table[hash]=tmpentry;
}else{
while(entry){
if(entry->next&&entry->next->key==key){
tmpentry=entry->next;
entry->next=entry->next->next;
free(tmpentry);
break;
}
entry=entry->next;
}
}
}

hash_free.c

#include<stdint.h>
#include<stdlib.h>

#include"hash.h"

void
hash_free(structhashtable*tablestruct)
{
intcounter;
structhashentry*entry,*prev;

/*Needtofreebucketsandtablestructandeveryitemineverychain*/
for(counter=0;counter<tablestruct->size;counter++){
entry=tablestruct->table[counter];
while(entry){
prev=entry;
entry=entry->next;
free(prev);
}
}
free(tablestruct->table);
free(tablestruct);
}

来源：http://ertos.nicta.com.au/software/kenge/libhash/devel/

更多结果：http://www.google.cn/search?complete=1&hl=zh-CN&q=libhash&meta=