C语言实现的哈希表

为了巩固一下链表知识，自己实现的一个哈希表，在GCC 4.4.7下编译通过；hash.h

/** * Author : maben * Date   : 2014-12-23 */#ifndef __HASH_H__#define __HASH_H__typedef struct _bucket {    char* key;    char* value;    struct _bucket* next;}Bucket;typedef struct _hash {    Bucket* buckets;}HashTable;void hash_init(HashTable** hash);unsigned int get_hash_index(char* str);int hash_insert(HashTable* hash, char* key, char* value);int hash_find(HashTable* hash, char* key, Bucket** bucket);int hash_remove(HashTable* hash, char* key);void hash_free(HashTable* hash);#endif

hash.c

/** * Author : maben * Date   : 2014-12-23 */#include "stdio.h"#include "hash.h"#include "assert.h"#define HASH_SIZE 100void hash_init(HashTable** hash) {    (*hash) = (HashTable*)malloc(sizeof(HashTable));    if ((*hash) == NULL) {        printf("Hash table initialization failure!\n");        exit(0);    }    (*hash)->buckets = (Bucket*)malloc(sizeof(Bucket) * HASH_SIZE);    memset((*hash)->buckets, 0, sizeof(Bucket) * HASH_SIZE);}unsigned int get_hash_index(char* str) {    unsigned int hash = 0;    unsigned int x = 0;    while (*str) {        hash = (hash <> 24);            hash &= ~x;        }    }    return (hash & 0x7FFFFFFF) % HASH_SIZE;}int hash_insert(HashTable* hash, char* key, char* value) {    assert(hash != NULL);    assert(key != NULL);    int index = get_hash_index(key);    Bucket* bucket;    bucket = &hash->buckets[index];    while (NULL != (bucket->next)) {        bucket = bucket->next;    }    int key_len = strlen(key);    int value_len = strlen(value);    bucket->key = (char*)malloc(sizeof(char) * (key_len + 1));    bucket->value = (char*)malloc(sizeof(char) * (value_len + 1));    strcpy(bucket->key, key);    bucket->key[key_len] = '\0';    strcpy(bucket->value, value);    bucket->value[value_len] = '\0';    bucket->next = (Bucket*)malloc(sizeof(Bucket));    memset(bucket->next, 0, sizeof(Bucket));    bucket->next->next = NULL;    return 0;}int hash_find(HashTable* hash, char* key, Bucket** result){    assert(hash != NULL);    assert(key != NULL);    int index = get_hash_index(key);    Bucket* bucket = &hash->buckets[index];    while (bucket) {        if (bucket->key && strcmp(key, bucket->key) == 0) {            (*result) = bucket;            return 1;        }        bucket = bucket->next;    }    return 0;}int hash_remove(HashTable* hash, char* key){    assert(hash != NULL);    assert(key != NULL);    int index = get_hash_index(key);    Bucket* bucket = &hash->buckets[index];    int is_sub = 0;    Bucket* prev = NULL;    while (bucket) {        if (strcmp(key, bucket->key) != 0)            continue;        if (bucket->key)            free(bucket->key);        if (bucket->value)            free(bucket->value);        if (is_sub) {            prev->next = bucket->next;            free(bucket);            return 1;        } else {            if (bucket->next)                memcpy(bucket, bucket->next, sizeof(Bucket));            return 1;        }        prev = bucket;        bucket = bucket->next;        is_sub++;    }    return 0;}void hash_free(HashTable* hash){    int i = 0;    Bucket* bucket;    for (i = HASH_SIZE - 1; i > -1; i--) {        bucket = &hash->buckets[i];        if (!bucket)            continue;        int is_sub = 0;        do {            if (bucket->key)                free(bucket->key);            if (bucket->value)                free(bucket->value);            if (is_sub) {                Bucket* tmp = bucket;                bucket = bucket->next;                free(tmp);            } else {                bucket = bucket->next;            }            is_sub++;        } while(bucket);    }    free(hash->buckets);    free(hash);    hash = NULL;}

用法：

#include "stdio.h"#include "hash.h"int main(int argc, char* argv[]) {    HashTable* hash;    hash_init(&hash);    int i = 0;    for (; i < 200; i++) {        char key[10] = { 0 };        char value[10] = { 0 };        sprintf(key, "hello%d", i);        sprintf(value, "world%d", i);        hash_insert(hash, key, value);    }    for (i = 0; i < 200; i++) {        if (i % 2 == 0) {            char key[10] = { 0 };            sprintf(key, "hello%d", i);            hash_remove(hash, key);        }    }    for (i = 0; i %s\n", bucket->key, bucket->value);        }    }    hash_free(hash);    return 0;}