基于线性探测的哈希表(LinearProbingHashST) -- C++实现


实现代码

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

#include "Component.h"

namespace jay{

	template<typename Key,typename Value,class HashClass>
	class LinearProbingHashST
	{
	private:
		Key** m_key;
		Value** m_value;
		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);

		LinearProbingHashST();
		LinearProbingHashST(int TableSize);
		~LinearProbingHashST();

	};

	template<typename Key,typename Value,class HashClass>
	LinearProbingHashST<Key,Value,HashClass>::LinearProbingHashST():
	m_iHashTableSize(50),m_iCountOfValue(0)
	{
		// m_key为**类型,现在指向一个指针数组,数组的每个元素存放一个Key*的类型
		m_key = new Key*[m_iHashTableSize];
		// m_value为**类型,现在指向一个指针数组,数组的每个元素存放一个Value*的类型
		m_value = new Value*[m_iHashTableSize];

		// key value数组初始化 NULL在函数重载的时候可以转化为0,以后注意不要使用NULL
		for (int i = 0; i < m_iHashTableSize; ++i)
		{
			m_key[i] = nullptr;
			m_value[i] = nullptr;
		}
	}

	template<typename Key,typename Value,class HashClass>
	LinearProbingHashST<Key,Value,HashClass>::LinearProbingHashST(int TableSize):
	m_iHashTableSize(TableSize),m_iCountOfValue(0)
	{
		// m_key为**类型,现在指向一个指针数组,数组的每个元素存放一个Key*的类型
		m_key = new Key*[m_iHashTableSize];
		// m_value为**类型,现在指向一个指针数组,数组的每个元素存放一个Value*的类型
		m_value = new Value*[m_iHashTableSize];

		// key value数组初始化 NULL在函数重载的时候可以转化为0,以后注意不要使用NULL
		for (int i = 0; i < m_iHashTableSize; ++i)
		{
			m_key[i] = nullptr;
			m_value[i] = nullptr;
		}
	}

	template<typename Key,typename Value,class HashClass>
	LinearProbingHashST<Key,Value,HashClass>::~LinearProbingHashST()
	{
		for (int i = 0; i < m_iHashTableSize; ++i)
		{
			if (m_key[i] != nullptr)
			{
				delete m_key[i];
				m_key[i] = nullptr;
				delete m_value[i];
				m_value[i] = nullptr;
			}
		}

		delete []m_value;
		m_value = nullptr;
		
		delete []m_key;
		m_key = nullptr;
	}

	template<typename Key,typename Value,class HashClass>
	void LinearProbingHashST<Key,Value,HashClass>::Resize(int newHashTableSize)
	{
		LinearProbingHashST<Key, Value, HashClass> *tmp = new LinearProbingHashST(newHashTableSize);
		for (int i = 0; i < m_iHashTableSize; ++i)
		{
			// 如果当前有值,则tmp进行插入,此时使用新的TableSize计算哈希值
			if (m_key[i] != nullptr)
			{
				tmp->Insert(*m_key[i], *m_value[i]);

				// 释放空间 
				delete m_key[i];
				m_key[i] = nullptr;
				delete m_value[i];
				m_value[i] = nullptr;
			}
		}

		// 释放旧的空间
		delete []m_value;
		m_value = nullptr;

		delete []m_key;
		m_key = nullptr;
		
		// 关联新的空间
		m_key = tmp->m_key;
		m_value = tmp->m_value;
		m_iHashTableSize = tmp->m_iHashTableSize;

	//	delete tmp;
	}


	// 线性探测法实现的哈希表一定要动态调整大小,否则有可能造成无限循环
	template<typename Key,typename Value,class HashClass>
	void LinearProbingHashST<Key,Value,HashClass>::Insert( Key key,Value value)
	{
		// 用了50%以后大小翻倍
		if (m_iCountOfValue >= m_iHashTableSize / 2)
			Resize(2 * m_iHashTableSize);

		int iHash = Get_Hash(key,m_iHashTableSize);
		for (; m_key[iHash] != nullptr; iHash = (iHash + 1) % m_iHashTableSize)
		{
			// 如果key已存在则更新value
			if (*(m_key[iHash]) == key)
			{
				*(m_value[iHash]) = value;
				return;
			}
		}
		m_key[iHash] = new Key(key);
		m_value[iHash] = new Value(value);
		m_iCountOfValue++;
	}

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

		// 第一步查找 key
		bool isFind = false;
		int i = Get_Hash(key,m_iHashTableSize);
		for (; m_key[i] != nullptr; i = (i + 1) % m_iHashTableSize) 
		{
			//找到key对应的哈希值
			if (*(m_key[i]) == key)
			{
				isFind = true;
				break;
			}
		}

		// key不存在
		if (!isFind)
			return;

		// 删除当前的key和value
		delete m_key[i];
		m_key[i] = nullptr;
		delete m_value[i];
		m_value[i] = nullptr;
		// 删除元素后数量-1
		m_iCountOfValue--;

		// 将该元素后面(可能存在的)冲突数据删除后重新加入哈希表,
		i = (i + 1) % m_iHashTableSize;
		while (m_key[i] != nullptr) 
		{
			// delete keys[i] an vals[i] and reinsert
			Key   keytmp = *m_key[i];
			Value valuetmp = *m_value[i];

			// 删除当前的key和value
			delete m_key[i];
			m_key[i] = nullptr;
			delete m_value[i];
			m_value[i] = nullptr;

			// 这里-1,Insert的时候+1,相等于数量没变
			m_iCountOfValue--;
			Insert(keytmp, valuetmp);
			i = (i + 1) % m_iHashTableSize;
		}

		// halves size of array if it's 12.5% full or less
		if (m_iCountOfValue > 0 && m_iCountOfValue <= m_iHashTableSize/8) 
			Resize(m_iHashTableSize/2);

	}

	template<typename Key,typename Value,class HashClass>
	typename Value& LinearProbingHashST<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 LinearProbingHashST<Key,Value,HashClass>::Get( Key key)
	{
		for (int i = Get_Hash(key,m_iHashTableSize); m_key[i] != nullptr; i = (i + 1) % m_iHashTableSize) 
		{
			//找到key对应的哈希值
			if (*(m_key[i]) == key)
			{
				return *m_value[i];
			}
		}

		// 上面没有找到
		// 模板类内初始化值,返回一个默认值
		Value tmp = Value();
		return tmp;
	}

	template<typename Key,typename Value,class HashClass>
	typename Value& LinearProbingHashST<Key,Value,HashClass>::GetReference( Key key)
	{
		for (int i = Get_Hash(key,m_iHashTableSize); m_key[i] != nullptr; i = (i + 1) % m_iHashTableSize) 
		{
			//找到key对应的哈希值
			if (*(m_key[i]) == key)
			{
				return *m_value[i];
			}
		}

	}

	template<typename Key,typename Value,class HashClass>
	bool LinearProbingHashST<Key,Value,HashClass>::isContain( Key key)
	{
		for (int i = Get_Hash(key,m_iHashTableSize); m_key[i] != nullptr; i = (i + 1) % m_iHashTableSize) 
		{
			//找到key对应的哈希值
			if (*(m_key[i]) == key)
			{
				return true;
			}
		}

		return false;
	}

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

	template<typename Key,typename Value,class HashClass>
	bool LinearProbingHashST<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 "LinearProbingHashST.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[])
{
	// 暂未支持哈希表大小动态变化
	// 根据数据的实际情况来调整哈希表的大小
	LinearProbingHashST<int,string,GetIntHash> myHash;
	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;

	LinearProbingHashST<string,int,GetStringHash> myStrHash;
	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;
}

 

暂无评论

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