当前位置：首页 > news >正文

哈希表---闭散列

news 来源：原创 2024/9/29 9:22:40

闭散列

当我们用哈希函数的时候，其中一个就是除留余数法

取这个表的长度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;//记录表中数据个数
};

插入问题1

当用除留余数法的时，除以的的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了，就无法访问了

插入问题2

是不是有疑惑，当size==0的时候怎么处理？那就要扩容了

还有什么情况下要扩容？

在载荷因子较大的情况下要进行扩容

插入问题3

怎么扩容？

你们的脑瓜子一想简单啦，直接用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;}