一種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");
}
           

運作結果如下：