快上网专注成都网站设计 成都网站制作 成都网站建设
成都网站建设公司服务热线:028-86922220

网站建设知识

十年网站开发经验 + 多家企业客户 + 靠谱的建站团队

量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决

模拟实现英汉字典(使用key/value形式的哈希表)-创新互联

上一篇博客我们实现了key形式的线性探测法处理哈希冲突,有了前面的基础,我们就可以实现更加有难度的key/value形式的二次探测。

鲅鱼圈网站建设公司创新互联,鲅鱼圈网站设计制作,有大型网站制作公司丰富经验。已为鲅鱼圈1000多家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的鲅鱼圈做网站的公司定做!
  •  什么是key/value形式呢?

 key/value形式就是在哈希表中,有一个决定数据在表中位置的关键字key和这个关键字所携带的值value。

  在这里我们的目标是实现一个英汉字典,一个英语字符串就是key,对应的有一个汉语翻译value,通过key我们可以找到value。所以在这里key和value是“绑”在一起的,我们就用一个结构体来聚合起来:

template
struct Key_Value
{
	K _key;
	V _value;
	Key_Value(const K& key=K(), const V& value=V())
		:_key(key)
		, _value(value)
	{}
};

 key_value的构造函数中的形参key和value都有一个默认值,默认值是一个临时对象。

  • 还是同样的方法,我们用哈希表来实现字典,哈希表的查找效率真的太诱人!!

    字典的结构如下:

#pragma once
#include
#include
using namespace std;
enum State
{
	EXIST,
	EMPTY,
	DELETE
};
template
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 Dictionary
{
	typedef Key_Value KV;
public:
	Dictionary();
	//~Dictionary();
	Dictionary(size_t size);//初始化字典的大小
	bool Add(const K& key, const V& value);
	bool Delete(const K& key);
	size_t Find(const K& key);
	bool Alter(const K& key,const K& newkey,const V& newvalue);
	void Print();
protected:
	size_t HashFunc(const K& key);//哈希函数
	void Swap(Dictionary& d);
protected:
	KV* _table;
	State* _state;
	size_t _size;
	size_t _capacity;
	FuncModel _HF;
};

对于一个英汉字典我们要实现的是它的增删改查功能

(一)添加条目:

template>
bool Dictionary::Add(const K& key, const V& value)
{
	if (_size * 10 >= _capacity * 8)//载荷因子超过0.8,增容
	{
		Dictionary tmp(_capacity * 2 + 1);
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (_state[i] == EXIST)
			{
				KV node(_table[i]._key, _table[i]._value);
				size_t adress = HashFunc(_table[i]._key);
				size_t index = adress;
				size_t flag = 0;
				while (tmp._state[index] == EXIST)
				{
					index = adress + flag*flag;
					while (index >= _capacity)//如果到了散列表的末尾,要返回表的头
					{
						index -= _capacity;
					}
					flag++;
				}
				tmp._table[index] = node;
				tmp._size++;
				tmp._state[index] = EXIST;
			}
		}
		Swap(tmp);//this和tmp交换内容
	}
	size_t adress = HashFunc(key);
	size_t index = adress;//adress是不能变的,用index来标记最后的位置
	size_t flag = 0;
	while (_state[index] == EXIST)//二次探测
	{
		index = adress + flag*flag;
		while(index >= _capacity)//如果到了散列表的末尾,要返回表的头
		{
			index -= _capacity;
		}
		flag++;
	}
	KV tmp(key, value);
	_table[index] = tmp;
	_state[index] = EXIST;
	_size++;
	return true;
}

(二)查找条目:

template>
size_t Dictionary::Find(const K& key)
{
	size_t adress = HashFunc(key);
	size_t index = adress;
	for (size_t flag = 0; flag < _capacity;)
	{
		if (_table[index]._key == key)//二次探测
		{
			return index;
		}
		index = adress + flag*flag;
		while (index >= _capacity)
		{
			index -= _capacity;
		}
		flag++;
	}
	return -1;
}

 在查找的时候flag不仅用来控制查找的次数,还可以控制二次探测的增量(i^2,i++)。最多查找_capacity次就可以了。找了_capacity次还没找到就说明不存在。

(三)删除条目:

  调用查找条目,若找到则删除,否则返回flase.

template>
bool Dictionary::Delete(const K& key)
{
	size_t index = Find(key);
	if (index >= 0)
	{
		_state[index] = DELETE;
		_size--;
		return true;
	}
	return false;
}

(四)修改条目:

  调用查找条目,若找到则修改,否则返回flase.

emplate>
bool Dictionary::
Alter(const K& key,const K& newkey,const V& newvalue)
{
	size_t index = Find(key);
	if (index > 0)
	{
		_table[index]._key = newkey;
		_table[index]._value = newvalue;
		return true;
	}
	return false;
}

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


网站栏目:模拟实现英汉字典(使用key/value形式的哈希表)-创新互联
当前URL:http://6mz.cn/article/dseggi.html

其他资讯