基于拉链法的哈希表(SeparateChainingHashST) -- C++实现


实现代码

// SeparateChainingHashST.h
// 基于拉链法的散列(hash)表
#ifndef SEPARATECHAININGHASH_H
#define SEPARATECHAININGHASH_H

#include<iostream>
using namespace std;

namespace jay{

	template<typename Key,typename Value,class HashClass>
	class SeparateChainingHashST
	{
	private:

		LinkListByKeyValue<Key,Value> *m_HashTable;
		int m_iHashTableSize;
		int m_iCountOfValue;

	public:
		void Insert( Key key,Value value);
		HashClass Get_Hash;

		Value Get( Key key);
		Value& GetReference( Key key);
		void Delete( Key key);

		bool isContain(Key key);

		int Get_Size();
		bool isEmpty( Key key);

		void Resize( int newHashTableSize);

		// 重载操作符
		Value& operator []( Key key);

		SeparateChainingHashST();
		SeparateChainingHashST(int TableSize);
		~SeparateChainingHashST();

	};

	template<typename Key,typename Value,class HashClass>
	SeparateChainingHashST<Key,Value,HashClass>::SeparateChainingHashST():
	m_iHashTableSize(50),m_iCountOfValue(0)
	{
		m_HashTable = new LinkListByKeyValue<Key,Value>[m_iHashTableSize];
	}

	template<typename Key,typename Value,class HashClass>
	SeparateChainingHashST<Key,Value,HashClass>::SeparateChainingHashST(int TableSize):
	m_iHashTableSize(TableSize),m_iCountOfValue(0)
	{
		m_HashTable = new LinkListByKeyValue<Key,Value>[m_iHashTableSize];
	}

	template<typename Key,typename Value,class HashClass>
	SeparateChainingHashST<Key,Value,HashClass>::~SeparateChainingHashST()
	{
		// 释放链表元素的空间
		for (int i = 0; i < m_iHashTableSize; i++) 
		{
			LinkListByKeyValue<Key,Value>::Node* pNode;
			for (pNode = m_HashTable[i].m_pFrist; pNode != NULL;) 
			{
				// 备份当前Node
				LinkListByKeyValue<Key,Value>::Node* tmp = pNode;
				// 指向下一个Node
				pNode = pNode->m_pNext;
				// 删除当前Node
				delete tmp;
				tmp = NULL;
			}
		}

		// 释放哈希表的空间
		delete []m_HashTable;
		m_HashTable = NULL;
	}

	template<typename Key,typename Value,class HashClass>
	void SeparateChainingHashST<Key,Value,HashClass>::Insert( Key key,Value value)
	{
		// 如果链的平均长度是哈希表大小的10倍,则增加
		// C++实现Resize非常麻烦,暂时不处理
		// 		if (m_iCountOfValue >= 2 * m_iHashTableSize) 
		// 			Resize(2 * m_iHashTableSize);

		int ihash = Get_Hash(key,m_iHashTableSize);
		if (!isContain(key)) 
			m_iCountOfValue++;

		m_HashTable[ihash].Insert(key,value);
	}

	template<typename Key,typename Value,class HashClass>
	void SeparateChainingHashST<Key,Value,HashClass>::Delete( Key key)
	{

		int ihash = Get_Hash(key,m_iHashTableSize);
		if (isContain(key)) 
			m_iCountOfValue--;
		m_HashTable[ihash].DeleteFromList(key);

	}

	template<typename Key,typename Value,class HashClass>
	typename Value& SeparateChainingHashST<Key,Value,HashClass>::operator []( Key key)
	{
		// 如果当前key不存在则以默认值的方式,添加该key
		if (!isContain(key))
		{
			Insert(key,Value());
		}
		return GetReference(key);
	}

	template<typename Key,typename Value,class HashClass>
	typename Value SeparateChainingHashST<Key,Value,HashClass>::Get( Key key)
	{
		int ihash = Get_Hash(key,m_iHashTableSize);

		LinkListByKeyValue<Key,Value>::Node* tmp = m_HashTable[ihash].GetFromList(key);

		if (tmp != NULL)
		{
			return tmp->m_value;
		}
		else
		{
			// 模板类内初始化值
			Value tmp = Value();
			return tmp;
		}
	}

	template<typename Key,typename Value,class HashClass>
	typename Value& SeparateChainingHashST<Key,Value,HashClass>::GetReference( Key key)
	{
		int ihash = Get_Hash(key,m_iHashTableSize);

		return m_HashTable[ihash].GetFromList(key)->m_value;

	}

	template<typename Key,typename Value,class HashClass>
	bool SeparateChainingHashST<Key,Value,HashClass>::isContain( Key key)
	{
		int iHash = Get_Hash(key,m_iHashTableSize);
		return m_HashTable[iHash].GetFromList(key) != NULL;
	}

	template<typename Key,typename Value,class HashClass>
	int SeparateChainingHashST<Key,Value,HashClass>::Get_Size()
	{
		return m_iCountOfValue;
	}

	template<typename Key,typename Value,class HashClass>
	bool SeparateChainingHashST<Key,Value,HashClass>::isEmpty( Key key)
	{
		return m_iCountOfValue == 0;
	}
};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include "Component.h"
#include "SeparateChainingHashST.h"

using namespace jay;

class GetIntHash
{
public:
	int operator()(const int & key,int HashTableSize)
	{
		return (key& 0x7fffffff) % HashTableSize;
	}
};

class GetStringHash
{
public:
	int operator()(const string & key,int HashTableSize)
	{
		int hash = 0;
		for(int i = 0; i < key.length(); ++i)
		{
			hash = hash << 7 ^ key[i];
		}
		return (hash& 0x7fffffff) % HashTableSize;
	}
};

int main(int argc, char* argv[])
{
	// 暂未支持哈希表大小动态变化
	// 根据数据的实际情况来调整哈希表的大小
 	SeparateChainingHashST<int,string,GetIntHash> myHash(100);
	cout << "is Empty? " << myHash.isContain(0) << endl;
	myHash.Insert(0,"123");
	myHash.Insert(0,"012");
	myHash.Insert(1,"123");
	myHash.Insert(2,"223");
	myHash.Insert(3,"323");
	myHash.Insert(4,"423");
	myHash.Insert(5,"123");
	myHash.Insert(6,"012");
	myHash.Insert(7,"123");
	myHash.Insert(8,"223");
	myHash.Insert(9,"323");
	myHash.Insert(10,"222222222222423");
	myHash.Insert(11,"1111423");

	cout << "is Empty? " << myHash.isContain(0) << endl;
	cout << "Size? " << myHash.Get_Size() << endl;

	cout << myHash.isContain(10) << endl;
	myHash.Delete(10);
	cout << "Size? " << myHash.Get_Size() << endl;
	cout << myHash.isContain(10) << endl;
	cout << myHash.isContain(1) << endl;
	cout << myHash.isContain(4) << endl;
	cout << myHash.isContain(1477) << endl;

	cout << myHash.Get(10) << endl;
	cout << myHash.Get(1) << endl;
	cout << myHash.Get(2) << endl;
	cout << myHash.Get(3) << endl;
	cout << myHash.Get(4) << endl;
	cout << myHash.Get(5111) << endl;
	cout << myHash.isContain(5111) << endl;

	SeparateChainingHashST<string,int,GetStringHash> myStrHash(100);
	cout << "is Contain 1? " << myStrHash.isContain("1") << endl;

	myStrHash.Insert("你好",3);
	myStrHash.Insert("hjm",4);
	myStrHash.Insert("1234",5);
	cout << myStrHash.Get("hjm") << endl;
	cout << myStrHash.Get("1234") << endl;
	cout << myStrHash.Get("你好") << endl;
	cout << myStrHash.Get("你好1") << endl;
	cout << myStrHash["你好"] << endl;
	myStrHash["你好"] = 15;
	cout << myStrHash["你好"] << endl;
	cout << myStrHash["你好XX"] << endl;
	myStrHash["你好YY"] = 6;
	cout << myStrHash["你好YY"] << endl;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。