處理哈希沖突的閉散列方法-線性探測

 說到哈希沖突，就必須談到哈希函數了。

• 什么時候哈希函數

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

• 什么是哈希沖突

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

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

• 線性探測

  如下圖所示

  在上圖中，這里key取8。

實現線性探測代碼：
#pragma once
#include<string>
enum Status
{
	EXIST,
	EMPTY,
	DELETE,
};
//如果是數據類型，直接返回數據，定位位置
template<class T>
struct DataType
{
	long long operator()(const T&key)
	{
		return key;
	}
};
//如果是字符串類型，求出字符串ASCII和，根據求出的和定位位置
template<class T>
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 T,template<class T> class HashFuncer=DataType>
//class HashFuncer = DataType<T>
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<T,HashFuncer>&ht)
	{
		HashTable<T,HashFuncer> 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<T, HashFuncer>& operator=(const HashTable<T, HashFuncer> &ht)
	{
		if (_tables != ht._tables)
		{
			HashTable<T, HashFuncer> ht1(ht);
			/*HashTable<T, HashFuncer> 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<T,HashFuncer> 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<T,HashFuncer> &ht)
	{
		swap(_tables, ht._tables);
		swap(_status, ht._status);
		swap(_size, ht._size);
		swap(_capacity, ht._capacity);
	}
	size_t _HashFunc(const T&key)
	{
		HashFuncer<T> hf;
		return hf(key)%_capacity;
	}
protected:
	T *_tables;
	Status *_status;
	size_t _size;
	size_t _capacity;
};