C版哈希表(Hash Table)的简单实现（支持自动扩容）

hashtable.cpp

/**
 * Author: Wilson Zeng
 */

#include <stdio.h>
#include <cstdlib>
#include <string.h>
using namespace std;

// DECLARATIONS

#define INIT_SIZE 100
#define HASH_INDEX(ht, key) (key2int((key)) % (ht)->size)

typedef struct _Bucket {
	const char* key;
	const void* value;
	struct _Bucket *next;
} Bucket;

typedef struct _HashTable {
	int size;
	int elem_num;
	Bucket **buckets;
} HashTable;

int key2int(const char* key);
void hashtable_init(HashTable* ht, int size);
HashTable* hashtable_create(int size);
const void* hashtable_find(HashTable* ht, const char* key);
void hashtable_expand(HashTable* ht);
void hashtable_expand_if_needed(HashTable* ht);
void hashtable_insert(HashTable* ht, const char* key, const void* value);

// DEFINITIONS

int key2int(const char* key) {
	int result = 0;
	const char* current = key;
	while ((*current) != '\0') {
		result += (int)(*current);
		current++;
	}
	return result;
}

void hashtable_init(HashTable* ht, int size) {
	ht->size = size;
	ht->elem_num = 0;
	ht->buckets = (Bucket**) calloc(ht->size, sizeof(Bucket*));
}

HashTable* hashtable_create(int size) {
	HashTable* ht = (HashTable*) malloc(sizeof(HashTable));
	hashtable_init(ht, size);
	return ht;
}

const void* hashtable_find(HashTable* ht, const char* key) {
	int index = HASH_INDEX(ht, key);
	Bucket* tmp_bucket = ht->buckets[index];
	while (tmp_bucket) {
		if (strcmp(key, tmp_bucket->key) == 0) {
			return tmp_bucket->value;
		}
		tmp_bucket = tmp_bucket->next;
	}
	return NULL;
}

void hashtable_expand(HashTable* ht) {
	int old_size = ht->size;
	Bucket** old_buckets = ht->buckets;
	ht->size = old_size * 2; //2 times growing
	//alloc new buckets with new size
	ht->buckets = (Bucket**) calloc(ht->size, sizeof(Bucket*));
	//re-inserting the original elements
	Bucket* tmp_bucket = NULL;
	int i = 0;
	for (; i < old_size; i++) {
		tmp_bucket = old_buckets[i];
		while (tmp_bucket) { //iterate the bucket chain
			//insert into new buckets
			hashtable_insert(ht, tmp_bucket->key, tmp_bucket->value); //[CAN BE IMPROVED]here we can insert the existing bucket without releasing it and creating new
			//release the tmp bucket
			free(tmp_bucket);
			//next
			tmp_bucket = tmp_bucket->next;
		}
	}
	//release the whole old buckets
	free(old_buckets);
}

void hashtable_expand_if_needed(HashTable* ht) {
	if (ht->size <= ht->elem_num) {
		hashtable_expand(ht);
	}
}

void hashtable_insert(HashTable* ht, const char* key, const void* value) {
	//if already full, needs resize
	hashtable_expand_if_needed(ht);
	//locate the index
	int index = HASH_INDEX(ht, key);
	Bucket* old_bucket = ht->buckets[index];
	Bucket* tmp_bucket = old_bucket;
	//if exsits
	while (tmp_bucket) {
		//if find the same key, then just change the value
		if (strcasecmp(key, tmp_bucket->key) == 0) {
			tmp_bucket->value = value;
			printf("[UPDATE]the key %s 's value has been changed.\n", key);
			return ;
		}
		//pass to next
		tmp_bucket = tmp_bucket->next;
	}
	//if not exsits, create new bucket
	Bucket* new_bucket = (Bucket*) malloc(sizeof(Bucket));
	new_bucket->key = key;
	new_bucket->value = value;
	new_bucket->next = NULL;
	//if colliding, then shift the new one
	if (old_bucket) {
		new_bucket->next = old_bucket;
	}
	//replace with the new one
	ht->buckets[index] = new_bucket;
	ht->elem_num++;
	return ;
}

// EXECUTIONS

int main() {
	HashTable* ht = hashtable_create(INIT_SIZE);
	hashtable_insert(ht, "t007", "zcs");
	hashtable_insert(ht, "t001", "sssss");
	hashtable_insert(ht, "t007", "updated zcs");
	const char* value = (const char*)hashtable_find(ht, "t007");
	printf("t007=%s\n", value);
	value = (const char*)hashtable_find(ht, "t001");
	printf("t007=%s\n", value);
	printf("size=%d, used=%d\n", ht->size, ht->elem_num);
	free(ht);
	return 0;
}