站长工具seo综合查询方法_社区推广宣传活动方案_seo论坛_搜索引擎推广试题

---

前言

  哈喽大家好！承接上文，今天我们再来模拟实现一下哈希表
  它的实现方式一共有两种！

---

一、闭散列

大思路

  闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去

有点强盗逻辑，既然我的位置没了，那就去抢别人的位置！

基本构架

	enum State{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K, class V>class HashTable{public:private:vector<HashData<K, V>> _tables;size_t _n = 0;};

_ size 一般用于序列式容器中表示有效元素个数，在关联式容器中命名约定一般规定 _n 作为记录有效元素个数

插入数据

  在插入过程，元素需要通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入

  在向后寻找位置途中可能存在越界情况，这里采用处理循环队列方式进行取模操作，保证数据在合法范围进行查找。这里存在一个大前提，空间是充足的，不然找半天都找不到位置

		bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 扩容if (_n * 10 / _tables.size() >= 7){//vector<HashData<K, V>> newTables(_tables.size() * 2); 遍历旧表，将所有数据映射到新表 ...//_tables.swap(newTables);HashTable<K, V, Hash> newHT;newHT._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

扩容逻辑

  上点中我们代码中有个扩容模块

负载因子越小，冲突率越低，效率就越高，空间利用率就越低

  当然，为了防止出现类型问题，我们采用乘个十的方法来解决这类问题

同时，我们可以思考一个问题，就是我们的 n 到底是除以 size() 还是 capacity() ，选择后者有可能会导致越界访问，所以我们可以先在构造函数中为 _tables 开辟空间，同时防止了 size() 出现等于零的风险

扩容换表

  当哈希表进行扩容逻辑时，导致了散列表长度发生了变换。这也意味着通过哈希函数(开发定址法)得到的位置需要重新安排插入

  这个时候我们就可以重新书写哈希函数，避免显得冗余，这就是插入逻辑复用

查找元素

		HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (   _tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}++hashi;hashi %= _tables.size();}return nullptr;}

  其中我们需要注意的是，当删除某个元素时，查找过程中无法判断找到数据及其是否需要继续前进，这时候就需要DELETE标记

删除数据

		bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{ret->_state = DELETE;return true;}}

哈希表删除数据是我们遇到最简单的删除逻辑，只需要改变位置状态就可以了

除留余数法出现类型问题

  对于 key 进行取模查找，是建立在 key 属于无符号整型类型来考虑的，但是我们设计属于泛型编程，key 需要去适应不同种类型如 string类型、自定义类型、负数

简单类型做key

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};

string类型做key

  这时候我们可能会想，能不能把字母转成 ASCII 码值，但是事实上，这种方法可能会出错，且也可能会发生哈希冲突，因为不同字符组合可能具有相同的 ASCII 码总和

  这个时候，我们就可以进行模板特化

template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (const auto& e : key){hash *= 31;hash += e;}return hash;

二、开散列

大思路

  开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

开散列中每个桶中放的都是发生哈希冲突的元素，并没有顺序之分

插入数据

			Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;

其实头插尾插都行，只不过是尾插有点麻烦，头插比较简单轻松

析构函数

  这里涉及堆上空间资源的开辟，一般需要涉及析构函数进行资源处理

		~HashTable(){// 依次把每一个桶释放for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}

哈希扩容

  到这里，我们可以复用闭散列的扩容方案，只是那种方案如果存在一万个节点，意味着需要复制一万个节点又要释放一万个节点，显得很浪费

  这时候我们就可以采取一种新的方式了！

  先保存 cur 的下一个节点 next，然后得到新表的位置，再把 cur 所指向的节点链到新的表上，这就是我们的思路

删除数据

		bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}

一种是删除第一个节点，另一种是删除其他节点prev->_next = cur->_next

哈希查找

		Node* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}

---

总结

  本节其实没有什么特别难的地方，但是但是，下一篇的 unordered 封装就不尽然了，请继续加油！