C++之开散列哈希表

闭散列哈希表

元素的插入

元素的查找

元素的删除

上期我们学习了闭散列哈希表，闭散列哈希表和开散列哈希表的区别就是插入的元素在冲突时，应对冲突的处理方式不同，本期我们将详细的学习闭散列哈希表。

闭散列哈希表

闭散列哈希表图示如下。

开散列哈希表就是将冲突的元素通过一个单向链表链接起来。在闭散列哈希表中，当平衡因子的大小大于为0.7时，就需要进行扩容，这样可以尽可能避冲突。在开散列哈希表中，因为冲突的元素可以通过一张链表链接在同一位置，对于冲突的容忍性会比闭散列的容忍性较高，但是为了避免一个位置冲突的元素过多，所以在平衡因子为1时也需要进行扩容。

元素的插入

bool insert(const pair<K, V>& pair){HashFunc<K> hf;Node* node = find(pair.first);if (node){return false;}if (_table.size() == 0 || _num * 10 / _table.size() > 10){int NewSize = _table.size() == 0 ? 10 : _table.size() * 2;vector<Node*> newtable;newtable.resize(NewSize);for (int i = 0; i < _table.size(); i++){Node* cur = _table[i];while(cur){Node* next = cur->_next;int num = hf(cur->_kv.first) % newtable.size();cur->_next = newtable[num];newtable[num] = cur;cur = next;}_table[i] = nullptr;}newtable.swap(_table);}int index = hf(pair.first) % _table.size();Node* newnode = new Node(pair);//头插newnode->_next = _table[index];_table[index] = newnode;_num++;return true;}

元素的插入同闭散列哈希表一样，也需要扩容，但是在进行扩容时，因为节点的创建是非常消耗空间的，所以我们不像闭散列哈希表一样，创建了一个哈希表对象去复用insert函数，而知识创建了一个vector对象，然后通过更改映射与指针的关系，实现扩容之后，新表中元素的映射。

元素的查找

Node* find(const K& key){if (_table.size() == 0){return nullptr;}HashFunc<K> hf;int index = hf(key) % _table.size();Node* cur = _table[index];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}

元素的查找原理很简单，因为我们是把所有冲突的元素放在了一张链表里，所以只需在特定映射位置的链表里找对应的元素即可。

元素的删除

bool erase(const K& key){if (_table.size() == 0){return false;}HashFunc<K> hf;int index = hf(key)% _table.size();Node* prev = nullptr;Node* cur = _table[index];while(cur){if (cur->_kv.first==key  ){if (prev == nullptr){//头删_table[index] = cur->_next;}else{//中间删除prev->_next = cur->_next;}--_num;delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}

元素的删除，分为头删和中间删除，我们通过判断prev指针是否为空来判断是否是头删还是尾删，因为元素都是通过链表节点链接起来的，所以删除只需要更改指针的指向即可。

测试代码

void opentest(){HashTable<int, int> ht;ht.insert(make_pair(1, 1));ht.insert(make_pair(2, 1));ht.insert(make_pair(3, 1));ht.insert(make_pair(4, 1));ht.insert(make_pair(5, 1));ht.insert(make_pair(6, 1));ht.insert(make_pair(7, 1));ht.insert(make_pair(8, 1));ht.insert(make_pair(9, 1));ht.insert(make_pair(10, 1));ht.insert(make_pair(11, 1));ht.insert(make_pair(12, 1));ht.erase(1);ht.erase(2);ht.erase(3);cout << ht.find(1) << endl;cout << ht.find(5) << endl;}}

调试代码，结果符合预期。