# 哈希表的基本原理

数据的储存是通过`储存位置``其关键字`之间的某种映射关系来实现时,
称这种对应关系为哈希(Hash)函数。
当不同的关键字由映射关系而得到`同一`哈希地址时,
称此现象为`冲突`
对于冲突只能尽可能减小,不可能完全避免,
当建立哈希表时,应确定一个`好的哈希函数`和一种`有效的冲突处理`方法。
当关键字集合中的任何一个关键字都能以`同等的概率`而被映射到地址集合中时,
称此类哈希函数为`均匀的哈希函数`
此处介绍以`除留余数法`的哈希函数与`链地址法`的冲突处理方法来创建的哈希表
假设储存空间为`7`(key),哈希函数为函数f(data) = data % key,
储存空间中储存的是`哈希结点指针`,当数据进行储存时,先通过哈希函数来确定`索引值`
储存时,通过确定的`索引值`来将数据直接映射到储存空间的相应位置。

# 哈希表的基本创建

Hash_Table_.h(头文件)
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define ElemType int
#define MAX_SPACE 7
struct Hash_Node
{
	ElemType data;
	struct Hash_Node* Next;
};
void Init_Hash_Table(struct Hash_Node* (*HT)[MAX_SPACE]);
void Hash_Table_Insert(struct Hash_Node* (*HT)[MAX_SPACE], const ElemType data);
void Show_Hash_Table(struct Hash_Node* (*HT)[MAX_SPACE]);
struct Hash_Node* Search_Hash_Value(struct Hash_Node* (*HT)[MAX_SPACE],const ElemType data);
void ReMove_Hash_Value(struct Hash_Node* (*HT)[MAX_SPACE], const ElemType data);
void Hash_Table_Clean(struct Hash_Node* (*HT)[MAX_SPACE]);
Hash_Table_.c
#include"_Hash_Table.h"
void Init_Hash_Table(struct Hash_Node* (*HT)[MAX_SPACE])
{
	assert(NULL != HT);
	int i = 0;
	for (i = 0; i < MAX_SPACE; i++)
	{
		(*HT)[i] = NULL;
	}
}
static Hash(ElemType data)
{
	return (data % MAX_SPACE);
}
void Hash_Table_Insert(struct Hash_Node* (*HT)[MAX_SPACE], const ElemType data)
{
	assert(NULL != HT);
	int index = Hash(data);
	struct Hash_Node* P_HT = (struct Hash_Node*)malloc(sizeof(struct Hash_Node));
	assert(NULL != P_HT);
	P_HT->data = data;
	P_HT->Next = NULL;
	if (NULL == (*HT)[index])
	{
		(*HT)[index] = P_HT;
	}
	else
	{
		P_HT->Next = (*HT)[index];
		(*HT)[index] = P_HT;
	}
}
void Show_Hash_Table(struct Hash_Node* (*HT)[MAX_SPACE])
{
	assert(NULL != HT);
	int i = 0;
	struct Hash_Node* P_HT = NULL;
	for (i = 0; i < MAX_SPACE; i++)
	{
		P_HT = (*HT)[i];
		printf("%d:", i);
		while (NULL != P_HT)
		{
			printf("%d→",P_HT->data);
			P_HT = P_HT->Next;
		}
		printf("NULL\n");
	}
	
}
struct Hash_Node* Search_Hash_Value(struct Hash_Node* (*HT)[MAX_SPACE],const ElemType data)
{
	assert(NULL != HT);
	int index = Hash(data);
	struct Hash_Node* P_HT = (*HT)[index];
	while (NULL != P_HT && data != P_HT->data)
	{
		P_HT = P_HT->Next;
	}
	return P_HT;
}
void ReMove_Hash_Value(struct Hash_Node* (*HT)[MAX_SPACE], const ElemType data)
{
	assert(NULL != HT);
	int index = Hash(data);
	struct Hash_Node* P_HT = (*HT)[index];
	struct Hash_Node* P_HT_data = NULL;
	
	while (NULL != P_HT && data != P_HT->Next->data)
	{
		P_HT = P_HT->Next;
	}
	P_HT_data = P_HT->Next;
	P_HT->Next = P_HT_data->Next;
	free(P_HT_data);
	P_HT_data = NULL;
}
void Hash_Table_Clean(struct Hash_Node* (*HT)[MAX_SPACE])
{
	assert(NULL != HT);
	struct Hash_Node* P_HT = NULL;
	struct Hash_Node* P_Head = NULL;
	int i = 0;
	for (i = 0; i < MAX_SPACE; i++)
	{
		P_HT = (*HT)[i];
		while (NULL != P_HT)
		{
			P_Head = P_HT;
			P_HT = P_HT->Next;
			P_Head->Next = NULL;
			free(P_Head);
			P_Head = NULL;
		}
	}
}
Hash_Table_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"_Hash_Table.h"
#define ElemForm "%d"
#define ElemEndForm -1
static void Show_Menu()
{
	printf("\n***************************************************\n");
	printf("[1] Hash_Table_Insert ******[2] Search_Hash_Value *\n");
	printf("[3] ReMove_Hash_Value ******[4] Hash_Table_Clean  *\n");
	printf("[5] Show_Hash_Table                               *\n");
	printf("***************************************************\n");
}
int main()
{
	ElemType data;
	struct Hash_Node* Hash_Table[MAX_SPACE];
	struct Hash_Node* value = NULL;
	int option = 0;
	int flag = 1;
	
	Init_Hash_Table(&Hash_Table);
	Show_Menu();
	while (printf("选择为>: "), scanf("%d", &option), printf("\n"), option)
	{
		getchar();
		switch (option)
		{
			case 1:
				if (!flag)
				{
					Init_Hash_Table(&Hash_Table);
					flag = 1;
				}
				printf("输入的值为(结束标志'-1')>:");
				while (scanf(ElemForm, &data), ElemEndForm != data)
				{
					Hash_Table_Insert(&Hash_Table, data);
				}
				Show_Hash_Table(&Hash_Table);
				break;
			case 2:
				printf("搜寻值为>: ");
				scanf(ElemForm, &data);
				value = Search_Hash_Value(&Hash_Table, data);
				printf(ElemForm, value->data);
				break;
			case 3:
				printf("清除的值为>: ");
				scanf(ElemForm, &data);
				ReMove_Hash_Value(&Hash_Table, data);
				Show_Hash_Table(&Hash_Table);
				break;
			case 4:
				Hash_Table_Clean(&Hash_Table);
				flag = 0;
				break;
			case 5:
				Show_Hash_Table(&Hash_Table);
				break;
			default: printf("选择输入错误");
		}
	}
	printf("已退出");
	Hash_Table_Clean(&Hash_Table);
	
	return 0;
}

# LeetCode 案题

Two_Sum
/*
题目
Given an array of integers nums and an integer target, 
return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, 
and you may not use the same element twice.
You can return the answer in any order.
 
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums [0] + nums [1] == 9, we return [0, 1].
Constraints:
2 <= nums.length <= 104
-109 <= nums [i] <= 109
-109 <= target <= 109
Only one valid answer exists.
C 语言 Hash 表解法 (6ms)
*/
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define MAX 10000
struct Hash_Node
{
    int data;
    int cur;
};
void Init_Hash(struct Hash_Node* (*HN)[MAX])
{
    int i = 0;
    for(i = 0; i < MAX;++i)
        (*HN)[i] = NULL;
}
int hash(const int data)
{
    return (data > 0 ? data % MAX : (data * -1) % MAX);
}
struct Hash_Node* Search_Opposite(struct Hash_Node* (*HN)[MAX],const int data)
{
    int index = hash(data);
    
    return (NULL == (*HN)[index] ? NULL : (*HN)[index]);
}
void Hash_Insert(struct Hash_Node* (*HN)[MAX],const int data,const int cur)
{
    int index = hash(data);
    struct Hash_Node* P_HN = (struct Hash_Node*)malloc(sizeof(struct Hash_Node));
    assert(NULL != P_HN);
    
    P_HN->data = data;
    P_HN->cur = cur;
    (*HN)[index] = P_HN;
}
int* twoSum(int* nums, int numsSize, int target,int* returnSize)
{
    int* result = (int*)malloc(sizeof(int) * 2);
    struct Hash_Node* P_HN = NULL;
    struct Hash_Node* HN[MAX];
    *returnSize = 2;
    int i = 0;
    
    Init_Hash(&HN);
    for(i = 0;i < numsSize;++i)
    {
        P_HN = Search_Opposite(&HN, target - *(nums + i));
        
        if(NULL != P_HN && target == P_HN->data + *(nums + i) && i != P_HN->cur)
        {
            *result = P_HN->cur;
            *(result + 1) = i;
            return result;
        }
        Hash_Insert(&HN,*(nums + i),i);
    }
    return NULL;
}