AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)（下）

2024-05-29 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)

从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)（中）：https://developer.aliyun.com/article/1522331

2.2 封装unordered_set和unordered_map

       有了前面的经验（map的方括号重载要改insert的返回值），这里先把完整的unordered_set.h和unordered_map.h写出来，看看需要怎么改。封装就是套一层，还是很容易的：

完整unordered_map.h

#pragma once
 
#include "HashTable.h"
 
namespace rtx
{
  template<class K, class V, class Hash = HashFunc<K>>
  class unordered_map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
    typedef typename HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;
 
    iterator begin()
    {
      return _ht.begin();
    }
 
    iterator end()
    {
      return _ht.end();
    }
 
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _ht.Insert(kv); // 先看下面，所以insert要返回插入后的键值对
    }
 
    bool find(const K& key)
    {
      return _ht.Find(key);
    }
 
    bool erase(const K& key)
    {
      return _ht.Erase(key);
    }
 
    V& operator[](const K& key) // 根据原功能，返回的是键值对中key对应的value的引用。
    {   // 当key不存在时，operator[]用默认value与key构造键值对然后插入
      pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
      return ret.first->second;
    }
 
  protected:
    HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
  };
}

完整unordered_set.h

#pragma once
 
#include "HashTable.h"
 
namespace rtx
{
  template<class K, class Hash = HashFunc<K>>
  class unordered_set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;
 
    iterator begin()
    {
      return _ht.begin();
    }
 
    iterator end()
    {
      return _ht.end();
    }
 
    pair<iterator, bool> insert(const K& key) //和unordered_map保持一致
    {
      return _ht.Insert(key);
    }
 
    bool find(const K& key)
    {
      return _ht.Find(key);
    }
 
    bool erase(const K& key)
    {
      return _ht.Erase(key);
    }
  protected:
    HashTable<K, K, Hash, SetKeyOfT> _ht;
  };
}

2.3 修改哈希桶

       先给哈希桶的模板参数增加两个仿函数，用typedef封装迭代器，并给迭代器传对应的模板参数。还需要在哈希表中增加获取迭代器起始位置和结束位置的接口：


  • 在获取其实位置时，需要从头开始遍历哈希表项，寻找到第一个桶的头节点作为起始位置。
  • 使用空指针代替迭代器的结束位置。
  • 在构造迭代器时，直接传this指针去定义迭代器中的哈希表指针。

       在插入中，凡是使用到key值以及用key取模的地方，都要用仿函数取获得。包括删除和删除中也是，插入之前要查找下，先把查找改了：让其返回迭代器，如果存在，返回key所在位置的迭代器，如果不存在，返回末尾的迭代器。

  iterator Find(const K& key)
  {
    if (_tables.size() == 0)
    {
      return end();
    }
 
    Hash hs;
    KeyOfT kot;
    size_t hashi = hs(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur)
    {
      if (kot(cur->_data) == key)
      {
        return iterator(cur,this);
      }
      cur = cur->_next;
    }
    return end();
  }


然后修改哈希表的Inerst，返回由迭代器和布尔值组成的键值对。

  • 先进行查找，如果存在，则返回key所在位置的迭代器和false组成的键值对。
  • 查找结构不存在，则返回插入新节点后key所在位置的迭代器和true组成的键值对。
  pair<iterator, bool> Insert(const T& data)
  {
    KeyOfT kot;
    iterator ret = Find(kot(data));
    if (ret != end())
    {
      return make_pair(ret, false);
    }
 
    Hash hs;
    if (_size == _tables.size()) // 负载因子到1就扩容
    {
      //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      vector<Node*> newTables;
      //newTables.resize(newSize, nullptr);
      newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数，前两注释改成这一条
 
      for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
 
          size_t hashi = hs(kot(cur->_data) % newTables.size();
          cur->_next = newTables[hashi];
          newTables[hashi] = cur;
 
          cur = next;
        }
 
        _tables[i] = nullptr;
      }
 
      _tables.swap(newTables);
    }
 
    size_t hashi = hs((kot(data) % _tables.size(); // 哈希映射
    Node* newnode = new Node(data); // 头插
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_size;
    return make_pair(iterator(newnode, this), true);
  }

删除只需在移除用上KeyOfT仿函数，然后就改完了，程序就能跑起来了：

完整HashTable.h：

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
template<class T>
struct HashNode
{
  T _data;
  HashNode* _next; // 不用存状态栏了，存下一个结点指针
 
  HashNode(const T& data)
    :_data(data)
    , _next(nullptr)
  {}
};
 
template<class K>
struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了
{
  size_t operator()(const K& key)
  {
    return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行
  }
};
 
template<>
struct HashFunc<string> // 上面的特化
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (const auto& ch : key)
    {
      val *= 131;
      val += ch;
    }
 
    return val;
  }
};
 
template<class K, class T, class Hash, class KeyOfT>
class HashTable; // 前置声明
 
template<class K, class T, class Hash, class KeyOfT>
class __HashIterator
{
public:
  typedef HashNode<T> Node;
  typedef HashTable<K, T, Hash, KeyOfT> HT;
  typedef __HashIterator<K, T, Hash, KeyOfT> Self;
 
  Node* _node; // 数据结点
  HT* _pht; // 哈希表指针
 
  __HashIterator(Node* node, HT* pht)
    :_node(node)
    , _pht(pht)
  {}
 
  Self& operator++()
  {
    if (_node->_next) // 不是桶中的最后一个数据
    {
      _node = _node->_next;
    }
    else // 是桶中的最后一个数据，找下一个桶
    {
      Hash hs;
      KeyOfT kot;
      size_t i = hs(kot(_node->_data)) % _pht->_tables.size() + 1;//没+1是当前桶位置
      for (; i < _pht->_tables.size(); ++i)
      {
        if (_pht->_tables[i]) // 向后迭代找到了有桶的位置
        {
          _node = _pht->_tables[i]; // 把这个位置给_node
          break;
        }
      }
      if (i == _pht->_tables.size()) // 后面都没桶了
      {
        _node = nullptr;
      }
    }
    return *this; // this调用该函数的对象（迭代器），指向下一个后解引用返回
  }
 
  T& operator*()
  {
    return _node->_data;
  }
 
  T* operator->()
  {
    return &_node->_data;
  }
 
  bool operator!=(const Self& s) const
  {
    return s._node != _node;
  }
 
  bool operator==(const Self& s) const
  {
    return s._node == _node;
  }
};
 
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
public:
  template<class K, class T, class Hash, class KeyOfT>
  friend class __HashIterator;
 
  typedef HashNode<T> Node;
  typedef __HashIterator<K, T, Hash, KeyOfT> iterator;
 
  iterator begin()
  {
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      if (_tables[i])
      {
        return iterator(_tables[i], this); // 构造：(Node * node, HT * pht)
      }
    }
    return end();
  }
 
  iterator end()
  {
    return iterator(nullptr, this);
  }
 
  ~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;
    }
  }
 
  iterator Find(const K& key)
  {
    if (_tables.size() == 0)
    {
      return end();
    }
 
    Hash hs;
    KeyOfT kot;
    size_t hashi = hs(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur)
    {
      if (kot(cur->_data) == key)
      {
        return iterator(cur,this);
      }
      cur = cur->_next;
    }
    return end();
  }
 
  inline size_t __stl_next_prime(size_t n)
  {
    static const size_t __stl_num_primes = 28;
    static const size_t __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 (size_t i = 0; i < __stl_num_primes; ++i)
    {
      if (__stl_prime_list[i] > n)
      {
        return __stl_prime_list[i];
      }
    }
 
    return -1; // 不会走到这，随便返回一个值
  }
 
  pair<iterator, bool> Insert(const T& data)
  {
    KeyOfT kot;
    iterator ret = Find(kot(data));
    if (ret != end())
    {
      return make_pair(ret, false);
    }
 
    Hash hs;
    if (_size == _tables.size()) // 负载因子到1就扩容
    {
      //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      vector<Node*> newTables;
      //newTables.resize(newSize, nullptr);
      newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数，前两注释改成这一条
 
      for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
 
          size_t hashi = hs(kot(cur->_data)) % newTables.size();
          cur->_next = newTables[hashi];
          newTables[hashi] = cur;
 
          cur = next;
        }
 
        _tables[i] = nullptr;
      }
 
      _tables.swap(newTables);
    }
 
    size_t hashi = hs(kot(data)) % _tables.size(); // 哈希映射
    Node* newnode = new Node(data); // 头插
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_size;
    return make_pair(iterator(newnode, this), true);
  }
 
  bool Erase(const K& key)
  {
    if (_tables.size() == 0) // 防止除零错误
    {
      return false;
    }
 
    Hash hs;
    KeyOfT kot;
    size_t hashi = hs(key) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while (cur)
    {
      if (kot(cur->_data) == key)
      {
        if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个
        {
          _tables[hashi] = cur->_next;
        }
        else // 中间删
        {
          prev->_next = cur->_next;
        }
        delete cur; // 统一在这delete
        return true;
      }
 
      prev = cur; // 往后走
      cur = cur->_next;
    }
    return false; // 没找到
  }
 
  size_t Size() // 存的数据个数
  {
    return _size;
  }
 
  size_t TablesSize() // 表的长度
  {
    return _tables.size();
  }
 
  size_t BucketNum() // 桶的个数
  {
    size_t num = 0;
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      if (_tables[i]) // 如果不是空就有桶
      {
        ++num;
      }
    }
    return num;
  }
 
  size_t MaxBucketLenth() // 最长桶的长度
  {
    size_t maxLen = 0;
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      size_t len = 0;
      Node* cur = _tables[i];
      while (cur)
      {
        ++len;
        cur = cur->_next;
      }
      if (len > maxLen)
      {
        maxLen = len;
      }
    }
    return maxLen;
  }
 
protected:
  vector<Node*> _tables; // 指针数组
  size_t _size;
};

Test.cpp:

#include "UnorderedSet.h"
#include "UnorderedMap.h"
 
namespace rtx
{
  void test_unordered_set()
  {
    unordered_set<int> s;
    s.insert(2);
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(5);
 
    unordered_set<int>::iterator it = s.begin();
    //auto it = s.begin();
    while (it != s.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl << endl;;
  }
 
  void test_unordered_map()
  {
    unordered_map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    dict.insert(make_pair("string", "字符串"));
    dict.insert(make_pair("left", "左边"));
 
    unordered_map<string, string>::iterator it = dict.begin();
    while (it != dict.end())
    {
      cout << it->first << ":" << it->second << endl;
      ++it;
    }
    cout << endl;
 
    unordered_map<string, int> countMap;
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    for (const auto& e : arr)
    {
      countMap[e]++;
    }
 
    for (const auto& kv : countMap)
    {
      cout << kv.first << ":" << kv.second << endl;
    }
  }
}
 
int main()
{
  rtx::test_unordered_set();
  rtx::test_unordered_map();
 
  return 0;
}


3. 题外话+笔试选择题

       还有一些接口函数和仿函数参数这里并没有实现，正如以前说的，模拟实现不是为了造一个更好的轮子，而是理解它的底层实现。还有就是库里面unordered系列都提供了比较key相不相等的仿函数：

       本篇模拟实现的是直接调用的等于，这样就写死了，比如key是日期类的指针比较就是比较指针的地址了，但是我们想要比较的是指针指向的内容。所以应该是要加上这个仿函数的，我们以前写过类似的这里就不加上去了。

所以就会有下面的面试题：

笔试选择题1：关于unordered_map和unordered_set说法错误的是（）

A.它们中存储元素的类型不同，unordered_map存储键值对，而unordered_set中只存储key


B.它们的底层结构相同，都使用哈希桶


C.它们查找的时间复杂度平均都是O(1)


D.它们在进行元素插入时，都得要通过key的比较去找待插入元素的位置


笔试选择题2：关于unordered_map和unordered_set说法错误的是（）


A.它们中都存储的键值对


B.map适合key有序的场景，unordered_map没有有序的要求


C.它们中元素查找的方式相同


D.map的底层结构是红黑树，unordered_map的底层结构是哈希桶


答案及解析：


笔试选择题1：


A：正确，参考unordered_map和unordered_set的文档说明


B：正确，都采用的是哈希桶来实现的


C：正确，哈希是通过哈希函数来计算元素的存储位置的，找的时候同样通过哈希函数找元素位 置，不需要循环遍历因此时间复杂度为O(1)


D：错误，不需要比较，只需要通过哈希函数，就可以确认元素需要存储的位置


选D


笔试选择题2：


A：正确，结合文档说明


B：正确，因为map的底层是红黑树，红黑树中序遍历可以得到关于key有序的序列，而unordered _map底层是哈希     桶，哈希对于其存储的元素是否有序，并不关心


C：错误，map按照二叉搜索树的规则查找，unordered_map按照哈希方式进行查找


D：正确

选C

本篇完。

       下一篇也是高阶数据结构的内容：从C语言到C++_32（哈希的应用）位图bitset+布隆过滤器+哈希切割。

文章标签：
C语言
存储
关键词：
C语言C++
C语言封装
C++ c语言
C++封装
C++哈希
GR鲸鱼
目录
相关文章
LuckiBit
|
1天前
|
算法 编译器 C语言
【C语言】C++ 和 C 的优缺点是什么？
C 和 C++ 是两种强大的编程语言，各有其优缺点。C 语言以其高效性、底层控制和简洁性广泛应用于系统编程和嵌入式系统。C++ 在 C 语言的基础上引入了面向对象编程、模板编程和丰富的标准库，使其适合开发大型、复杂的软件系统。 在选择使用 C 还是 C++ 时，开发者需要根据项目的需求、语言的特性以及团队的技术栈来做出决策。无论是 C 语言还是 C++，了解其优缺点和适用场景能够帮助开发者在实际开发中做出更明智的选择，从而更好地应对挑战，实现项目目标。
LuckiBit
14 0
c的前世今生
|
2月前
|
C语言 C++
C 语言的关键字 static 和 C++ 的关键字 static 有什么区别
在C语言中，`static`关键字主要用于变量声明，使得该变量的作用域被限制在其被声明的函数内部，且在整个程序运行期间保留其值。而在C++中，除了继承了C的特性外，`static`还可以用于类成员，使该成员被所有类实例共享，同时在类外进行初始化。这使得C++中的`static`具有更广泛的应用场景，不仅限于控制变量的作用域和生存期。
c的前世今生
59 10
石小浪♪
|
2月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装，包括节点的创建、链表的初始化、数据的插入和删除，以及链表的打印等功能。
石小浪♪
19 1
刘大猫.
|
3月前
|
算法
你对Collection中Set、List、Map理解？
你对Collection中Set、List、Map理解？
刘大猫.
38 5
周一同学Zelina
|
3月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法，并探讨了它们在前端开发中的具体应用，包括如何利用这些数据结构来解决常见的编程问题。
周一同学Zelina
33 0
ES6的Set和Map你都知道吗？一文了解集合和字典在前端中的应用
Codelinghu
|
2月前
|
C语言 C++
实现两个变量值的互换[C语言和C++的区别]
实现两个变量值的互换[C语言和C++的区别]
Codelinghu
23 0
aliyun1792367740-35101
|
2月前
|
存储 算法 C++
【算法】哈希映射（C/C++）
【算法】哈希映射（C/C++）
aliyun1792367740-35101
36 0
枫叶丹4
|
4月前
|
存储 搜索推荐 Serverless
【C++航海王：追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
【C++航海王：追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
枫叶丹4
37 1
可能只会写BUG
|
3月前
|
编译器 C语言 C++
从C语言到C++
本文档详细介绍了C++相较于C语言的一些改进和新特性，包括类型检查、逻辑类型 `bool`、枚举类型、可赋值的表达式等。同时，文档还讲解了C++中的标准输入输出流 `cin` 和 `cout` 的使用方法及格式化输出技巧。此外，还介绍了函数重载、运算符重载、默认参数等高级特性，并探讨了引用的概念及其应用，包括常引用和引用的本质分析。以下是简要概述： 本文档适合有一定C语言基础的学习者深入了解C++的新特性及其应用。
可能只会写BUG
20 0
游客ot6eft3qn37ga
|
4月前
|
存储 JavaScript 前端开发
ES6新特性（四）: Set 和 Map
ES6新特性（四）: Set 和 Map
游客ot6eft3qn37ga
45 1

热门文章

最新文章

  • 1
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    C语言标准库（常用函数）详解（含示例）数学公式：math.h
  • 4
    C语言四舍五入计算方法（包含各种精度）
  • 5
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 6
    C语言预处理之二-----宏定义那点事儿
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    四则运算表达式求值程序(C语言版)
  • 10
    C语言及程序设计提高例程-26 实现线性表基本操作的函数
  • 1
    Go语言map并发安全，互斥锁和读写锁谁更优？
    60
  • 2
    Go语言map并发安全使用的正确姿势
    65
  • 3
    Go语言中的map为什么默认不是并发安全的？
    63
  • 4
    【C++】开散列实现unordered_map与unordered_set的封装
    57
  • 5
    【C++】map和set封装
    40
  • 6
    Kotlin小技巧之用Transformations.map方法转换LiveData
    59
  • 7
    Java基础之集合Map
    42
  • 8
    Java Map集合：选择正确的实现方式
    52
  • 9
    算法金 | 推导式、生成器、向量化、map、filter、reduce、itertools，再见 for 循环
    55
  • 10
    js【最佳实践】遍历数组的八种方法（含数组遍历 API 的对比）for,forEach,for of,map,filter,reduce,every,some
    81

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • C++ 入门教程开发文档
  • 你的第一门C语言课
  • C语言学习教程

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月