說到哈希沖突，就必須談到哈希函數(shù)了。

碾子山網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,碾子山網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為碾子山成百上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的碾子山做網(wǎng)站的公司定做！

• 什么時候哈希函數(shù)

        哈希沖突函數(shù)hv(i)，用于在元素i發(fā)生哈希沖突時，將其映射至另一個內(nèi)存位置。

• 什么是哈希沖突

       哈希沖突即關(guān)鍵字不同的元素被映射到了同一個內(nèi)存位置，包括由同義詞沖突和非同義詞沖突。

 處理哈希沖突的方法很多，這里淺談一下處理哈希沖突的閉散列方法：

• 線性探測

  如下圖所示

  在上圖中，這里key取8。

實現(xiàn)線性探測代碼：
#pragma once
#include
enum Status
{
	EXIST,
	EMPTY,
	DELETE,
};
//如果是數(shù)據(jù)類型，直接返回數(shù)據(jù)，定位位置
template
struct DataType
{
	long long operator()(const T&key)
	{
		return key;
	}
};
//如果是字符串類型，求出字符串ASCII和，根據(jù)求出的和定位位置
template
struct StringType
{
	long long operator()(const string&key)
	{
		long long size = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			size = size + key[i];
		}
		return size;
	}

};
//定義的哈希類
template class HashFuncer=DataType>
//class HashFuncer = DataType
class HashTable
{
public:
	HashTable()
		:_tables(NULL)
		, _status(NULL)
		, _size(0)
		, _capacity(0)
	{}
	HashTable(const size_t size)
		:_tables(new T[size])
		, _status(new Status[size])
		, _size(0)
		, _capacity(size)
	{
		for (size_t i = 0; i < size; i++)
		{
			_status[i] = EMPTY;
		}
	}
	HashTable(const HashTable&ht)
	{
		HashTable tmp(ht._capacity);
		for (size_t i = 0; i < ht._capacity; i++)
		{
			if (ht._status[i] != EMPTY)
			{
				tmp._status[i] = ht._status[i];
				tmp._tables[i] = ht._tables[i];
			}
		}
		tmp._size = ht._size;
		tmp._capacity = ht._capacity;
		this->Swap(tmp);
	}
	~HashTable()
	{
		if (_tables)
		{
			delete[] _tables;
			delete[] _status;
		}
		_size = 0;
		_capacity = 0;
	}
	HashTable& operator=(const HashTable &ht)
	{
		if (_tables != ht._tables)
		{
			HashTable ht1(ht);
			/*HashTable ht1(ht._capacity);
			for (size_t i = 0; i < ht._capacity; i++)
			{
				if (ht._status[i] != EMPTY)
				{
					ht1._tables[i] = ht._tables[i];
					ht1._status[i] = ht._status[i];
				}
			}
			ht1._size = ht._size;*/
			this->Swap(ht1);
		}
		return *this;
	}
	bool Insert(const T&key)
	{
		_CheckCapacity();
		size_t index = _HashFunc(key);
		while (_status[index] == EXIST)
		{
			if (_tables[index] == key)
			{
				return false;
			}
			++index;
			if (index == _capacity)
			{
				index = 0;
			}
		}
		_status[index] = EXIST;
		_tables[index] = key;
		_size++;
		return true;
	}
	size_t Find(const T&key)
	{
		size_t index = _HashFunc(key);
		while (_status[index] != EMPTY)
		{
			if (_tables[index] == key&&_status[index] != DELETE)
			{
				return index;
			}
			++index;
			if (index == _capacity)
			{
				index = 0;
			}
		}
		return -1;
	}
	bool Remove(const T&key)
	{
		int index = Find(key);
		if (index != -1)
		{
			_status[index] = DELETE;
			return true;
		}
		return false;
	}
	void _CheckCapacity()//載荷因子
	{
		if (_size * 10 >= _capacity * 7)
		{
			HashTable tmp(2 * _capacity+3);
			for (size_t i = 0; i < _capacity; ++i)
			{
				if (_status[i] != EMPTY)
				{
					tmp.Insert(_tables[i]);
				}
			}
			this->Swap(tmp);
		}
	}
	void PrintTables()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (_status[i] == EXIST)
			{
				printf("[%d]:E->", i);
				cout << _tables[i];
			}
			else if (_status[i] == DELETE)
			{
				printf("[%d]:D->", i);
				cout << _tables[i];
			}
			else if (_status[i] == EMPTY)
			{
				printf("[%d]:N->NONE", i);
			}
			cout << endl;
		}
		cout << endl;
	}
	void Swap(HashTable &ht)
	{
		swap(_tables, ht._tables);
		swap(_status, ht._status);
		swap(_size, ht._size);
		swap(_capacity, ht._capacity);
	}
	size_t _HashFunc(const T&key)
	{
		HashFuncer hf;
		return hf(key)%_capacity;
	}
protected:
	T *_tables;
	Status *_status;
	size_t _size;
	size_t _capacity;
};