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

简介: 从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+布隆过滤器+哈希切割。

目录
相关文章
|
8天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
11 2
|
15天前
|
存储 算法 C++
C++一分钟之-扁平化映射与unordered_map
【7月更文挑战第5天】C++的STL `unordered_map`是键值对的快速查找容器,基于哈希表。常见问题包括哈希函数选择、键类型限制、内存管理和迭代顺序不确定性。要避免问题,需优化哈希函数,确保自定义类型支持哈希和比较操作,合理管理内存,不依赖迭代顺序。提供的代码示例展示了如何为自定义类型定义哈希函数并操作`unordered_map`。正确使用能提升代码效率。
23 0
C++一分钟之-扁平化映射与unordered_map
|
17天前
|
存储 开发框架 Java
|
8天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
14 0
|
24天前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
22 1
|
1月前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`,它们是高效处理集合数据的工具。`Map`允许任何类型的键,提供唯一键值对;`Set`存储唯一值。使用`Map`时,注意键可以非字符串,用`has`检查键存在。`Set`常用于数组去重,如`[...new Set(array)]`。了解它们的高级应用,如结构转换和高效查询,能提升代码质量。别忘了`WeakMap`用于弱引用键,防止内存泄漏。实践使用以加深理解。
|
10天前
|
存储 安全 Java
Java基础之集合Map
【7月更文挑战第8天】Java中的Map集合以键值对方式存储数据,如`Map&lt;&quot;name&quot;, &quot;张三&quot;&gt;`。Map接口定义了存取、判断、移除等操作,包括`put`、`get`、`containsKey`等方法。HashMap是最常用的实现,基于哈希表,允许null键值,但不保证顺序。其他实现包括同步的Hashtable、处理属性文件的Properties、保持插入顺序的LinkedHashMap、基于红黑树的TreeMap、弱引用的WeakHashMap、并发安全的ConcurrentHashMap和针对枚举优化的EnumMap。
17 4
|
25天前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
17 1
|
11天前
|
存储 安全 Java
Java Map集合:选择正确的实现方式
Java Map集合:选择正确的实现方式
|
1月前
|
存储 缓存 Java
Java遍历Map集合的方法
在Java中,遍历Map集合主要有四种方式:1) 使用`keySet()`遍历keys并用`get()`获取values;2) 使用`entrySet()`直接遍历键值对,效率较高;3) 通过`Iterator`遍历,适合在遍历中删除元素;4) Java 8及以上版本可用`forEach`和Lambda表达式,简洁易读。`entrySet()`通常性能最佳,而遍历方式的选择应考虑代码可读性和数据量。
34 0