AI 助理
备案控制台
开发者社区 云原生 文章 正文

unordered_map和unordered_set的源码模拟实现

2023-11-01 58
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： unordered_map和unordered_set的源码模拟实现

在源码中，这两个STL容器都是共用一个框架的所以，我们就用一个框架实现两个

容器，代码细节都在注释上

HashTable.h

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <utility>
//namespace txh
//{
//  enum state
//  {
//    EMPTY,//空
//    EXITS,//存在
//    DELETE,//被删除
//  };
//  template<class K,class V>//元素类
//  class HashData//先画一个存放数据的蓝图，声明和定义
//  {
//  public:
//     std::pair<K,V> _kv;//哈希表，我们要根据key(也是模板的K)值去模一个值，得到哈希值存到哈希表的位置
//     //V是数据类型
//
//     //我们在查找的时候不知道用什么表示为空，没有一个合适的数，0吗，-1，不对，因为这些都有可能是某个数0，-1
//     //所以不能用，我们用另一种方法，那就是在每个数据上存一个标志代表是否为空
//
//     //前面定义了enum类型，类名是state，
//     state _state = EMPTY;//默认都是空
//  };
//
//
//
//  //线性探测法
//  template<class K,class V,class keyConv>
//  class HashTable
//  {
//  public:
//    typedef HashData<K, V> data;
//    keyConv kc;
//    HashTable()
//      :_n(0)
//    {
//      _table.resize(11);
//    }
//
//    //那如果key值不是int而是string 类型呢,我们不可能去特意在模板里判断一个数是否是string类型
//    //那么我们可以传一个模板,因为我们hash主要的是要把key值转换成hash值
//    //我们用一个模板类去封装转换成hash值的方式
//    bool insert(const std::pair<K,V>& kv)//插入元素,我们用pair类接受
//    {
//      //如果表内有相同的值的话，就不插入了
//      if (find(kv.first))
//      {
//        return false;
//      }
//
//      if (_n * 10 / _table.size() > 7)//负载因子大于0.7我们的冲突就会变大，导致效率下降
//        //在线性探测中，所以我们就需要扩容，扩多少倍呢，扩质数倍其实是很好的，java中只是扩2倍，没有按质数扩
//        //按质数扩会降低哈希冲突率
//      {
//        HashTable<K, V,keyConv> newtable;
//        newtable._table.resize(2 * _table.size());
//
//        for (auto& e:_table)//为什么要重新插入，是因为我们扩容之后，下标映射变了，所以要重新插入
//        {
//          if(e._state == EXITS)
//          {
//            /* int hashi = e._kv.first % newtable._table.size();
//             newtable._table[hashi]._kv = e._kv;
//             newtable._table[hashi]._state = e._state;*/
//            newtable.insert(e._kv);//复用写法
//          }
//        }
//        _table.swap(newtable._table);//2023年的现代写法,新表代替了旧表
//      }
//
//
//      //线性探测
//      size_t hashi = kc(kv.first) % _table.size(); //成员里不用capacity的原因是我们的vector的下标引用只能引用size内的值，capacity
//        //肯定大于等于size,所以肯定不能去模除capacity
//      size_t i = 0;
//      while (_table[hashi]._state != EMPTY)//查看当前表的每个元素类是否有空,没空一直继续
//      {
//        //如果当前的hashi被占了，直接去下一个厕所看(就是相邻的下一个)，所以有了i
//        //i控制每一轮要看的厕所不是上一次看过的，所以i++
//        ++hashi;
//        hashi %= _table.size();//防止越界
//      }
//      _table[hashi]._kv = kv;
//      _table[hashi]._state = EXITS;
//      ++_n;
//      return true;
//    }
//
//    data* find(const K& key)
//    {
//      size_t hashi = kc(key) % _table.size();
//      size_t i = 0;
//      while (_table[hashi]._state != EMPTY)//这是线性探测
//      {
//        if (_table[hashi]._kv.first == key
//          && _table[hashi]._state == EXITS)
//        {
//          return &_table[hashi];
//        }
//        hashi++;
//        hashi %= _table.size();//防止越界
//      }
//    
//      return nullptr;
//    }
//
//    bool erase(const K& key)
//    {
//      data* ret = find(key);
//      if (!ret)
//      {
//        return false;
//      }
//      else
//      {
//        ret->_state = DELETE;
//        _n--;
//        return true;
//      }
//    }
//  private:
//    std::vector<data> _table;//当前存放元素的表,
//    size_t _n;//代表当前表内有多少个元素
//    //负载因子是什么呢，就是总共插入的元素 除以 总元素 就是负载因子
//  };
//}
//
template <typename T>
struct HashFunc
{
  size_t operator()(const T& key)//键值接受
  {
    size_t hashi = key;
    return hashi;
  }
};//声明键值转换函数是模板类,因为模板类只是个图纸
template <>//特化之前一定要有一个基础类
struct HashFunc<std::string>
{
  size_t operator()(const std::string& key)
  {
    size_t hashi = 0;
    for (auto e : key)//关键值转hash
    {
      hashi *= 131;
      hashi += e;
    }
    return hashi;
  }
};
namespace HashBucket
{
  //开散列，拉链法
  template<class T>//改造后只有一个参数，我们自动去识别是一个参数还是两个参数
  struct HashNode
  {
    HashNode(const T& data) :_data(data), next(nullptr) {}
    T _data;
    HashNode* next;
  };
  template<class K, class T, class keyCon, class KeyofT>
  class HashTable;//在hashIterator类前面声明,编译器就会跟着这个声明去找到相应的模板
  //容器都有迭代器,所以我们要封装一个迭代器，因为我们的迭代器会有重载*，->这种，所以我们直接传ptr这种吧
  template<class K,class T,class Ref,class Ptr,class keyCon,class KeyofT>
  class _HashIterator
  {
  public:
    typedef HashNode<T> node;
    typedef _HashIterator<K, T, T&, T*, keyCon, KeyofT> iterator;
    typedef HashTable<K, T, keyCon, KeyofT> HT;
    _HashIterator(node* node1,HT* ht) :_node(node1),_ht(ht){}
    _HashIterator(const iterator& it):_node(it._node),_ht(it._ht){}
    typedef _HashIterator<K,T,Ref,Ptr,keyCon,KeyofT> self;
    self& operator++()
    {
      //先看当前桶里是否有元素，如果后续有元素，那就在桶里++，如果桶里没有，那么就去其他桶
      //里找
      node* cur = _node->next;
      if (cur)
      {
        _node = _node->next;
        //返回迭代器本身
      }
      else
      {
        //去遍历这个桶，找到后续第一个有元素的桶
        keyCon kc;
        //找到当前迭代器里的节点的桶的位置
        size_t hashi = kc(_node->_data) % _ht->_table.size();
        //遍历这个桶
        ++hashi;
        while (hashi < _ht->_table.size())
        {
          if (_ht->_table[hashi])
          {
            _node = _ht->_table[hashi];
            break;
          }
          hashi++;
        }
        if (hashi == _ht->_table.size())
        {
          _node = nullptr;
        }
      }
      return *this;
    }
    self operator++(int)
    {
      //后置++
      self ret = self(_node,_ht);
      node* cur = _node;
      if (cur)
      {
        _node = _node->next;
        //返回迭代器本身
      }
      else
      {
        //去遍历这个桶，找到后续第一个有元素的桶
        keyCon kc;
        //找到当前迭代器里的节点的桶的位置
        size_t hashi = kc(_node->_data) % _ht->_table.size();
        //遍历这个桶
        ++hashi;
        while (hashi < _ht->_table.size())
        {
          if (_ht->_table[hashi])
          {
            _node = _ht->_table[hashi];
            break;
          }
          hashi++;
        }
        if (hashi == _ht->_table.size())
        {
          _node = nullptr;
        }
      }
      return ret;//返回迭代器对象的时候，会进行拷贝构造，所以不用担心生命周期
    }
    bool operator!=(const self& s)
    {
      return s._node != _node;
    }
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr& operator->()
    {
      return &_node->_data;
    }
  public:
    node* _node;//有了迭代器，我们就可以直接用迭代器,迭代器++，就是这里的_node = _node->next等
    //我们的++，--操作还会设计到遍历桶，我们的遍历桶只在HashTable里面设计了,所以我们需要有一个
    //可以操作HashTable的动作，因为都是算类，我们可以设计一个指针进行操作,我们用友元
    HT* _ht;
  };
  //第二个才是数，第一个只是我们的键值
  template<class K, class T, class keyCon,class KeyofT>
  class HashTable
  {
  public:
    //友元声明
    template<class K,class T,class Ref,class Ptr,class KeyCon, class KeyofT>//声明这个_hashIterator是个模板类，告诉编译器我要这个_HashIterator模板类
    //是HashTable类的友元
    friend class _HashIterator;
    typedef _HashIterator<K,T,T&,T*,keyCon,KeyofT> iterator;
    typedef _HashIterator<K, T,const T&,const T*,keyCon,KeyofT> const_iterator;
    //我们通过传的模板参数来控制我们的迭代器是否是const迭代器
    typedef HashNode<T> node;
    keyCon hash;
    KeyofT koft;
    size_t _stl_next_prime(size_t size)
    {
      static const int __stl_num_primes = 28;
      static const unsigned long __stl_prime_list[__stl_num_primes] =
      {
        53, 97, 193, 389, 769,
        1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843,
        50331653, 100663319, 201326611, 402653189, 805306457,
        1610612741, 3221225473, 4294967291
      };
      //这里存放素数,为什么设素数为长度呢，因为在模素数的
      //时候，造成的哈希冲突会竟可能的好
      for (int i = 0;i < __stl_num_primes;i++)
      {
        if (__stl_prime_list[i] > size)
        {
          return  __stl_prime_list[i];
        }
      }
    }
    HashTable() :_n(0)
    {
      _table.resize(_stl_next_prime(_table.size()));
    }
    ~HashTable()
    {
      for (auto e : _table)
      {
        node* cur = e;
        while (cur)//把在桶里的元素删除
        {
          node* next = cur->next;
          delete cur;
          cur = next;
        }
        e = nullptr;
      }
    }
    iterator begin()
    {  
      node* cur = nullptr;
      //找到第一个有元素的桶
      for (size_t hashi = 0;hashi < _table.size();hashi++)
      {
        cur = _table[hashi];
        if (cur)
        {
          break;
        }
      }
      return iterator(cur,this);//传值返回,生命周期就不用管，他会执行一次拷贝构造
      //匿名构造函数
    }
    iterator end()
    {
      return iterator(nullptr, this);//传值返回,生命周期就不用管，他会执行一次拷贝构造
    }
    const_iterator begin() const
    {
      node* cur = nullptr;
      for (size_t i = 0; i < _table.size(); ++i)
      {
        cur = _table[i];
        if (cur)
        {
          break;
        }
      }
      return const_iterator(cur, this);
    }
    const_iterator end() const{return const_iterator(nullptr, this);}
    std::pair<iterator,bool> insert(const T& data)
    {
      iterator ret = find(koft(data));
      if (ret != end())//有该点的话
      {
        return std::make_pair(ret, true);
      }
      //拉链法中，当负载因子等于1的时候，哈希的冲突就会变大，桶里的元素可能最多，所以负载因子为1就扩容最好
      if (_n == _table.size())//负载因子等于1
      {
        /*HashTable<K, V, keyCon> newHash;*/
        /*newHash._table.resize(_table.size() * 2);*/
        //这种做法很费效率，因为每次插入要重新new一个节点，并释放，所以同样映射的节点就不需要重新new了
        std::vector<node*> newtable;
        /*newtable.resize(_table.size() * 2,nullptr);*/
        //扩容
        newtable.resize(_stl_next_prime(_table.size()));
        //重新映射
        for (auto& e : _table)
        {
          node* cur = e;
          //头插
          while (cur)
          {
            node* next = cur->next;
            //哈希重新映射
            size_t hashi = hash(koft(cur->_data)) % newtable.size();
            cur->next = newtable[hashi];//将未插入之前的头插到cur的next
            newtable[hashi] = cur;
            cur = next;
          }
          e = nullptr;
        }
        //现代写法
        _table.swap(newtable);//旧表换新表,只是表新表的内容搬到旧表中
        //新表不用手动释放,生命周期只在当前作用域中，如果出了作用域会自动销毁(调用析构函数)
      }
      //这里的kc是实例化后的对象，所以可以kc(kv.first)，但是不能用hash(kv.first)，因为hash不是一个实例化的对象，需要把他实例化
      //之后才能调用
      size_t hashi = hash(koft(data)) % _table.size();
      //头插
      node* newnode = new node(data);
      newnode->next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return std::make_pair(iterator(newnode,this),true);
    }
    iterator find(const K& key)
    {
      size_t hashi = hash(key) % _table.size();//根据关键值算出哈希值
      node* cur = _table[hashi];
      //在桶里寻找
      while (cur)
      {
        if (koft(cur->_data) == key)
        {
          return iterator(cur,this);
        }
        cur = cur->next;
      }
      return iterator(nullptr,this);
    }
    bool erase(const K& key)
    {
      size_t hashi = hash(key) % _table.size();
      node* cur = _table[hashi];//找到了桶
      node* prev = nullptr;
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          //如果是头节点的话
          if (cur->_kv == _table[hashi])
          {
            _table[hashi] = cur->next;
          }
          else//找到的这个key值不是头结点的话
          {
            prev->next = cur->next;
          }
          delete cur;
          --_n;
          return true;
        }
        else//继续找
        {
          prev = cur;
          cur = cur->next;
        }
      }
      return false;
    }
  private:
    std::vector<node*> _table;//每个位置存放hashnode类，里面有指针,存放的是头结点
    size_t _n;
  };
}
//先改造哈希表
//int main()
//{
//
//  /*txh::HashTable<int,int,> h1;*/
//
//  //h1.insert(std::make_pair(4,1));
//  //h1.insert(std::make_pair(4,1));
//  //h1.insert(std::make_pair(4,1));
//  //h1.insert(std::make_pair(3,1));
//
//  //h1.insert(std::make_pair(7,1));
//
//  /*txh::HashTable<std::string, int,HashFunc<std::string>> h1;
//  h1.insert(std::make_pair("苹果", 1));
//  h1.insert(std::make_pair("香蕉", 1));
//  h1.insert(std::make_pair("梨", 1));
//  h1.insert(std::make_pair("苹果", 1));
//  txh::HashData<std::string, int>* ret = h1.find("苹果");
//  ret->_kv.second++;
//  h1.erase("苹果");*/
//
//  HashBucket::HashTable<int, int, HashFunc<int>> h1;
//
//  h1.insert(std::make_pair(3, 1));
//  h1.insert(std::make_pair(4, 1));
//  h1.insert(std::make_pair(3, 1));
//  h1.insert(std::make_pair(3, 1));
//  h1.insert(std::make_pair(12, 1));
//  h1.insert(std::make_pair(12, 1));
//  return 0;
//}
template<class T>
struct compare
{
  bool operator()(const T& t1,const T& t2)
  {
    return t1 > t2;
  }
};

unordered_map.h

#pragma once
#include "HashTable.h"
#include "unordered_map.h"
#include "unordered_set.h"
#include <iostream>
namespace txh
{
  template<class K,class T,class keyCon = HashFunc<K>>
  class unordered_map
  {
  public:
    struct mapkeyoft
    {
      const K& operator()(const std::pair<K,T>& kv)
      {
        return  kv.first;
      }
    };
    typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::iterator iterator;
    typedef typename HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft>::const_iterator const_iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    const_iterator begin()const
    {
      return _ht.begin();
    }
    const_iterator end()const
    {
      return _ht.end();
    }
    std::pair<iterator, bool> insert(const std::pair<K, T>& data)
    {
      return _ht.insert(data);
    }
    T& operator[](const K& key)
    {
      std::pair<iterator, bool> ret = insert(std::make_pair(key
        , T));
      return ret.first->second;
      //加->就是得到了data,然后second
    }
    iterator find(const K& key)
    {
      return _ht.find(key);
    }
    bool erase(const K& key)
    {
      _ht.erase(key);
    }
  private:
    HashBucket::HashTable<K, std::pair<K, T>, keyCon, mapkeyoft> _ht;
  };
}

unordered_set.h

#pragma once
#include "HashTable.h"
#include <iostream>
#include <utility>
namespace txh
{
  template<class K,class keyCon = HashFunc<K>>
  class unordered_set
  {
    struct keyofset
    {
      const K& operator()(const K& data)
      {
        return data;
      }
    };
  public:
    typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::const_iterator iterator;
    typedef typename HashBucket::HashTable<K, K, keyCon, keyofset>::const_iterator const_iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    const_iterator begin()const
    {
      return _ht.begin();
    }
    const_iterator end()const
    {
      return _ht.end();
    }
    std::pair<iterator, bool> insert(const K& data) 
    {
      return _ht.insert(data);
    }
    iterator find(const K& data)
    {
      return _ht.find(data);
    }
    bool erase(const K& data)
    {
      return _ht.erase(data);
    }
  private:
    HashBucket::HashTable<K, K, keyCon, keyofset> _ht;
  };
}

test.cpp

 

#define  _CRT_SECURE_NO_WARNINGS 1
#include "unordered_map.h"
#include "unordered_set.h"
#include "HashTable.h"
#include <iostream>
#include <algorithm>
#include <utility>
int main()
{
  txh::unordered_set<int, HashFunc<int>> s1;
  s1.insert(1);
  return 0;
}
文章标签：
容器
C++
关键词：
map Set
unordered_map Set
Map源码
Map unordered_set
乖的小肥羊
目录
相关文章
Codelinghu
|
2月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
Codelinghu
81 0
Codelinghu
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
Codelinghu
67 0
刘大猫.
|
22天前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
57 18
你对Collection中Set、List、Map理解？
软件求生
|
16天前
|
存储 缓存 安全
只会“有序无序”？面试官嫌弃的List、Set、Map回答！
小米，一位热衷于技术分享的程序员，通过与朋友小林的对话，详细解析了Java面试中常见的List、Set、Map三者之间的区别，不仅涵盖了它们的基本特性，还深入探讨了各自的实现原理及应用场景，帮助面试者更好地准备相关问题。
软件求生
54 20
chian-ocean
|
1月前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对，每个键唯一；而`set`存储唯一元素，不包含值。两者均基于红黑树实现，支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口，并简要对比了`map`与`set`的主要差异。此外，还介绍了允许重复元素的`multiset`和`multimap`。
chian-ocean
32 3
【C++】map、set基本用法
chian-ocean
|
1月前
|
存储 算法 C++
【C++】unordered_map（set）
C++中的`unordered`容器（如`std::unordered_set`、`std::unordered_map`）基于哈希表实现，提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中，每个桶可存储一个或多个元素，以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列，以及迭代器。哈希函数用于计算元素的哈希值，冲突通过开链法解决，负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1)，但在冲突较多时可能退化为O(n)。
chian-ocean
23 5
html的七十二变
|
2月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中，Set 和 Map 用于存储唯一值和键值对，支持多种操作方法，如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象，有助于防止内存泄漏，适合特定场景使用。
html的七十二变
41 2
2的n次方_
|
3月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet（哈希表实现，无序且元素唯一）、LinkedHashSet（保持插入顺序的HashSet）、TreeSet（红黑树实现，自动排序）。Map系列为双列集合，键值一一对应，键不可重复，值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景，并提供了面试题示例，如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
2的n次方_
50 6
【数据结构】map&set详解
GuGuStudy
|
2月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别，以及Map与Set的关系
GuGuStudy
44 1
刘大猫.
|
3月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
42 5