十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
上一篇博客我们实现了key形式的线性探测法处理哈希冲突,有了前面的基础,我们就可以实现更加有难度的key/value形式的二次探测。
鲅鱼圈网站建设公司创新互联,鲅鱼圈网站设计制作,有大型网站制作公司丰富经验。已为鲅鱼圈1000多家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱,请找那个售后服务好的鲅鱼圈做网站的公司定做!什么是key/value形式呢?
在这里我们的目标是实现一个英汉字典,一个英语字符串就是key,对应的有一个汉语翻译value,通过key我们可以找到value。所以在这里key和value是“绑”在一起的,我们就用一个结构体来聚合起来:
templatestruct 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许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。