当前位置: 编程技术>c/c++/嵌入式
c语言实现的hashtable分享
来源: 互联网 发布时间:2014-10-23
本文导语: 头文件 hashtable.h 代码如下:typedef struct _Bucket{ char *key; void *value; struct _Bucket *next;} Bucket;typedef struct _HashTable{ int size; int total; struct _Bucket *buckets;} HashTable;int hash_init(HashTable **ht);int hash_find(HashTable *ht,...
头文件 hashtable.h
代码如下:
typedef struct _Bucket
{
char *key;
void *value;
struct _Bucket *next;
} Bucket;
typedef struct _HashTable
{
int size;
int total;
struct _Bucket *buckets;
} HashTable;
int hash_init(HashTable **ht);
int hash_find(HashTable *ht, char *key, void **result);
int hash_insert(HashTable *ht, char *key, void *value);
int hash_remove(HashTable *ht, char *key);
int hash_loop(HashTable *ht, void **result);
//int hash_index(HashTable *ht, char *key);
static unsigned int ELFHash(char *str, unsigned int length);
hashtable.c
代码如下:
#include
#include
#include
#include "hashtable.h"
#include "mempool.h"
#include "log.h"
#define SUCCESS 1
#define FAILED 0
#define HASH_LEN 5
int hash_init(HashTable **ht) {
(*ht) = (HashTable *)malloc(sizeof(HashTable));
if (NULL == ht) {
write_log("HashTable init error");
exit(1);
}
(*ht)->size = 0;
(*ht)->total = HASH_LEN;
Bucket *bucket = (Bucket *)malloc(sizeof(Bucket) * HASH_LEN);
memset(bucket, 0, sizeof(sizeof(Bucket) * HASH_LEN));
(*ht)->buckets = bucket;
return SUCCESS;
}
int hash_insert(HashTable *ht, char *key, void *value) {
if (ht->size >= ht->total) {
ht->buckets = (Bucket *)realloc(ht->buckets, sizeof(Bucket) * (ht->size + HASH_LEN));
ht->total = ht->size + HASH_LEN;
}
int index = hash_index(ht, key);
Bucket *bucket = &ht->buckets[index];
int _tmpindex;
char _tmpindexstr[20];
while (NULL != bucket->value) {
while (NULL != bucket->next) {
if (strcmp(key, bucket->key) == 0) {
memset(bucket->value, 0, sizeof(bucket->value));
memcpy(bucket->value, value, sizeof(value));
return SUCCESS;
}
bucket = bucket->next;
}
do {
_tmpindex = abs(rand() - index);
sprintf(_tmpindexstr, "%d", _tmpindex);
_tmpindex = hash_index(ht, _tmpindexstr);
} while (_tmpindex == index || ht->buckets[_tmpindex].value != NULL);
index = _tmpindex;
bucket->next = &ht->buckets[index];
bucket = bucket->next;
}
bucket->key = (char *)malloc(sizeof(key));
bucket->value = (void *)malloc(sizeof(value));
memcpy(bucket->key, key, sizeof(key));
memcpy(bucket->value, value, sizeof(value));
bucket->next = NULL;
ht->size ++;
return SUCCESS;
}
int hash_find(HashTable *ht, char *key, void **result) {
int index = hash_index(ht, key);
Bucket *bucket = &ht->buckets[index];
if (NULL == bucket->value) {
return FAILED;
}
while (strcmp(key, bucket->key)) {
if (NULL != bucket->next) {
bucket = bucket->next;
} else {
break;
}
}
if (NULL == bucket->value || strcmp(key, bucket->key)) {
return FAILED;
}
*result = bucket->value;
return SUCCESS;
}
int hash_delete(HashTable *ht, char *key) {
int index = hash_index(ht, key);
Bucket *bucket = &ht->buckets[index];
if (NULL == bucket->value) {
return FAILED;
}
while (strcmp(key, bucket->key)) {
if (NULL != bucket->next) {
bucket = bucket->next;
} else {
break;
}
}
if (NULL == bucket->value || strcmp(key, bucket->key)) {
return FAILED;
}
memset(bucket, 0, sizeof(Bucket));
ht->size --;
return SUCCESS;
}
void hash_status(HashTable *ht) {
printf("Total Size:tt%dn", ht->total);
printf("Current Size:tt%dn", ht->size);
}
int hash_index(HashTable *ht, char *key) {
return ELFHash(key, ht->total);
}
// ELF Hash Function
static unsigned int ELFHash(char *str, unsigned int length){
unsigned int hash = 0;
unsigned int x = 0;
while (*str)
{
hash = (hash >28
hash ^= (x >> 24);
//上面这行代码并不会对X有影响,本身X和hash的高4位相同,下面这行代码&~即对28-31(高4位)位清零。
hash &= ~x;
}
}
//返回一个符号位为0的数,即丢弃最高位,以免函数外产生影响。(我们可以考虑,如果只有字符,符号位不可能为负)
return (hash & 0x7FFFFFFF) % length;
}
其中key的映射使用的是 ELFHash 算法