哈希表之简易数学原理和简易实现（史上最简单易懂的哈希表介绍）- C

什么是哈希表呢？我先不说，但其思想确实厉害。下面，我以最简单易懂的方式来介绍哈希表。

你要是去看教科书啊，还没有理解哈希表的原理，他就给你介绍近10种防冲突的方法，这就是中国的教育。你要是去网上搜点资料问为什么哈希表查找的时间复杂度为O（1），他说因为哈希表只需要比较一次即可。最后你满意而来，扫兴而归。

我呢？喜欢把复杂的东西搞简单，下面我来介绍一下哈希表.

为了简便起见，假设有一个数组An = {81, 62, 55, 43, 97, 76, 49, 98, 64}; 这大概就是你在高一上学期数学学习的内容吧。下面，任何给定一个数x, 如果判断x是否在该给定的数列An中呢？作为一个正常的人，我们自然会想，把x先和81， 62， ..., 进行比较呗，对了，你这么想就对了，这标志着你完全没有入门哈希表。

从这个角度来讲，提出哈希表的人，确实很了不起，因为他没有采用正常人的思路。我们来看看哈希表人的思路：

现在，我们来看看程序：


#include <iostream>
using namespace std;
 
int hash(int key, int n)
{
	return key % n;
}
 
int main()
{
	int a[9] = {81, 62, 55, 43, 97, 76, 49, 98, 64};
	int b[9] = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
	int i = 0;
	for(i = 0; i < 9; i++)
	{
		b[hash(a[i], 10)] = a[i];
	}
	
	int x = 0;
	for(x = 0; x < 1000000; x++)
	{
		if(b[hash(x, 10)] == x) //对于每一个x, 只需要比较一次哈
		{
			cout << x << " is in a[...]" << endl;
		}
	}
 
	return 0;
}