【代码】key-value模式下的哈希二次探测与简单的哈希类的实现-创新互联

二次探测是避免哈希冲突的一种常见手段，思想是：

为渭南等地区用户提供了全套网页设计制作服务，及渭南网站建设行业解决方案。主营业务为成都网站设计、成都网站制作、渭南网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

    插入：

    找到哈希位置（serch）->如果不冲突就插入，冲突就进行第一次探测

    第1次探测：

    哈希位置变为原有哈希位置加上1*1的偏移->进行插入

    ....

    ....

    第i次探测：

    哈希位置变为原有哈希位置加上i*i的偏移->进行插入

    知道插入完成为止。

如图所示：

    哈希类代码如下：

#pragma once
#include<vector>
#include<string>
enum Status
{
	DELETE,
	EMPTY,
	EXIST,
};
template<class K, class V>
struct KV
{
	KV()
	{}
	KV(K _key, V _value)
	:key(_key)
	, value(_value)
	{}
	Status s;
	K key;
	V value;
};
template<class K>
struct DefaultHash
{
	size_t operator()(const K& k)
	{
		return k;
	}
};
template<>
struct DefaultHash<string>
{
	size_t operator()(const string&k)
	{
		size_t ret = 0;
		for (size_t i = 0; i < k.size(); ++i)
		{
			ret *= 10;
			ret += k[i];
		}
		return ret;
	}
};
template<class K,class V,
class Hash = DefaultHash<K> >
class HashTable
{
public:
	HashTable(size_t capacity)
		:tables(new KV<K,V>[capacity])
		,_size(0)
		, _capacity(capacity)
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			tables[i].s = EMPTY;
		}
	}
	HashTable()
		:_size(0)
		, _capacity(0)
	{}
	void Push(const KV<K,V> &x)
	{
		size_t index = search(x.key);
		tables[index].s = EXIST;
		tables[index].key = x.key;
		tables[index].value = x.value;
		++_size;
	}
	void Print()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			cout << i << ":";
			if (tables[i].s == EXIST)
				cout <<"["<<tables[i].key<<","<< tables[i].value<<"]";
			else
				cout << "NULL";
			cout << endl;
		}
		cout << endl;
	}
	int Find(const K& key)
	{
		Hash Search;
		int index = Search(key) % _capacity;
		size_t i = 0;
		while (tables[index].s != EMPTY)
		{
			if (tables[index].key == key&&tables[index].s == EXIST)
				return index;
			i++;
			index += 2*i-1;
			if (index >= _capacity)
				index %= _capacity;
		}
		return -1;
	}
	void Pop(const K& key)
	{
		int index = Find(key);
		if (index > 0)
		{
			tables[index].s = DELETE;
			_size--;
		}
	}
	~HashTable()
	{
		if (tables)
			delete[]tables;
		_size = 0;
		_capacity = 0;
	}
protected:
	size_t search(K key)
	{
		if (_size * 2 >= _capacity)
		{
			HashTable tmp(_capacity * 2 + 10);
			for (size_t i = 0; i < _capacity; ++i)
			{
				if (tables[i].s == EXIST)
					tmp.Push(tables[i]);
			}
			std::swap(tables, tmp.tables);
			std::swap(_size, tmp._size);
			std::swap(_capacity, tmp._capacity);
		}
		Hash Search;
		size_t index = Search(key)%_capacity;
		size_t i = 0;
		while (tables[index].s == EXIST)
		{
			i++;
			index += i*i;
			if (index >= _capacity)
				index %= _capacity;
		}
		return index;
	}
protected:
	KV<K,V>* tables;
	size_t _size;
	size_t _capacity;
};

    如有疑问希望提出，有不足也希望指正

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

网页名称：【代码】key-value模式下的哈希二次探测与简单的哈希类的实现-创新互联
转载源于：https://www.cdcxhl.com/article40/copdeo.html

成都网站建设公司_创新互联，为您提供网站导航、软件开发、外贸建站、商城网站、App开发、微信公众号

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联