哈希表/散列表-创新互联

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

构造哈希表的常用方法：

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; //容量
};

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。