简单哈希

                  

简单哈希

Description
使用线性探测法(Linear Probing)可以解决哈希中的冲突问题，其基本思想是：设哈希函数为h(key) = d, 并且假定哈希的存储结构是循环数组, 则当冲突发生时, 继续探测d+1, d+2…, 直到冲突得到解决.

例如, 现有关键码集为 {47，7，29，11，16，92，22，8，3}，

设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；采用线性探测法处理冲突。建哈希表如下：



现在给定哈希函数为Hash(key)= key mod m，要求按照上述规则, 使用线性探测法处理冲突.要求建立起相应哈希表，并按要求打印。

Input

仅有一个测试用例, 第1行为整数n与m（1 <= n, m <= 10000）， n代表key的总数, m代表哈希表的长度, 并且令哈希函数为: Hash(key) = key mod m.
接下来n行，每行一个整数，代表一个key。Key与key两两不相同 ( 0 <= key <= 10, 000)。

Output
输出建立好的hash表，比如下表



应输出

0#11
1#22
2#NULL
3#47
4#92
5#16
6#3
7#7
8#29
9#8
10#NULL
----------------------------
Sample Input
Copy sample input to clipboard
3 5
1
5
6
-----------------------------
Sample Output
0#5
1#1
2#6
3#NULL
4#NULL
-------------------------------
代码如下：

#include<iostream>
using namespace std;

int a[10001];

int Hash(int key,int m)
{
	return key%m;
}

int main()
{
	int n,m,key;
	cin>>n>>m;
	
	for(int j = 0;j < n;j++)
	{
		cin>>key;
		int index = Hash(key,m);

		while(1)
		{
			if(a[index] == '\0')
			{
				a[index] = key;
				break;
			}
			index=(index+1)%m;
		}
	}

	for(int i = 0;i < m;i++)
	{
		cout<<i<<"#";
		if(a[i]=='\0')
			cout<<"NULL"<<endl;
		else
			cout<<a[i]<<endl;
	}

	return 0;
}