哈希表/散列表-創(chuàng)新互聯(lián)

哈希表/散列表，是根據(jù)關(guān)鍵字（key）直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。

站在用戶的角度思考問題，與客戶深入溝通，找到武川網(wǎng)站設(shè)計(jì)與武川網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名注冊(cè)、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋武川地區(qū)。

構(gòu)造哈希表的常用方法：

  1. 直接地址法---取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址，Hash(Key) = Key或Hash(key) = A*Key + B,

    A,B為常數(shù)。

  2. 除留余數(shù)法---取關(guān)鍵值被某個(gè)不大于散列表長m的數(shù)p除后的所得的余數(shù)為散列地址。

    Hash(key) = key % p。

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

  當(dāng)Key值特別大時(shí)，而Key之前的數(shù)很少，就會(huì)造成空間浪費(fèi)。大多時(shí)候采取除留余數(shù)法。

  哈希沖突/哈希碰撞

  不同的Key值經(jīng)過哈希函數(shù)Hash(Key)處理以后可能產(chǎn)生相同的哈希地址，我們稱這種情況為哈希沖突。任何的散列函數(shù)都不能避免產(chǎn)生沖突。

 散列表的載荷因子定義為a = 填入表中元素的個(gè)數(shù)/散列表的長度

 載荷因子越大，沖突的可能性就越大。

 解決沖突的辦法：

 （1）線性探測(cè)

哈希表/散列表

 （2）二次探測(cè)

哈希表/散列表

#pragma once
#include <iostream>
#include <string>
using namespace std;

enum State
{
	EMPTY,
	DELETE,
	EXITS,
};
//以key形式實(shí)現(xiàn)線性探測(cè)
template <class T>
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<T>& ht) //拷貝構(gòu)造
	{
		_tables = new T[ht._capacity];
		_states = new State[ht._capacity];
		for(size_t i=0;i<ht._capacity;++i)
		{
			if(ht._tables[i] != EMPTY)
			{
				_tables[i] = ht._tables[i];
				_states[i] = ht._states[i];
			}		
		}
		_capacity = ht._capacity;
		_size = ht._size;
	}

	//HashTable<T>& operator=(const HashTable<T>& ht)  //賦值操作符重載
	//{
	//	if(this != &ht)
	//	{
	//		delete[] _tables;
	//		delete[] _states;
	//		_tables = new T[ht._capacity];
	//		_states = new State[ht._capacity];
	//		for(size_t i=0;i<ht._capacity;++i)
	//		{
	//			if(ht._tables[i] != EMPTY)
	//			{
	//				_tables[i] = ht._tables[i];
	//				_states[i] = ht._states[i];
	//			}		
	//		}
	//		_capacity = ht._capacity;
	//		_size = ht._size;
	//	}
	//	return *this;
	//}


	//現(xiàn)代寫法
	HashTable<T>& operator=(HashTable<T> 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)  //到達(dá)哈希表尾部
			{
				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)  //到達(dá)哈希表的尾部
			{
				index = 0;
			}
            if(start == index)  //哈希表查完
            {
               return false;
            }
		}
		return false;
	}
public:
	size_t HashFunc(const T& key)  //哈希函數(shù)
	{
		return key%10;
	}

	void _CheckCapacity()  //檢查容量
	{
		if(_size*10 % _capacity == 7)  //載荷因子
		{
			HashTable<T> tmp(2*_capacity);
			for(size_t i=0;i<_capacity;++i)
			{
				if(_states[i] == EXITS)
				{
					tmp.Insert(_tables[i]);
				}
			}
			Swap(tmp);
		}	
	}
	
	void Swap(HashTable<T>& 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<<endl;
	}
private:
	T* _tables; //哈希表
	State* _states; //狀態(tài)表
	size_t _size; //數(shù)據(jù)的個(gè)數(shù)
	size_t _capacity; //容量
};


//以key形式實(shí)現(xiàn)二次探測(cè)
//enum State
//{
//	EMPTY,
//	DELETE,
//	EXITS,
//};
//template <class T>
//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) //拷貝構(gòu)造
//	{
//		_tables = new T[ht._capacity];
//		_states = new State[ht._capacity];
//		for(size_t i=0;i<ht._capacity;++i)
//		{
//			if(ht._tables[i] != EMPTY)
//			{
//				_tables[i] = ht._tables[i];
//				_states[i] = ht._states[i];
//			}		
//		}
//		_capacity = ht._capacity;
//		_size = ht._size;
//	}
//
//	HashTableSecond& operator=(const HashTableSecond& ht)  //賦值操作符重載
//	{
//		if(this != &ht)
//		{
//			delete[] _tables;
//			delete[] _states;
//			_tables = new T[ht._capacity];
//			_states = new State[ht._capacity];
//			for(size_t i=0;i<ht._capacity;++i)
//			{
//				if(ht._tables[i] != EMPTY)
//				{
//					_tables[i] = ht._tables[i];
//					_states[i] = ht._states[i];
//				}		
//			}
//			_capacity = ht._capacity;
//			_size = ht._size;
//		}
//		return *this;
//	}
//
//public:
//	bool Insert(const T& key) //插入
//	{
//		_CheckCapacity();
//		size_t start = HashFunc(key);
//		size_t index = start;
//		size_t i = 1;
//		while(_states[index] == EXITS)  
//		{
//			if(_tables[index] == key)
//			{
//				return false;
//			}
//			index = start + i * i;
//			++i;
//			index %= _capacity;
//		}
//		_tables[index] = key;
//		_states[index] = EXITS;
//		++_size;
//		return true;
//	}
//	bool 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)
//			{
//				return true;
//			}
//			index = start + i * i;
//			++i;
//			index %= _capacity;
//		}
//		return false;
//	}
//	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)
//			{
//				_states[index] = DELETE;
//				return true;
//			}
//			index = start + i * i;
//			++i;
//			index %= _capacity;
//		}
//		return false;
//	}
//public:
//	size_t HashFunc(const T& key)  //哈希函數(shù)
//	{
//		return key%10;
//	}
//
//	void _CheckCapacity()  //檢測(cè)容量
//	{
//		if(_size*10 % _capacity == 7)
//		{
//			HashTableSecond<T> tmp(2*_capacity);
//			for(size_t i=0;i<_capacity;++i)
//			{
//				if(_states[i] == EXITS)
//				{
//					tmp.Insert(_tables[i]);
//				}
//			}
//			Swap(tmp);
//		}	
//	}
//	
//	void Swap(HashTableSecond<T>& 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<<endl;
//	}
//private:
//	T* _tables; //哈希表
//	State* _states; //狀態(tài)表
//	size_t _size; //數(shù)據(jù)的個(gè)數(shù)
//	size_t _capacity; //容量
//};


//以key/value形式實(shí)現(xiàn)二次探測(cè)，支持字典查詢
//enum State
//{
//	EMPTY,
//	DELETE,
//	EXITS,
//};

template <class T,class K>
struct HashTableNode //節(jié)點(diǎn)
{
	T key;
	K value;
};
template <class T>
struct __HashFunc    //重載()
{
	size_t operator()(const T& key)
	{
		return key;
	}
};

template<>
struct __HashFunc<string>   //特化
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for(size_t i=0;i<key.size();++i)
		{
			hash += key[i];
		}
		return hash;
	}	
};

template <class T,class K,class HashFunc = __HashFunc<T> >
class HashTableSecond
{
public:
	HashTableSecond(size_t capacity = 10)
		:_tables(new HashTableNode<T,K>[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<T,K>* 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)  //哈希函數(shù)
	{
		HashFunc hfun;
		return hfun(key)%_capacity;
	}
 
	void _CheckCapacity()  //檢測(cè)容量
	{
		if(_size*10 % _capacity == 7)
		{
			HashTableSecond<T,K> 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<T,K>& 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<<endl;
	}
private:
	HashTableNode<T,K>* _tables; //哈希表
	State* _states; //狀態(tài)表
	size_t _size; //數(shù)據(jù)的個(gè)數(shù)
	size_t _capacity; //容量
};

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站題目：哈希表/散列表-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://muchs.cn/article34/dpphpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、響應(yīng)式網(wǎng)站、微信小程序、搜索引擎優(yōu)化、營銷型網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站建設(shè)