一种hash表实现（分离链接法）

散列是一种用于以O（1）平均时间执行insert、delete和search的技术，但是不支持FindMin、FindMax以及排序等操作

基本思想：通过散列函数将数据进行处理，根据处理的结果将数据放置到一个hash表中

主要的问题：一旦数据产生冲突，如何处理冲突？

分离链接法就是一种常见处理冲突的方案，将冲突的数据放到一个Link List中，闲话少说，直接上干货：

#include<stdio.h>
#include<stdlib.h>

#define HASH_TABLE_SIZE 10
#define HASH_VALUE 11

struct my_list {
	int data;
	struct my_list *next;
};

struct my_hash {
	int hash_size;
	struct my_list **list;
};
//
//首先判断是否为空表，若不为空，则进行散列
//链表操作采用头插法
//
static int hash_func(struct my_hash *h,int my_data)
{
	int temp;
	struct my_list *l;
	if(h == NULL)
	{
		printf("Error: this is no hash table!!\n");
		return -1;
	}
	//为数据data分配一个my_list临时节点
	l = malloc(sizeof(struct my_list));
	if(NULL == l)
	{
		printf("Error: out of memory!!\n");
		return -1;
	}

	l->data = my_data;
	temp = my_data % HASH_VALUE;//散列函数
	if(h->list[temp]->next == NULL)
	{
			h->list[temp]->next = l;
			l->next = NULL;
	}
	else
	{
		l->next = h->list[temp]->next;
		h->list[temp]->next = l;
	}
	return 0;
}

static int find(struct my_hash *h,int my_data)
{
	int temp;
	struct my_list *l;
	if(NULL == h)
	{
		printf("Error: this is no hash table!!so not found\n");
		return -1;
	}
	
	temp = my_data % HASH_VALUE;
	if(h->list[temp]->next == NULL)
	{
		printf("Error: there is no %d in current hash table!!\n",my_data);
		return -1;
	}
	else{
		l = h->list[temp]->next;
		while(l != NULL && l->data != my_data)
			l = l->next;
		if(l == NULL)
		{
			printf("Error；there is no %d in current hash table!!\n",my_data);
			return -1;
		}
		printf("find %d in current hash table!\n",my_data);
		return 0;
	}
}

int main(void)
{
	struct my_hash *h;
	int i;
	int temp;
	int ret;

	h = malloc(sizeof(struct my_hash));
	if(NULL == h)
	{
		printf("Error: out of memory!!\n");
		return -1;
	}
	h->hash_size = HASH_VALUE;

	h->list = malloc(sizeof(struct my_list *)*h->hash_size);
	if(NULL == h->list)
	{
		printf("Error: out of memory!!\n");
		return -1;
	}

	for(i=0;i<h->hash_size;i++)
	{
		h->list[i] = malloc(sizeof(struct my_list));
		if(NULL == h)
		{
			printf("Error: out of memory!!\n");
			return -1;
		}

		h->list[i]->next = NULL;
	}

	i = 0;
	while(++i < HASH_TABLE_SIZE)
	{
		scanf("%d",&temp);
		ret = hash_func(h,temp);
		if(ret)
			return -1;
	}
	printf("plese input the data you want to find: ");
	scanf("%d",&temp);
	ret = find(h,temp);
	if(ret)
		printf("not found!!\n");
	else
		printf("find!!\n");
}