哈希表（C语言实现）超级简洁版

数据结构设计

//字典类型
#define DICT_TYPE_INT 0
#define DICT_TYPE_STR 1

//键值对
typedef struct dict_entry
{
	struct dict_entry* next;
	void* key;
	void* value;
}dict_entry;

typedef struct dict
{
	//哈希函数
	unsigned int (*hash)(void* key);
	// table 数组存放 dict_entry 指针
	dict_entry** table;
	int size;
	//掩码
	int sizemask;
}dict;

接口设计

//哈希函数（适用整数）
static unsigned int hash_integer(void* key);
//哈希函数（适用字符串）
static unsigned int hash_33(void* key);
//创建一个dict
dict* dict_create(int type);
//创建一个dict_entry
dict_entry* dict_create_entry(void* key, void* value);
//字典插入一个键值对
dict* dict_put_entry(dict* dict, void* key, void* value);
//dict获取值
void* dict_get_value(dict* dict, void* key);
//清除所有dict元素
void dict_empty(dict* dict);
//释放dict
void dict_release(dict* dict);

接口实现

/哈希函数（适用整数）
static unsigned int hash_integer(void* key)
{
	return (*(int*)key * 2654435769) >> 28;
}

//哈希函数（适用字符串）
static unsigned int hash_33(void* key)
{
	unsigned int hash = 0;
	while (*(char*)key!=0)
	{
		//左移5位相当于*32，再加hash相当于*33
		hash = (hash << 5) + hash + (*(char*)key)++;
	}
	return hash;
}

//创建一个dict
dict* dict_create(int type)
{
	dict* dict = (struct dict*)malloc(sizeof(struct dict));
	if (dict == NULL)
		return NULL;
	if (type == DICT_TYPE_INT)
		dict->hash = &hash_integer;
	else
		dict->hash = &hash_33;

	dict->size = 1;
	dict->sizemask = dict->size - 1;
	dict->table = (dict_entry**)malloc(sizeof(dict_entry*) * (dict->size));
	if (dict->table == NULL)
		return NULL;
	memset(dict->table, 0, sizeof(dict_entry*) * (dict->size));
	return dict;
}

//创建一个dict_entry
dict_entry* dict_create_entry(void* key, void* value) 
{
	dict_entry* entry = (struct dict_entry*)malloc(sizeof(struct dict_entry));
	if (entry == NULL)
		return NULL;
	entry->key = key;
	entry->value = value;
	entry->next = NULL;
	return entry;
}

//字典插入一个键值对
dict* dict_put_entry(dict* dict, void* key, void* value)
{
	//无论key值是否存在都直接新插入 key - value
	unsigned int hash = dict->hash(key);
	int pos = hash & dict->sizemask;

	dict_entry* entry;
	entry = dict_create_entry(key,value);
	entry->next = dict->table[pos];
	dict->table[pos] = entry;

	return dict;
}



//dict获取值
void* dict_get_value(dict* dict, void* key)
{
	unsigned int hash = dict->hash(key);
	int pos = hash & dict->sizemask;
	if (dict->table[pos] == NULL)
		return NULL;
	dict_entry* cur = dict->table[pos];
	while (dict->hash(cur->key) != dict->hash(key))
	{
		if (cur->next != NULL)
			cur = cur->next;
		else
			return NULL;
	}
	return cur->value;
}

//清除所有dict元素
void dict_empty(dict* dict)
{
	for (int i = 0; i < dict->size; i++)
	{
		if (dict->table[i]!=0)
		{
			dict_entry* cur, * next;
			cur = dict->table[i];
			while (cur)
			{
				next = cur->next;
				free(cur);
				cur = next;
			}
			dict->table[i] = 0;
		}//end if
	}//end for
	return ;
}

//释放dict
void dict_release(dict* dict)
{
	dict_empty(dict);
	free(dict->table);
	free(dict);

	return;
}

测试代码

int main()
{
	//创建一个key为字符串的字典
	dict* dict = dict_create(1);

	char str[] = "name";
	char str2[] = "Austin";
	char str3[] = "Lookcos";
	char str4[] = "age";
	int age = 18;

	dict_put_entry(dict, &str4, &str2);
	printf("%sn", (char*)dict_get_value(dict, &str4));

	dict_put_entry(dict, &str2, &str);
	printf("%sn", (char*)dict_get_value(dict, &str2));

	dict_put_entry(dict, &str, &str3);
	printf("%sn", (char*)dict_get_value(dict, &str));

	dict_put_entry(dict, &str4, &age);
	printf("age: %dn", *(int*)dict_get_value(dict, &str4));

	return 0;
}