【数据结构】哈希表

发布时间：2020-12-15 05:56:43 所属栏目：安全来源：网络整理

导读：HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。构造哈希表的几种方法 1. 直接定址法--取关键字

HashTable-散列表/哈希表，是根据关键字（key）而直接访问在内存存储位置的数据结构。
它通过一个关键值的函数将所需的数据映射到表中的位置来访问数据，这个映射函数叫做散列函数，存放记录的数组叫做散列表。
构造哈希表的几种方法
1. 直接定址法--取关键字的某个线性函数为散列地址，Hash（Key）= Key 或 Hash（Key）= A*Key + B，A、B为常数。
2. 除留余数法--取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址。Hash（Key）= Key % P。
3. 平方取中法
4. 折叠法
5. 随机数法

6. 数学分析法

这里实现除留余数法构造的哈希表

除留余数函数

size_t _HashFunc(const K& key)
	{
		return key%_table.size();
	}

实现哈希表、

#include<iostream>
#include <cstdlib>
#include <vector>
using namespace std;
enum Status
{
	EMPTY,EXIST,DELETE,};
template<class K,class V>
struct HashTableNode
{
	K _key;
	V _value;
	Status _status;
	HashTableNode(const K& key=K(),const V& value=V())
		:_key(key),_value(value),_status(EMPTY)
	{}
};
template<class K,class V>
class HashTable
{
	typedef HashTableNode<K,V> Node;
public:
	HashTable()
		:_size(0)
	{
		_table.resize(_GetNextPrime(0));
	}
	~HashTable()
	{}
	bool Insert(const K& key,const V& value)
	{
		Checksize();
		size_t index=_HashFunc(key);
		while (_table[index]._status==EXIST)
		{
			if(_table[index]._key==key)
				return false;
			++index;
			if(index==_table.size())
				index=0;
		}
		_table[index]._key=key;
		_table[index]._value=value;
		_table[index]._status=EXIST;
		_size++;
		return true;
	}
	Node* Find(const K& key)
	{
		if(_table.empty())
		{
			return NULL;
		}
		for (size_t i=0;i<_table.size();i++)
		{
			if(_table[i]._status==EXIST&&_table[i]._key==key)
				return &_table[i];
			else
				continue;
		}
		return NULL;
	}
	bool Remove(const K& key)
	{
		if (_table.empty())
		{
			return false;
		}
		Node* del=Find(key);
		if(del->_status==EXIST)
		{
			del->_status=DELETE;
			return true;
		}
		else
			return false;
	}
	void display()
	{
		if(_table.size()==0)
		{
			return;
		}
		for (size_t i=0;i<_table.size();i++)
		{
			cout<<" key:"<<_table[i]._key<<" value:"<<_table[i]._value<<" status:"<<_table[i]._status<<endl;
		}
		cout<<endl;
	}
protected:
	size_t _HashFunc(const K& key)
	{
		return key%_table.size();
	}
	void Checksize()
	{
		if(_table.size()==0||_size*10/_table.size()>=8)
		{
			size_t newsize=_GetNextPrime(_table.size());
			HashTable hash;
			hash._table.resize(newsize);
			for (size_t i=0;i<_table.size();i++)
			{
				if(_table[i]._status==EXIST)
				{
					hash.Insert(_table[i]._key,_table[i]._value);
				}
			}
			this->Swap(hash);
		}
	}
	size_t _GetNextPrime(size_t num)
	{
		const int _PrimeSize=28;
		static const unsigned long _PrimeList[_PrimeSize]=
		{
			53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,1996613ul,391241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,429496729ul
		};
		for (size_t i=0;i<_PrimeSize;i++)
		{
			if(_PrimeList[i]>num)
				return _PrimeList[i];
		}
		return 429496729ul;
	}
	void Swap(HashTable<K,V>& hs)
	{
		_table.swap(hs._table);
		swap(_size,hs._size);
	}
protected:
	vector<Node> _table;
	size_t _size;
};
void testHash()
{
	HashTable<int,int> hash;
	for (size_t i=0;i<20;i++)
	{
		hash.Insert(i,i);
	}
	for (size_t i=10;i<30;i++)
	{
		hash.Insert(i,i);
	}
	hash.display();
	hash.Remove(3);
	hash.Remove(7);
	hash.display();
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!