哈希表/散列表

哈希表/散列表，是根据关键字（key）直接访问在内存存储位置的数据结构。

创新互联公司是一家专业提供松北企业网站建设,专注与网站设计制作、网站设计、H5响应式网站、小程序制作等业务。10年已为松北众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。

构造哈希表的常用方法：

1. 直接地址法---取关键字的某个线性函数为散列地址，Hash(Key) = Key或Hash(key) = A*Key + B,

   A,B为常数。

2. 除留余数法---取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。

   Hash(key) = key % p。

   若采用直接地址法（Hash(Key) = Key）存在一定的缺陷。

   当Key值特别大时，而Key之前的数很少，就会造成空间浪费。大多时候采取除留余数法。

   哈希冲突/哈希碰撞

   不同的Key值经过哈希函数Hash(Key)处理以后可能产生相同的哈希地址，我们称这种情况为哈希冲突。任何的散列函数都不能避免产生冲突。

  散列表的载荷因子定义为a = 填入表中元素的个数/散列表的长度

  载荷因子越大，冲突的可能性就越大。

  解决冲突的办法：

 （1）线性探测           

 （2）二次探测

#pragma once
#include 
#include 
using namespace std;

enum State
{
	EMPTY,
	DELETE,
	EXITS,
};
//以key形式实现线性探测
template 
class HashTable
{
public:
	HashTable(T capacity = 10)
		:_tables(new T[capacity])
		,_states(new State[capacity])
		,_capacity(capacity)
		,_size(0)
	{
		for(size_t i=0;i < _capacity;++i)
		{
			_states[i] = EMPTY;
		}
	}

	~HashTable()
	{
		delete[] _tables;
		delete[] _states;
		_tables = NULL;
		_states = NULL;
	}

	HashTable(const HashTable& ht) //拷贝构造
	{
		_tables = new T[ht._capacity];
		_states = new State[ht._capacity];
		for(size_t i=0;i& operator=(const HashTable& ht)  //赋值操作符重载
	//{
	//	if(this != &ht)
	//	{
	//		delete[] _tables;
	//		delete[] _states;
	//		_tables = new T[ht._capacity];
	//		_states = new State[ht._capacity];
	//		for(size_t i=0;i& operator=(HashTable ht)  //赋值操作符重载
	{
		this->Swap(ht);
		return *this;
	}

public:
	bool Insert(const T& key) //插入
	{
		_CheckCapacity();
		size_t index = HashFunc(key);
		while(_states[index] == EXITS) 
		{
			if(_tables[index] == key)  //冗余
			{
				return false;
			}
			++index;
			if(index == _capacity)  //到达哈希表尾部
			{
				index = 0;
			}
		}
		_tables[index] = key;
		_states[index] = EXITS;
		++_size;
		return true;
	}
	bool Find(const T& key)  //查找
	{
		size_t index = HashFunc(key);
        size_t start = index;
		while(_states[index] == EXITS)
		{
			if(_tables[index] == key)  
			{
				return true;
			}
			++index;
			if(index == _capacity)
			{
				index = 0;
			}
            if(start == index)   //哈希表查完
            {
               return false;
            }
		}
		return false;
	}
	bool Remove(const T& key)  //删除
	{
		size_t index = HashFunc(key);
		size_t start = index;
		while(_states[index] == EXITS)
		{
			if(_tables[index] == key)
			{
				_states[index] = DELETE;
				return true;
			}
			++index;
			if(index == _capacity)  //到达哈希表的尾部
			{
				index = 0;
			}
            if(start == index)  //哈希表查完
            {
               return false;
            }
		}
		return false;
	}
public:
	size_t HashFunc(const T& key)  //哈希函数
	{
		return key%10;
	}

	void _CheckCapacity()  //检查容量
	{
		if(_size*10 % _capacity == 7)  //载荷因子
		{
			HashTable tmp(2*_capacity);
			for(size_t i=0;i<_capacity;++i)
			{
				if(_states[i] == EXITS)
				{
					tmp.Insert(_tables[i]);
				}
			}
			Swap(tmp);
		}	
	}
	
	void Swap(HashTable& ht)
	{
		swap(_tables,ht._tables);
		swap(_states,ht._states);
		swap(_size,ht._size);
		swap(_capacity,ht._capacity);
	}

	void Print()
	{
		for(size_t i=0;i<_capacity;++i)
		{
			cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
		}
		cout<
//class HashTableSecond
//{
//public:
//	HashTableSecond(T capacity = 10)
//		:_tables(new T[capacity])
//		,_states(new State[capacity])
//		,_capacity(capacity)
//		,_size(0)
//	{
//		for(size_t i=0;i < _capacity;++i)
//		{
//			_states[i] = EMPTY;
//		}
//	}
//
//	~HashTableSecond()
//	{
//		delete[] _tables;
//		delete[] _states;
//		_tables = NULL;
//		_states = NULL;
//	}
//
//	HashTableSecond(const HashTableSecond& ht) //拷贝构造
//	{
//		_tables = new T[ht._capacity];
//		_states = new State[ht._capacity];
//		for(size_t i=0;i tmp(2*_capacity);
//			for(size_t i=0;i<_capacity;++i)
//			{
//				if(_states[i] == EXITS)
//				{
//					tmp.Insert(_tables[i]);
//				}
//			}
//			Swap(tmp);
//		}	
//	}
//	
//	void Swap(HashTableSecond& ht)
//	{
//		swap(_tables,ht._tables);
//		swap(_states,ht._states);
//		swap(_size,ht._size);
//		swap(_capacity,ht._capacity);
//	}
//
//	void Print()
//	{
//		for(size_t i=0;i<_capacity;++i)
//		{
//			cout<<"["<<_states[i]<<","<<_tables[i]<<"]"<<" ";
//		}
//		cout<
struct HashTableNode //节点
{
	T key;
	K value;
};
template 
struct __HashFunc    //重载()
{
	size_t operator()(const T& key)
	{
		return key;
	}
};

template<>
struct __HashFunc   //特化
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for(size_t i=0;i >
class HashTableSecond
{
public:
	HashTableSecond(size_t capacity = 10)
		:_tables(new HashTableNode[capacity])
		,_states(new State[capacity])
		,_capacity(capacity)
		,_size(0)
	{
		for(size_t i=0;i < _capacity;++i)
		{
			_states[i] = EMPTY;
		}
	}
	~HashTableSecond()
	{
		delete[] _tables;
		delete[] _states;
		_tables = NULL;
		_states = NULL;
	}

public:
	bool Insert(const T& key,const K& value)  //插入
	{
		_CheckCapacity();
		size_t start = __HashFunc(key);
		size_t index = start;
		size_t i = 1;
		while(_states[index] == EXITS)  
		{
			if(_tables[index].key == key)
			{
				return false;
			}
			index = start + i * i;
			++i;
			index %= _capacity;
		}
		_tables[index].key = key;
		_tables[index].value = value;
		_states[index] = EXITS;
		++_size;
		return true;
	}
	HashTableNode* Find(const T& key)  //查找
	{
		size_t start = __HashFunc(key);
		size_t index = start;
		size_t i = 1;
		while(_states[index] == EXITS)
		{
			if(_tables[index].key == key)
			{
				return &(_tables[index]);
			}
			index = start + i * i;
			++i;
			index %= _capacity;
		}
		return NULL;
	}

	bool Remove(const T& key)  //删除
	{
		size_t start = __HashFunc(key);
		size_t index = start;
		size_t i = 1;
		while(_states[index] == EXITS)
		{
			if(_tables[index].key == key)
			{
				_states[index] = DELETE;
				return true;
			}
			index = start + i * i;
			++i;
		}
		return false;
	}
public:
	size_t __HashFunc(const T& key)  //哈希函数
	{
		HashFunc hfun;
		return hfun(key)%_capacity;
	}
 
	void _CheckCapacity()  //检测容量
	{
		if(_size*10 % _capacity == 7)
		{
			HashTableSecond tmp(2*_capacity);
			for(size_t i=0;i<_capacity;++i)
			{
				if(_states[i] == EXITS)
				{
					tmp.Insert(_tables[i].key,_tables[i].value);
				}
			}
			Swap(tmp);
		}	
	}
	
	void Swap(HashTableSecond& ht)
	{
		swap(_tables,ht._tables);
		swap(_states,ht._states);
		swap(_size,ht._size);
		swap(_capacity,ht._capacity);
	}

	void Print()
	{
		for(size_t i=0;i<_capacity;++i)
		{
			cout<<"["<<_tables[i].key<<","<<_tables[i].value<<"]"<<" ";
		}
		cout<* _tables; //哈希表
	State* _states; //状态表
	size_t _size; //数据的个数
	size_t _capacity; //容量
};