赞
踩
当我们用哈希函数的时候,其中一个就是除留余数法
取这个表的长度len,按照哈希函数:Hash(key) = key% len,将这个位置映射到表中
通过上面的除留余数法,会有哈希碰撞的问题,可以通过闭散列来解决
闭散列也叫开放定址法,通过线性探测,依次找后面的位置存储
- enum State
- {
- EMPTY,
- EXIST,
- DELETE
- };
-
- template<class K, class V>
- struct HashData
- {
- pair<K, V> _kv;
- State _state=EMPTY;
- };
哈希表的底层可以用vector封装
- template<class K,class V>
- class HashTable
- {
- public:
-
- bool insert(const pair<K,V>& kv)
- {
-
- ...........
- }
-
- private:
- vector<HashData<K, V>> _ht;
- size_t _n = 0;//记录表中数据个数
- };
当用除留余数法的时,除以的的vector的capacity还是size呢?
- bool insert(const pair<K,V>& kv)
- {
- int hashi = kv.first% _ht.size();
- int index = hashi;
- int i = 1;
- while (_ht[index]._state ==EXIST)
- {
- index = hashi + i;
- index %= _ht.size();
- i++;
- }
- _ht[index]._kv = kv;
- _ht[index]._state = EXIST;
- _n++;
- }
答案是size,因为用vector的[ ]的时候,是只能访问size的部分的,假如是capacity,算出来的值可以就大于size了,就无法访问了
是不是有疑惑,当size==0的时候怎么处理?那就要扩容了
还有什么情况下要扩容?
在载荷因子较大的情况下要进行扩容
怎么扩容?
你们的脑瓜子一想简单啦,直接用vector的reserve就好啦,不对的,vector的reserve是扩大了capacity,size没有变的
我们可以用resize进行扩容,risize既扩容又初始化,size改变了
再把旧表数据移到新表
-
- bool insert(const pair<K,V>& kv)
- {
- if (Find(kv.first))
- return false;
- if (_ht.size()==0||_n * 10 / _ht.size() >= 7)
- {
- int newsize = _ht.size() == 0 ? 10 : _ht.size() * 2;
- HashTable<K, V> newht;
- //对原来insert进行复用
- newht._ht.resize(newsize);
-
- //遍历旧表,来初始化新表
- for (auto& data : _ht)
- {
- if (data._state == EXIST)
- {
- newht.insert(data._kv);
- }
-
- }
- _ht.swap(newht._ht);
- }
- //线性探测
- int hashi = kv.first% _ht.size();
- int index = hashi;
- int i = 1;
- while (_ht[index]._state ==EXIST)
- {
- index = hashi + i;
- index %= _ht.size();
- i++;
- }
- _ht[index]._kv = kv;
- _ht[index]._state = EXIST;
- _n++;
- return true;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。