数据结构实战

        设定哈希函数的方法通常有直接定址法、数字分析法、平方取中法、折叠法、除留取余法、随机数法等等。这里我们采用的是折叠法来计算哈希值。设关键字的类型为int，占4个字节。我们对这4个字节的数进行折叠相加，计算出这个关键字的哈希值。此哈希函数如下：

char hashtable_hashcode(int key)
{
	char h_key = 0xff & key;
	h_key += 0xff & (key >> 8);
	h_key += 0xff & (key >> 16);
	h_key += 0xff & (key >> 24);
	return h_key;
}

        经过哈希函数计算后的值也有可能出现冲突，例如使用哈希函数对于1和256这两个关键字求值，结果均为1。解决哈希值冲突的办法也有很多，我们这里采用线性表来存放冲突哈希值的数据。对于1、2、3、4、256、257、258、259这8个关键字来说，它们的存储方式如下：

        下面关于线性表的实现我们在前面的章节已经完成，这里不再叙述。我们来实现哈希表的代码：

//哈希表大小
#define INIT_SIZE	(0xff)

//哈希表
typedef struct s_hashtable
{
	//线性表
	s_list *list;
} s_hashtable;

bool hashtable_init(s_hashtable *ht, void (*free_data)())
{
	if (ht == null)
	{
		return false;
	}

	ht->list = (s_list *) malloc(sizeof(s_list) * INIT_SIZE);
	for (int i = 0; i < INIT_SIZE; i++)
	{
		init_list(&ht->list[i], free_data);
	}

	return true;
}

//销毁哈希表
bool hashtable_destory(s_hashtable *ht)
{
	for (int i = 0; i < INIT_SIZE; i++)
	{
		//销毁线性表
		destroy_list(&ht->list[i]);
	}

	free(ht->list);

	return true;
}

//插入数据到哈希表
bool hashtable_push(s_hashtable *ht, int key, void *value)
{
	//计算哈希值
	char h_key = hashtable_hashcode(key);

	//插入数据
	return list_insert(&ht->list[h_key], key, value);
}

//移除一个数据
bool hashtable_remove(s_hashtable *ht, int key)
{
	//计算哈希值
	char h_key = hashtable_hashcode(key);

	//移除数据
	return list_delete(&ht->list[h_key], key);
}

//取得数据
void* hashtable_get(s_hashtable *ht, int key)
{
	//计算哈希值
	char h_key = hashtable_hashcode(key);

	//取得数据
	return list_get(&ht->list[h_key], key);
}

//计算哈希值
char hashtable_hashcode(int key)
{
	char h_key = 0xff & key;
	h_key += 0xff & (key >> 8);
	h_key += 0xff & (key >> 16);
	h_key += 0xff & (key >> 24);
	return h_key;
}

        写一个main函数来使用这个哈希表：

#include "hashtable.h"

int main(int argc, char **args)
{
	s_hashtable ht;
	hashtable_init(&ht, null);

	int t1 = 1111;
	int t2 = 2222;
	int t3 = 3333;
	int t4 = 4444;
	int t5 = 5555;

	hashtable_push(&ht, 1, &t1);
	hashtable_push(&ht, 2, &t2);
	hashtable_push(&ht, 3, &t3);
	hashtable_push(&ht, 4, &t4);
	hashtable_push(&ht, 256, &t5);

	printf("%d\n", *(int *) hashtable_get(&ht, 1));
	printf("%d\n", *(int *) hashtable_get(&ht, 2));
	printf("%d\n", *(int *) hashtable_get(&ht, 3));
	printf("%d\n", *(int *) hashtable_get(&ht, 4));
	printf("%d\n", *(int *) hashtable_get(&ht, 256));

	hashtable_destory(&ht);

	return 0;
}

        运行结果：

1111
2222
3333
4444
5555

        本例代码：

code path   chapter.07/e.g.7.6/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure