第一节——初赛中的Hash

        哈希表，也称散列表，是一种高效的数据结构。它的最大优点就是把数据存储和查找所消耗的时间大大降低，几乎可以看成是O(1)的，而代价是消耗比较多的内存。在当前竞赛可利用内存空间越来越多、程序运行时间控制的越来越近的情况下，“空间换时间”的做法还是很值得的。

        哈希冲突，不能保证每个元素的关键字与函数值是一一对应的，这样就产生了“冲突”。

        解决冲突方法：

        1、直接取余数法      h(k)=k  mod  m     //m一般为一个大素数

              关键字k除以m，取余数作为在Hash表中的位置。

        2、乘积取整法；

        3、平方取中法；

        4、线性探测法

        5、链地址法（后两种会在后面详细讲到，第二种和第三种可以自行了解，不强求）

        查找算法

        基本的查找算法有以下4种：

                1、线性查找（挨个看呗）

                2、二分查找（log级别每次折半查找，前提是所有元素必须是顺序排列的）

                3、分块查找（块与块有序、块内无序，可以理解成块外用二分、块内用线性）

                4、哈希查找（他来了，他来了！！）

        哈希查找简介

                1、哈希是Hash的音译，意译就是散列。哈希查找是一种按关键字地址的快速检索方法。

                2、哈希与其他查找方法的不同之处

                        （1）哈希查找是对记录的关键字值进行某种运算，直接求出记录的地址

                        （2）快——关键字到地址直接转换，无序反复比较

                        （3）核心不在于如何“比较”，而在于如何“计算”

                        （4）最能体现计算机科学精髓的查找方法

        哈希查找的基本思想：记录关键字与其存储地址之间的映射关系H(key)，把某个较大的集合P映射到另一个较小的集合Q中，核心就是设计哈希函数，并构建哈希表。

        哈希查找过程：

                1、由给定的关键字key，根据哈希函数计算出对应的哈希地址H(key)

                2、根据H(key)直接找到该记录的存储位置

        哈希冲突与解决（系不系很多童鞋们都肥肠期待！！？？）

        当两个不同的数据的哈希值相同时，就会发生冲突（collision）

        处理哈希冲突的常用方法之一：链地址法

        链地址法具体步骤：

                （1）将哈希值相同的数据存在一个链表中

                （2）查找哈希表时，当查找到这个链表时必须采用线性查找方法

        哈希函数典型构造方法——求模取余法

                （1）H(key)=key % p

                （2）p<=m，哈希表表长为m

                （3）余数（哈希地址）总是循环出现，呈周期性变化

        哈希表的特点

        第二节——Hash查询代码实现

        哈希典型题

        哈希构造的链表中查询方式比较快。已知存在一个随机的数据表（表中数字均为正整数，没有重复），数据个数n≤50000；现在给定一些整数，查询在表中是否存在。

        二分代码实现（代码短，时间长）

#include<iostream>
#include<algorithm>
using namespace std;

int a[10005],l,r,mid;

int main()
{
	int key,n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n+1);
	while(m--)
	{
		cin>>key;
		l=1;
		r=n;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(a[mid]==key)
			{
				cout<<"yes\n";
				break;
			}
			if(a[mid]<key)
			{
				l=mid+1;
			}
			if(a[mid]>key)
			{
				r=mid-1;
			}
		}
		if(a[mid]!=key)
		{
			cout<<"no\n";
		}
	}
	return 0;
}

　　哈希代码实现（代码长、时间短）

#include<iostream>
using namespace std;

const int N=50000;
const int b=999979,H=999979;
int tot,adj[H],nxt[N],num[N];
int top,stk[N];

void init()
{
	tot=0;
	while(top)
	{
		adj[stk[top--]]=0;
	}
}

void insert(int key)
{
	int h=key%b;
	for(int e=adj[h];e;e=nxt[e])
	{
		if(num[e]==key)
		{
			return ;
		}
	}
	if(!adj[h])
	{
		stk[++top]=h;
	}
	nxt[++tot]=adj[h],adj[h]=tot;
	num[tot]=key;
}

bool query(int key)
{
	int h=key%b;
	for(int e=adj[h];e;e=nxt[e])
	{
		if(num[e]==key)
		{
			return true
		}
	}
	return false;
}

int main()
{
	int a[10000];
	init();
	int n,m;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		insert(a[i]);
	}
	cin>>m;
	int num;
	for(int i=1;i<=m;i++)
	{
		cin>>num;
		if(query(num))
		{
			cout<<"yes"<<endl;
		}
		else
		{
			cout<<"no"<<endll;
		}
	}
	return 0;
}

　　第三节——哈希冲突解决

        1、顺序寻址法

        设H(key)=key%9

        若当前位置已经有原先的数据了，则放到下一个位置去，如果下一个位置仍然不为空，那么久继续往后走，直到找到第一个为空的元素位置把该元素放进去。

        代码实现

int hash_table[N];
void push1(int x)
{
	int y=x%N;
	for(;hash_table[y]&&hash_table[y]!=x;)
	{
		y=(y+1)%N;
	}
	if(hash_table[y])
	{
		cout<<x<<"_has_occured_before!"<<endl;
	}
	else
	{
		hash_table[y]=x;
		cout<<x<<"_inserted."<<endl;
	}
}

　　2、链地址法（刚才说过了，不再多说了，直接上代码）

        代码实现（用到了动态数组vector，在STL里面，不知道的可以去百度上搜搜教程）

        推荐题目（洛谷）：P1102、P3370、P2957、P1955、P13381、P5018