温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

实现哈希桶(空间利用率较高的哈希表)

发布时间:2020-06-16 18:44:50 阅读:4018 作者:稻草阳光L 栏目:开发技术
亿速云空间服务器,独享5M带宽,BGP线路,安全稳定,不到0.96元/天! 查看详情>>

  前面几篇博客已经写过了哈希表的闭散列法,也写过哈希表的应用,在这里就不赘述。今天我们要实现的是一个哈希桶。什么哈希桶呢?

  • 哈希桶:哈希桶就是盛放不同key链表的容器(即是哈希表),在这里我们可以把每个key的位置看作是一个孔,孔里放了一个链表

  • 哈希桶是使用一个顺序表来存放具有相同哈希值的key的链表的头节点,利用这个头节点可以找到其它的key。

  • 实现哈希桶(空间利用率较高的哈希表)

  • #pragma once
    #include<iostream>
    #include<string>
    #include<vector>
    
    using namespace std;
    
    template<class T>
    struct DefaultFunc
    {
    	size_t operator()(const T& data)
    	{
    		return (size_t)data;
    	}
    };
    
    struct StringFunc
    {
    	size_t operator()(const string& str)
    	{
    		size_t sum = 0;
    		for (size_t i = 0; i < str.size(); ++i)
    		{
    			sum += str[i];
    		}
    		return sum;
    	}
    };
    
    template<class Kclass V>
    struct HashBucketNode
    {
    	K _key;
    	V _value;
    	HashBucketNode<K, V>* _next;
    	HashBucketNode(const K& key, const V& value)
    		:_key(key)
    		, _value(value)
    		, _next(NULL)
    	{}
    };
    
    template<class Kclass Vclass FuncModle = DefaultFunc<K>>
    class HashBucket
    {
    	typedef HashBucketNode<K, V> Node;
    public:
    	HashBucket();
    	//~HashBucket();
    	HashBucket(const HashBucket<K, V, FuncModle>& h);
    	HashBucket<K, V, FuncModle>& operator=(HashBucket<K, V, FuncModle> h);
    	bool Insert(const K& key, const V& value);
    	Node* Find(const K& key);
    	bool Remove(const K& key);
    	//bool Alter(const K& key);//用Find实现
    	void Print();
    protected:
    	void _CheckExpand();//检查是否需要扩容
    	size_t _GetNextPrime(size_t size);//从素数表中得到比当前素数大的素数
    	size_t _HashFunc(const K& key,size_t mod);//哈希函数
    protected:
    	vector<Node*> _table;
    	size_t _size;//记录的个数
    };

得到哈希桶的结构以后,我们来实现几个比较重要的函数:

(一)bool Insert(const K& key, const V& value)

  插入函数是最难实现的,它涉及到是否需要扩容。为插入函数我们写了两个内部函数void _CheckExpand(); 和 size_t _GetNextPrime(size_t size);

template<class Kclass Vclass FuncModle>
bool HashBucket<K, V, FuncModle>::Insert(const K& key, const V& value)
{
	_CheckExpand();
	//使用头插法插入
	size_t index = _HashFunc(key,_table.size());
	Node* tmp=new Node(key, value);//一定要用new出结点
	if (_table[index] == NULL)
	{
		_table[index] = tmp;
	}
	else
	{
		//不为NULL则使用头插法插入新结点
		tmp->_next = _table[index];
		_table[index] = tmp;
	}
	_size++;
	return true;
}
template<class Kclass Vclass FuncModle>
size_t  HashBucket<K, V, FuncModle>::_GetNextPrime(size_t size)
{
	const int _PrimeSize = 28;
	static const unsigned long _PrimeList[_PrimeSize] =
	{
		53ul97ul193ul389ul769ul,
		1543ul3079ul6151ul12289ul24593ul,
		49157ul98317ul196613ul393241ul786433ul,
		1572869ul3145739ul6291469ul12582917ul25165843ul,
		50331653ul100663319ul201326611ul402653189ul805306457ul,
		1610612741ul3221225473ul4294967291ul
	};
	for (int i = 0; i < _PrimeSize; ++i)
	{
		if (_PrimeList[i] > size)
			return _PrimeList[i];
	}
	assert(false);
	return 4294967291ul;
}
template<class Kclass Vclass FuncModle>
void HashBucket<K, V, FuncModle>::_CheckExpand()
{
	if (_size == _table.size())
	{
		size_t newsize = _GetNextPrime(_size);//从素数表中取出下一个素数
		if (newsize == _size)
			return;
		vector<Node*> newtable;
		newtable.resize(newsize);
		for (size_t i = 0; i < _size; ++i)
		{
			size_t index = _HashFunc(_table[i]->_key,newsize);
			if (_table[i])
			{
				Node* head = _table[i];//保存头节点
				newtable[index] = head;//摘下vector的第一个指针为新表的头节点
				_table[i] = _table[i]->_next;
				while (_table[i])//依次摘结点
				{
					Node* tmp = _table[i];
					_table[i] = _table[i]->_next;
					head->_next = tmp;
					head = head->_next;
				}
			}
			else
				newtable[index] = NULL;
			_table[i] = NULL;
		}
		swap(_table, newtable);
	}
}

  在调用哈希函数HashFunc的时候一定要注意,我们用key取模一定模的是vector当前的容量。

  在插入的时候使用头插法是很高效的!!!

(二)Node* Find(const K& key);

  查找函数返回一个结点的指针方便我们在外部更改数据。

emplate<class Kclass Vclass FuncModle>
HashBucketNode<K,V>* HashBucket<K, V, FuncModle>::Find(const K& key)
{
	size_t index = _HashFunc(key, _table.size());
	while (_table[index])
	{
		if (_table[index]->_key == key)
		{
			return _table[index];
		}
		_table[index] = _table[index]->_next;
	}
	return NULL;
}

   我们在写删除节点函数时最好别调用Find函数去查找要删除的结点,如果要删除的结点是头节点或者尾节点的话就无法修改要删除指针的前一个指针的_next域;

template<class Kclass Vclass FuncModle>
bool HashBucket<K, V, FuncModle>::Remove(const K& key)
{
	//不能用find找到,然后删。
	size_t index = _HashFunc(key,_table.size());
	if (_table[index] == NULL)
		return false;
	Node* cur = _table[index];
	if (cur->_key==key)
	{
		Node* del = cur;
		_table[index] = cur->_next;
		delete del;
		_size--;
		return true;
	}
	else
	{
		Node* prev = NULL;
		while (cur)
		{
			if (cur->_key == key)
			{
				prev->_next = cur->_next;
				delete cur;
				_size--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
}

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI

开发者交流群×