闭散列二次探测的哈希表代码实现插入删除查找
实际上，线性探测也是具有一定的缺陷的，线性探测的缺陷就是会将产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为
其中：i=1,2,3...,H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
那么，对于2.1中如果要插入44，产生冲突，使用解决后的情况为
由于闭散列不管使用什么探测方式，都是治标不治本，所以这里就不再继续代码实现二次探测了，下面我们看一看开散列的实现方式
5.2 开散列
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列哈希表代码实现插入删除查找
1、首先由于结构的原因，要把数据链接起来需要一个节点类：
template<class K, class V> struct HashNode { std::pair<K, V> _kv; HashNode* _next; HashNode(const std::pair<K, V>& kv) :_kv(kv) ,_next(nullptr) {} };
2、同样的，由于KV结构中的key是一个泛型，当我们在进行哈希映射的时候，需要先让其映射成为整型，然后才能够映射到哈希地址，所以这里提供一个仿函数，用于将key映射到整型家族
template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<>//模板的特化 struct HashFunc<std::string> { size_t operator()(const std::string& key) { size_t hash = 0; for (auto ch : key) { hash *= 131; hash += ch; } return hash; } };
3、开散列的哈希表结构
template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: HashTable() :_n(0) { _tables.resize(10); } private: std::vector<Node*> _tables;//本质上是一个指针数组，存放节点指针。 size_t _n = 0; };
4、插入
bool Insert(const std::pair<K,V>& kv) { if(Find(kv.first)) return false; //扩容 //负载因子为1的时候就扩容 if(_n == _tables.size()) { //扩容方式有两种，一种是遍历，然后创建新节点挂在新表上 //由于方案一造成的消耗较大，所以这里就不实现了 // HashTable<K, V, Hash> newTable; // newTable._tables.resize(2 * _tables.size()); //另一种是直接更改节点的指向 std::vector<Node*> newTables; newTables.resize(2* _tables.size(), nullptr);//这里暂时使用2倍的方式扩容 for(size_t i = 0; i < _tables.size(); ++i)//遍历旧表，依次拿到每个桶的头节点 { Node* cur = _tables[i]; while(cur) { Node* next = cur->_next;//先使用一个指针保存next，以免更改cur指向之后找不到其他节点 size_t hashi = Hash()(cur->_kv.first) % newTables.size();//计算哈希位置 //头插到新表中 cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next;//迭代到next } _tables[i] = nullptr;//将旧表的内容置空，以免出现自动析构旧表的时候释放节点 } _tables.swap(newTables);//交换旧表和新表 } //插入 size_t hashi = Hash()(kv.first) % _tables.size();//定址 //头插 Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; }
删除
bool Erase(const K& key) { size_t hashi = Hash()(key) % _tables.size(); Node* prev = nullptr;//用prev存放当前节点的上一个节点，从而链接cur的前后节点 Node* cur = _tables[hashi]; while(cur) { if(cur->_kv.first == key)//找到了,准备删除 { if(_tables[hashi] == cur)//删除桶的头节点 { _tables[hashi] = cur->_next; } else//删除非头节点 { prev->_next = cur->_next; } delete cur; --_n; return true; } else//没找到 { prev = cur; cur = cur->_next; } } return false; }
查找
Node* Find(const K& key) { size_t hashi = Hash()(key) % _tables.size();//找到key对应的哈希地址 Node* cur = _tables[hashi];//遍历该地址对应的哈希桶 while(cur) { if(cur->_kv.first == key)//找到了 { return cur; } else//没找到 { cur = cur->_next; } } return nullptr; }
本节完……
