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

哈希表的底层实现(2)---C++版

news 2025/6/25 22:35:25

链地址法Separate Chaining——哈希桶的模拟实现

超大重点分析：

两种方法对比

由于在上次的哈希表的底层实现(1)---C++版已经详细的阐述了相关的结构和原理，哈希表的实现方法主要分为链地址法和开放定址法。开放定址法上次已经实现过了，这次我们实现一下链地址法。

链地址法Separate Chaining——哈希桶的模拟实现

哈希桶的结构和链表是完全一样的，我们这边选择在每个vector里面装入单链表就可以了，比较简单嘛，所以每个结点和成员都是指针。

#include<iostream>
#include<vector>
using namespace std;

template<class K>
struct Hashfunc//仿函数
{
   int operator()(const K& key)
   {
       return (int)key;
   }
};

struct Hashfunc<string>//结构体名字必须一致才省略模板
{
   int operator()(const string& key)
   {
       int hashi = 0;
       for (auto e : key)
       {
           hashi = hashi * 31;
           hashi = hashi + e;
       }
       return hashi;
   }
};
template<class K, class V>
struct Hashnode
{
   pair<K, V> _kv;
   Hashnode<K, V>* _next;
   Hashnode(const pair<K, V>& kv)
       :_kv(kv)
       ,_next(nullptr)
   {}
};

template<class K, class V, class hash = Hashfunc<K>>
class Hashtable
{
   typedef Hashnode<K, V> node;
public:
   Hashtable()
   {
       _tables.resize(10, nullptr);//先初始化存有10个空指针的数组
   }
   ~Hashtable()//需要自己写析构函数的
   {
       for (int i = 0; i < _tables.size(); i++)
       {
           node* cur = _tables[i];
           while (cur)
           {
               node* next = cur->_next;
               delete cur;
               cur = next;
           }
           _tables[i] = nullptr;

}
}

   bool Insert(const pair<K, V>& kv)
   {
       hash ha;
       // 负载因子==1扩容
       if (n == _tables[size])
       {
           /*Hashtable<K, V> newHT;
           newHT._tables.resize(_tables.size() * 2);
           for (size_t i = 0; i < _tables.size(); i++)
           {
               node* cur = _tables[i];
               while(cur)
               {
                   newHT.Insert(cur->_kv);//用以前复用的逻辑有点浪费空间了
                   cur = cur->_next;
               }
           }*/
           vector<node*>newht.resize(_tables.size() * 2, nullptr);
           for (int i = 0; i < _tables.size(); i++)
           {
               node* cur = _tables[i];
               while (cur)
               {
                   node* next = cur->_next;
                   // 旧表中节点，挪动新表重新映射的位置
                   size_t hashi = ha(cur->_kv.first) % newht.size();
                   // 头插到新表，当然使用尾插也可以
                   cur->_next = newht[hashi];//头插的逻辑
                   newht[hashi] = cur;
                   cur = next;
               }
               _tables[i] = nullptr;//置空了头结点后面的结点也就找不到了，其实感觉不置空也没什么问题
           }
           _tables.swap(newht);//再交换一下
       }
       size_t hashi = ha(kv.first) % _tables.size();
       //头插
       node* newnode = new(kv);//通过kv构造一个新结点，需要合适的构造函数
       newnode->_next = _tables[hashi];
       _tables[hashi] = newnode;
       n++;
   }

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

   bool Erase(const K& key)
   {
       hash ha;
       if (Find(key) == nullptr)
       {
           return false;
       }
       else
       {
           size_t hashi =ha(K) % _tables.size();
           node* cur = _table[hashi];
           node* prev = nullptr;
           while (cur)
           {
               if (cur->_kv.first == key)
               {
                   if (prev == nullptr)
                   {
                       _tables[hashi] = cur->_next;
                   }
                   else
                   {
                       prev->_next = cur->_next;
                   }
                   delete cur;
                   cur = nullptr;
                   --n;
                   return true;
               }
               prev = cur;
               cur = cur->_next
           }
       }
   }
private:
   vector<node*> _tables;// 使用指针数组
   size_t n = 0;//负载因子
};

超大重点分析：

为什么需要自己写析构函数呢？因为如果让系统调用默认构造的话，成员中负载因子属于内置类型编译器不处理，然后vector属于自定义类型，编译器会调用vector的默认构造，这样vector里面的单链表就没有办法析构了，就会照成内存泄漏。

为什么扩容不复用insert了呢，先说一下为什么会需要扩容，随着数据的不断大量的插入单链表，肯定在某种情况下会使得某个链表过于长，这样在查找哈希表的时候会使得时间复杂度过于大了，所以引入负载因子n进行控制，当n == size时就扩容，为什么在扩容时不建议复用呢，因为这样不断的创造新的结点而放着旧结点不直接拿来用的话会比较浪费空间，创造一个结点的消耗还是比较大的。