HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。
   它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希冲突/哈希碰撞
    不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的值哈希地址，我们称这种情况为哈希冲突。任意的散列函数都不能避免产生冲突。
   我给大家介绍的是哈希表的线性探测，线性探测的基本思路：
       1.用一个数据除以散列表的长度，余数是多少，就把这个数放在散列表下标相同的地方。
       2.如果发生哈希冲突，就看下一个位置是否有数据，一直到没有哈希冲突，就把这个数据放在此位置。
       3.如果已经试探到最后一个位置，但前面还有位置没有试探，那么我们就从开始位置继续试探，直到全部位置试探成功。
实现代码：
Hash.h中
//哈希表中存放数据的状态
enum State
{
	EMPTY,//没有数据
	DELETE,//删除数据后
	EXIST//有数据
};
template <class K>
class HashTable
{
public:
	//构造函数
	HashTable()
		:_table(NULL)
		, state(NULL)
		, _size(0)
		, _capatity(0)
	{}
	//构造函数
	HashTable(size_t size)
		:_table(new K[size])
		, _state(new State[size])
		, _capatity(size)
		, _size(0)
	{
		for (int i = 0; i < _capatity; i++)
		{
			_state[i] = EMPTY;
		}
	}
	//插入数据
	bool Insert(const K& key)
	{
		//检测静态哈希表是否已满
		if (_size == _capatity)
		{
			cout << "哈希表已满!" << endl;
			return false;
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希冲突，找下一个位置
			//最后一个位置有数据，从头开始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不冲突，直接放数据
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	//查找
	int Find(const K& key)
	{
		int index = _HashFunc(key);
		while (_state[index] != EMPTY)
		{
			//找到元素
			if (_table[index] == key&&_state[index] == EXIST)
			{
				return index;
			}
			//如果算出的位置，不是要找的元素，index++;
			index++;
			//最后一个位置不是，就从头开始找
			if (index == _capatity)
			{
				index = 0;
			}
		}
		return -1;
	}
	void print()
	{
		for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				printf("[%d]EXIST:%d\n",i, _table[i]);
			}
			else if (_state[i] == DELETE)
			{
				printf("[%d]DELETE:NULL\n", i, _table[i]);
			}
			else
			{
				printf("[%d]EMPTY:NULL\n", i);
			}
		}
	}
	//删除某一位置元素
	bool Remove(const K& key)
	{
		int index = Find(key);//找到这个元素
		//删除这个元素
		if (index != -1)
		{
			_state[index] = DELETE;
			_size--;
			return true;
		}
		return false;
	}
protected:
	//算出数据在哈希表中的位置（哈希不冲突）
	int _HashFunc(const K& key)
	{
		return key%_capatity;
	}
protected:
	K* _table;//数组
	State* _state;//状态数组
	size_t _size;//数组大小
	size_t _capatity;//数组的容量
};
test.cpp中
#include <iostream>
using namespace std;
#include "Hash.h"
void Test()
{
	HashTable<int> ht(10);
	ht.Insert(24);
	ht.Insert(20);
	ht.Insert(36);
	ht.Insert(23);
	ht.Insert(30);
	ht.print();

	int ret = ht.Find(30);
	cout << "下标为："<<ret << endl;

	ht.Remove(30);
	ht.print();

}
int main()
{
	Test();
	system("pause");
	return 0;
}
上面的代码有不完善的地方，我们在处理哈希问题是，有这样的问题存在。散列表载荷因子的问题。
    载荷因子=填入表中的元/散列表的长度
   载荷因子与“填在表中元素的个数”成正比，载荷因子越大，填入表中的元素越多，产生冲突的可能性越大。反之，则相反。
    载荷因子应该限制在0.7—0.8以下，超过0.8，查找CPU缓存不命中，效率就比较低，所以一般载荷因子为0.8就应该扩容。
   所以上面的检查容量应该稍微改一下
代码：
bool Insert(const K& key)
	{
		//检测静态哈希表是否已满
		/*if (_size == _capatity)
		{
			cout << "哈希表已满!" << endl;
			return false;
		}*/
		//考虑到载荷因子在0.7~0.8一下比较好，这样检查容量比较好
		if (10 * _size >= 8 * _capatity)
		{
			_CheckCapatity();
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希冲突，找下一个位置
			//最后一个位置有数据，从头开始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不冲突，直接放数据
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	
	//交换
	void _Swap(HashTable<K> tmp)
	{
		swap(_size, tmp._size);
		swap(_capatity, tmp._capatity);
		swap(_state, tmp._state);
		swap(_table, tmp._table);
	}
	//检查容量
	void _CheckCapatity()
	{
		HashTable<K> tmp(2 * _capatity);
		for (int i = 0; i < _capatity; i++)
		{
			tmp.Insert(_table[i]);
		}
		_Swap(tmp);
	}
上面只能存储数据，如果是字符串，怎么办哪？所以我们想处理字符串，可以写一个自定义类型，然后利用特化来处理字符串。
代码如下：
#include <string>
//哈希表中存放数据的状态
enum State
{
	EMPTY,//没有数据
	DELETE,//删除数据后
	EXIST//有数据
};
template <class K>
//处理
struct DefaultFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
//自定义类型
template<>
struct DefaultFunc<string>//特化
{
	size_t value = 0;
	size_t operator()(const string& str)
	{
		for (int i = 0; i < str.size(); i++)
		{
			value += str[i];
		}
		return value;
	}
};
template <class K, template <class>class HashFunc = DefaultFunc>
class HashTable
{
public:
	//构造函数
	HashTable()
		:_table(NULL)
		, state(NULL)
		, _size(0)
		, _capatity(0)
	{}
	//构造函数
	HashTable(size_t size)
		:_table(new K[size])
		, _state(new State[size])
		, _capatity(size)
		, _size(0)
	{
		for (int i = 0; i < _capatity; i++)
		{
			_state[i] = EMPTY;
		}
	}
	//插入数据
	bool Insert(const K& key)
	{
		//检测静态哈希表是否已满
		/*if (_size == _capatity)
		{
			cout << "哈希表已满!" << endl;
			return false;
		}*/
		//考虑到载荷因子在0.7~0.8一下比较好，这样检查容量比较好
		if (10 * _size >= 8 * _capatity)
		{
			_CheckCapatity();
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希冲突，找下一个位置
			//最后一个位置有数据，从头开始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不冲突，直接放数据
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	//查找
	int Find(const K& key)
	{
		int index = _HashFunc(key);
		while (_state[index] != EMPTY)
		{
			//找到元素
			if (_table[index] == key&&_state[index] == EXIST)
			{
				return index;
			}
			//如果算出的位置，不是要找的元素，index++;
			index++;
			//最后一个位置不是，就从头开始找
			if (index == _capatity)
			{
				index = 0;
			}
		}
		return -1;
	}
	void print()
	{
		/*for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				printf("[%d]EXIST:%d\n",i, _table[i]);
			}
			else if (_state[i] == DELETE)
			{
				printf("[%d]DELETE:NULL\n", i, _table[i]);
			}
			else
			{
				printf("[%d]EMPTY:NULL\n", i);
			}
		}*/
		for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				cout << i <<"-"<< "EXIST:" << _table[i] << endl;
			}
			else if (_state[i] == DELETE)
			{
				cout << i <<"-"<< "DELETE:" << "NULL" << endl;
			}
			else
			{
				cout << i <<"-"<< "EMPTY:" << "NULL" << endl;
			}
		}
	}
	//删除某一位置元素
	bool Remove(const K& key)
	{
		int index = Find(key);//找到这个元素
		//删除这个元素
		if (index != -1)
		{
			_state[index] = DELETE;
			_size--;
			return true;
		}
		return false;
	}
protected:
	//算出数据在哈希表中的位置（哈希不冲突）
	/*int _HashFunc(const K& key)
	{
		return key%_capatity;
	}*/
	int _HashFunc(const K& key)
	{
		HashFunc<K> ht;
		return ht(key) % _capatity;
	}
	//交换
	void _Swap(HashTable<K> tmp)
	{
		swap(_size, tmp._size);
		swap(_capatity, tmp._capatity);
		swap(_state, tmp._state);
		swap(_table, tmp._table);
	}
	//检查容量
	void _CheckCapatity()
	{
		HashTable<K> tmp(2 * _capatity);
		for (int i = 0; i < _capatity; i++)
		{
			tmp.Insert(_table[i]);
		}
		_Swap(tmp);
	}
protected:
	K* _table;//数组
	State* _state;//状态数组
	size_t _size;//数组大小
	size_t _capatity;//数组的容量
};
test.cpp中
#include <iostream>
using namespace std;
#include "Hash.h"
//void Test()
//{
//	HashTable<int> ht(10);
//	ht.Insert(24);
//	ht.Insert(20);
//	ht.Insert(36);
//	ht.Insert(23);
//	ht.Insert(30);
//	ht.print();
//
//	int ret = ht.Find(30);
//	cout << "下标为："<<ret << endl;
//
//	ht.Remove(30);
//	ht.print();
//
//}

void Test1()
{
	HashTable<string> ht(10);
	ht.Insert("杭哥");
	ht.Insert("张哥");
	ht.Insert("詹姐");
	ht.Insert("亮哥");
	ht.Insert("蛋蛋");
	ht.print();

	int ret = ht.Find("蛋蛋");
	cout << "下标为：" << ret << endl;

	ht.Remove("亮哥");
	ht.print();
}
int main()
{
	//Test();
	Test1();
	system("pause");
	return 0;
}


				
转载于:https://blog.51cto.com/mnt3918290/1771958

#include<iostream>
#define HashLength 23
using namespace std;
//哈希函数
int HashFuc(int i,int length)
{
	return i%length;
}
//线性探测再散列
int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表、哈希表长度
{
	for (int i = 0; i < m; i++)
		h[i] = NULL;
	for (int j = 0; j < k; j++)
	{
		int loc = HashFuc(A[j], HashLength);
		while (h[loc])
		{
			loc=loc++%m;	//寻找第一个空位置
		}
		h[loc] = A[j];
	}
	return h;
}

int main()
{
	int Hash[25];//哈希表
	int Key[20] = { 23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91 };	//关键字
	HashReLineExplor(Key, 20, Hash, 25);
	for (int i = 0; i < 25; i++)
	{
		if (Hash[i])
		{
			printf("第%2d个元素是:%4d\n", i, Hash[i]);
		}
	}
	return 0;
}
数组中元素： 23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91 


哈希表中元素：
第 0个元素是:  23

第 1个元素是:  24

第 2个元素是:  93

第 3个元素是:  26

第 4个元素是:  23

第 5个元素是: 120

第 6个元素是:  29

第 7个元素是:  94

第 8个元素是: 123

第 9个元素是:  32

第10个元素是:  93

第11个元素是:  11

第12个元素是:  92

第14个元素是:  14

第15个元素是:  38

第16个元素是:  83

第20个元素是:  43

第21个元素是:  21

第22个元素是:  22

第23个元素是:  91

请按任意键继续. . .

哈希表线性探测再散列的方法详解

例：设哈希表长为m=14，散列函数为H(k)=k mod 11，关键字序列为5，7，16，12，11，21，31，51，17，81；试求：散列后的表中关键字分布（假定解决冲突的方法为线性探测再散列法）
解题步骤：

（1）将关键字序列中的每一个数除以散列函数中的11并取余数。



（2）将关键字对照余数，放入哈希表中。



（3）因为在关键字序列中16排在51前，所以我们先处理关键字16的冲突，也就是先解决关键字16到底应该放在哪一个哈希表值的位置。

（4）关键字16除以11取余数为5，哈希表值为5处已经被关键字5占用，关键字5在关键字序列中排在16的前面，所以，关键字16只能向后移动一位放在哈希表值为6处，但是此时哈希表6的位置处放的是关键字17，我们查看关键字序列可以发现，关键字16在序列中是排在17的前面，所以，可以将16放在哈希表值为6处。此时，17变为冲突的关键字。



（5）此时冲突关键字为17和51，对照关键字序列，关键字51的位置排在关键字17之前，所以我们先处理关键字51的冲突。

（6）关键字51与关键字7冲突，查看关键字序列，关键字7排在关键字51的前面，所以关键字需向后移动一位，在哈希表值8处存储，查看哈希表，值为8处没有其他关键字占用，将关键字51放入8处。


（7）此时只有关键字17处于冲突状态。哈希表值为7、8、9、10处关键字为7、51、31、21，查看关键字序列发现关键字7、51、31、21均排在17的前面，所以关键字17只能放在此时为空的哈希表值11处。


仅仅只是为了考试，我太难了。。。｡°(°¯᷄◠¯᷅°)°｡

在代码中实现了哈希表中任意类型都可以存放，即哈希函数要可扩展以及哈希表动态增容的功能。
贴上代码：
#include<iostream>
#include<vector>
using namespace std;

template<class K>//特化
 class _HashFun
 {
 public:
	 size_t operator()(K key)
	 {
		 return key;
	 }
 };

 template<>
 class _HashFun<string>
 {
 public:
	 size_t operator()(const char* str)
	 {
		 return BKDRHash(str);
	 }
 private:
	 static size_t BKDRHash(const char * str)
  {	
	unsigned int seed = 131; // 31 131 1313 13131 131313	
	unsigned int hash = 0;
	while (*str )
	{
		hash = hash * seed + (*str++);
	}
	return (hash & 0x7FFFFFFF);
  }
 };

enum State //状态标志
{
	EXIST,
	EMPTY,
	DELETE,
};

template<class K, class V>
struct HashElem //哈希元素
{
	HashElem()
		:_s(EMPTY)
	{}
	pair<K, V> _kv;
	State _s;
};

template<class K, class V, class HashFunc = _HashFun<K>, bool Isline = true>
class HashTable //哈希表
{
public:
	HashTable(size_t size = 12)
		:_size(0)
	{
		_table.resize(size);
	}

	bool Insert(const K& key, const V& value)
	{
		_CheckTable();
		//如果表满
		if(_size == _table.size())
			return false;

        size_t hashAddr = _HashFunc(key);//找哈希地址
		size_t H0 = hashAddr;
		size_t i = 1;
 		while(EXIST == _table[hashAddr]._s)//冲突
		{
			if(key == _table[hashAddr]._kv.first)//只插入唯一值
				return false;

			if(Isline)
			{
				hashAddr =  HashFunc1(H0);
			}
			else
			{
				hashAddr =  HashFunc2(H0, i);
			}
			i++;

		    //hashAddr++;//线性探测
			//if(hashAddr == _table.size())//找到最后一个再从头开始
			//	hashAddr = 0;
		}
		//插入
		_table[hashAddr]._kv.first = key;
		_table[hashAddr]._kv.second = value;
		_table[hashAddr]._s = EXIST;
		_size++;
		return true;

	}
	pair<HashElem<K,V>*, bool> Find(const K& key)//查找值为key的元素
	{
		size_t hashAddr = _HashFunc(key);
	    size_t H0 = hashAddr;
		size_t i = 1;
		while(EMPTY != _table[hashAddr]._s)
		{
			if(_table[hashAddr]._kv.first == key)
			{
				if(_table[hashAddr]._s == EXIST)
					return make_pair(&_table[hashAddr], true);
				else//DELETE
					return make_pair((HashElem<K, V>*)NULL, false);//这里需要强转，否则编译器可能将NULL当成0
			}
			if(Isline)
			{
				hashAddr =  HashFunc1(H0);
			}
			else
			{
				hashAddr =  HashFunc2(H0, i);
			}
			i++;
			//hashAddr++;//线性探测
			//if(hashAddr == _table.size())
			//	hashAddr = 0;
		}
		return make_pair((HashElem<K,V>*)NULL,false);
	}

	bool Remove(const K& key)//删除
	{
		pair<HashElem<K, V>*, bool> pos = Find(key);
		if(pos.second)
		{
			pos.first->_s = DELETE;
			_size--;
			return true;
		}
		return false;
	}

private:
	size_t _HashFunc(const K& key)
	{
		return HashFunc()(key) % 10/*_table.size()-1*/;
	}

	// 线性探测处理函数
	size_t HashFunc1(size_t hashAddr)
	{
		hashAddr++;
		if(hashAddr == _table.size())
			hashAddr = 0;
		return hashAddr;
	}

	// 二次探测处理函数
	size_t HashFunc2(size_t hashAddr, size_t i)
	{
		if(hashAddr >= _table.size())
			hashAddr = 0;
		return hashAddr+2*i+1;
	}

	void Swap(HashTable<K,V>& ht)
	{
		_table.swap(ht._table);//两个容器交换不创建临时对象 
		swap(_size, ht._size);
	}
	void _CheckTable()
	{
		if(_size*10 / _table.size() >= 7)
		{
			size_t newsize = _table.size()*2;//乘2可能会越界
			//newsize = GetNextPrime(newsize);
			//交换法 销毁原来的空间
			HashTable<K, V> ht(newsize);
			for(int idx = 0;idx <= _table.size();idx++)
			{
				if(_table[idx]._s == EXIST)
					ht.Insert(_table[idx]._kv.first, _table[idx]._kv.second);
			}
			Swap(ht);
		}
	}

	vector<HashElem<K, V>> _table;
	size_t _size;//有效元素的个数
};

void FunTest()
{
	int a[] = {11,25,37,14,36,49,57};
	HashTable<int, int> ht;
	for(int idx = 0; idx <sizeof(a)/sizeof(a[0]); idx++)
		ht.Insert(a[idx], idx);

	pair<HashElem<int, int>*, bool> pos = ht.Find(25);
	if(pos.second)
	{
		cout<<pos.first->_kv.first<<endl;
	}
	else
	{
		cout<<"没有找到该元素"<<endl;
	}

	ht.Remove(25);

	pair<HashElem<int, int>*, bool> pos1 = ht.Find(25);
	if(pos1.second)
	{
		cout<<pos1.first->_kv.first<<endl;
	}
	else
	{
		cout<<"没有找到该元素"<<endl;
	}

}