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

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

2024-05-29 20
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从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++ set
C++封装
C++哈希
GR鲸鱼
目录
相关文章
落雨便归尘
|
1天前
|
存储 Linux C语言
c++进阶篇——初窥多线程(二) 基于C语言实现的多线程编写
本文介绍了C++中使用C语言的pthread库实现多线程编程。`pthread_create`用于创建新线程，`pthread_self`返回当前线程ID。示例展示了如何创建线程并打印线程ID，强调了线程同步的重要性，如使用`sleep`防止主线程提前结束导致子线程未执行完。`pthread_exit`用于线程退出，`pthread_join`用来等待并回收子线程，`pthread_detach`则分离线程。文中还提到了线程取消功能，通过`pthread_cancel`实现。这些基本操作是理解和使用C/C++多线程的关键。
落雨便归尘
12 7
长梦
|
2天前
|
存储 算法 NoSQL
C++一分钟之-map与set容器详解
【6月更文挑战第21天】C++ STL的`map`和`set`是基于红黑树的关联容器，提供有序存储和高效查找。`map`存储键值对，键唯一，值可重复；`set`仅存储唯一键。两者操作时间复杂度为O(log n)。常见问题包括键的唯一性和迭代器稳定性。自定义比较函数可用于定制排序规则，内存管理需注意适时释放。理解和善用这些工具能提升代码效率。
长梦
10 3
快乐的流畅
|
4天前
|
存储 编译器 C++
【C++练级之路】【Lv.17】【STL】set类和map类的模拟实现
用改造后的红黑树，模拟实现set和map
快乐的流畅
25 4
知更鸟呆呆
|
9天前
|
C语言 C++ 编译器
【C++语言】冲突-C语言：输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言：输入输出、缺省参数、引用、内联函数
知更鸟呆呆
22 0
【C++语言】冲突-C语言：输入输出、缺省参数、引用、内联函数
知更鸟呆呆
|
9天前
|
C语言 C++
【C++语言】冲突-C语言：命名空间
【C++语言】冲突-C语言：命名空间
知更鸟呆呆
12 0
芯动大师
|
16天前
|
存储 C++ 容器
c++实现哈希桶
这篇文章回顾了闭散列的概念，指出在数据冲突时，闭散列会自动寻找后续未占用的位置插入数据。然而，这种方法可能导致某些元素状态变为删除，从而在查找时产生问题。为了解决这个问题，文章介绍了拉链法（哈希桶）作为改进策略。拉链法在每个哈希表位置上维护一个链表，冲突的数据挂载在相应位置的链表上。文章详细描述了拉链法的插入、查找和删除操作，并提供了相关代码示例。在插入过程中，当负载因子达到1时，哈希表会进行扩容，同时避免了频繁创建和销毁节点，提高了效率。最后，文章通过测试代码展示了拉链法的正确性。
芯动大师
12 0
sky_qiyi
|
16天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题（经典的笔试题）、C/C++中程序内存区域划分
C语言学习记录——动态内存习题（经典的笔试题）、C/C++中程序内存区域划分
sky_qiyi
23 0
GR鲸鱼
|
24天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)（下）
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
GR鲸鱼
23 0
aliyun5297948689-49597
|
3天前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`，它们是高效处理集合数据的工具。`Map`允许任何类型的键，提供唯一键值对；`Set`存储唯一值。使用`Map`时，注意键可以非字符串，用`has`检查键存在。`Set`常用于数组去重，如`[...new Set(array)]`。了解它们的高级应用，如结构转换和高效查询，能提升代码质量。别忘了`WeakMap`用于弱引用键，防止内存泄漏。实践使用以加深理解。
aliyun5297948689-49597
26 3
蓝色流星86
|
11天前
|
存储 安全 Java
Java集合详解：Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素，如ArrayList（适合读取）和LinkedList（适合插入删除）。Set不允许重复，有HashSet（无序）和TreeSet（排序）。Map存储键值对，HashMap（无序）和TreeMap（排序）。Vector是线程安全的ArrayList替代品，但在多线程环境下使用。选择集合类型应根据应用场景，如有序、无序、键值对需求及线程安全考虑。
蓝色流星86
21 3