unordered_map 和 unordered_set-阿里云开发者社区

unordered —— 无序的，从表面上来看，与 map 和 set 不同之处就在于，unordered_map 和 unordered_set 无法保证插入数据是有序的；

尽管如此，由于这两种容器内部封装了“哈希桶”，可以实现快速查找数据 —— 这一优点与 map 和 set 相同。

其实，除了内部结构的不同外，其余与 map 和 set 没什么不同，一样的 insert、find、erase … … 在我们模拟过 map set 的基础上，再学习封装无序map 和无序set 实在简单。

因此，本文的重点在于迭代器的运行逻辑 —— operator++() ，和理解模板、仿函数等。

最后，补充一个概念：

哈希 是一种思想，将传入的数据映射成一个或多个整型；哈希表 / 哈希桶 则是一种实现哈希思想的结构。

一、改造哈希桶

1.1 初步搭建 HashTable

// 改造 HashNode
  template<class T> 
    struct HashNode
    {
        HashNode<T>* _next; 
        T _data;
        
        HashNode(const T& data)
            :_next(nullptr)
            ,_data(data)
        {}
    };
  // 改造 HashTable
    // 此处 HashFunc 与《开散列哈希桶》中提供的无异
  // KeyOfT 与 map set 中的无异，都是用于从 T 中取到键值 
  template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> 
    class HashTable
    {
    public:
        typedef HashNode<T> Node;
    
    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };

1.2 数据插入数据查找

数据插入 —— Insert()

pair<iterator, bool> Insert(const T& data)
    {
        KeyOfT kot;
        iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
        if (ret != end())// 找到了
        {
            return make_pair(ret, false);
        }
        
        // 扩容 
        // ... 
        
        // 插入
        Hash hs;
        size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
        Node* newNode = new Node(data);
        newNode->_next = _tables[hashi];
        _tables[hashi] = newNode;
        _n++;
        
        return make_pair(new_iterator, true); // 此处为伪代码！
  }

与普通哈希桶不同的地方在于此： size_t hashi = hs(kot(data)) % _tables.size(); // kot(data) -- 取键值；hs(键值) -- 计算映射值 ，多套了一层仿函数。

PS：

扩容逻辑与哈希桶完全一致。
return make_pair(new_iterator, true); 为伪代码，用 new_iterator 代表插入节点的迭代器 —— 后面介绍迭代器时，会将这里的坑填上！

数据查找 —— Find()

很多新手不理解为什么在封装 map set 要这样构造 —— 好像传入了两个 Key ：

map: RBTree<K, pair<const K, V>, ... > _t;

set: RBTree<K, const K, ...> _t;

我们通常是 t.find(key1); t,erase(key2); 这种方式使用 find() 和 erase() ，无论 t 是 map 还是 set。

意思就是，第一个模板参数 K 是为了解决 map 的查找和删除等的问题。

iterator Find(const K& key)
    {
        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; // 这里同样是伪代码！
            }
            cur = cur->_next;
        }
        return iterator_nullptr;// 伪代码
    }

iterator_cur 代表 cur 位置的迭代器； iterator_nullptr 代表空迭代器，这两个迭代器的空白会在后面填补。

二、迭代器封装 __Hash_Iterator

__Hash_Iterator 内部应该传入什么呢？节点的指针吗？哈希桶的指针吗？

我们希望可以通过迭代器遍历整个哈希桶，同时要能取到当前迭代器所在节点的数据，因此，迭代器内部应有节点的指针和哈希桶的指针。

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> 
    struct __Hash_Iterator
    {
        typedef HashNode<T> Node;
        typedef HashTable<K, T, KeyOfT, Hash> HashTable;
        typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;
        
        Node* _node;
        HashTable* _ht;
        
        __Hash_Iterator(Node* node, HashTable* ht)
          :_node(node)
            ,_ht(ht)
        {}
    };

2.1 operator++()

operator++() 需要考虑两种情形：

_node->_next 不为空，++ 后，_node = _node->_next
_node->_next 为空，则往后遍历 HashTable，直到找到下一个不为空的位置，或者遍历完整个 HashTable 。

Self& operator++()
    {
        if (_node->_next)
        {
            _node = _node->_next;
        }
        else 
        {
            Hash hs;
            KeyOfT kot;
            size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
            hashi++; // 从当前位置的后一个位置开始查找
            while (hashi < _ht->_tables.size())
            {
                if (_ht->_tables[hashi])
                {
                    // 找到下一个位置，跳出循环
                    _node = _ht->_tables[hashi]; 
                    break;
                }
                ++hashi;
            }
            if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点
            {
                _node = nullptr;
            }
        }
        return *this;
    }

2.2 operator!=() operator*() operator->()

bool operator!=(const Self& s)
    {
        return _node != s._node;
    }
  T& operator*()
    {
        return _node->_data;
  }
  T* operator->()
    {
        return &_node->_data;
  }

2.3 完善 HashTable

针对第一部分中迭代器遗留问题，在这里将其完善。

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> 
    class HashTable
    {
    public:
        typedef HashNode<T> Node;
        typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;
        
        pair<iterator, bool> Insert(const T& data)
        {
            KeyOfT kot;
            Hash hs;
            iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
            if (ret != end())// 找到了
            {
                return make_pair(ret, false);
            }
            // 扩容 
            if (_n == _tables.size())
      {
        vector<Node*> newTables(_tables.size() * 2, 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(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
            Node* newNode = new Node(data);
            newNode->_next = _tables[hashi];
            _tables[hashi] = newNode;
            _n++;
            return make_pair(iterator(newNode, this), true); // 
        }
        
        iterator Find(const K& key)
        {
            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 iterator(nullptr, this);
        }
        
        bool Erase(const K& key)
        {
            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]
                    {
                        _tables[hashi]->_next = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
    
    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };

2.4 begin() end()

iterator begin()
    {
        for (size_t i = 0; i < _tables.size(); i++)
        {
            if (_tables[i])
            {
                return iterator(_tables[i], this);
      }
        }
        return iterator(nullptr, this);
    }
  iterator end()
    {
        return iterator(nullptr, this);
    }

三、`unordered_map` `unordered_set` 封装

unordered_map

template<class K, class V, class Hash = HashFunc<K>>
  class unordered_map
  {
  public:
    struct MapKeyOfT
    {
      K operator()(const pair<K, V>& kv)
      {
        return kv.first;
      }
    };
    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _ht.Insert(kv);
    }
    iterator find(const K& key)
    {
      return _ht.Find(key);
    }
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    V& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
  };

unordered_set

template<class K, class Hash = HashFunc<K>>
  class unordered_set
  {
  public:
    struct SetKeyOfT
    {
      K operator()(const K& key)
      {
        return key;
      }
    };
    typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _ht.Insert(key);
    }
    iterator find(const K& key)
    {
      return _ht.Find(key);
    }
  private:
    HashTable<K, const K, SetKeyOfT, Hash> _ht;
  };

注意：

如果直接将以上代码在 VS 中运行，会出现以下几个错误：

该问题的原因是，在 __Hash_Iterator 之前并未声明 HashTable 。

template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
  class HashTable; // 声明
  template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
  struct __Hash_Iterator
  {
        // ...
    };

该问题在于，__Hash_Iterator 无法访问 HashTable 的 private 成员变量，解决办法是将 __Hash_Iterator 写成 HashTable 的友元类。

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
  class HashTable
  {
  public:
    template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
    friend struct __Hash_Iterator; // 友元
        // ...
    };

四、完整代码

My_Unordered_Map.h

#include "HashTable.h"
namespace MY_Test
{
  template<class K, class V, class Hash = HashFunc<K>>
  class unordered_map
  {
  public:
    struct MapKeyOfT
    {
      K operator()(const pair<K, V>& kv)
      {
        return kv.first;
      }
    };
    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _ht.Insert(kv);
    }
    iterator find(const K& key)
    {
      return _ht.Find(key);
    }
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    V& operator[](const K& key)
    {
      pair<iterator, bool> ret = insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
  };
  void test_map1()
  {
    unordered_map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    dict.insert(make_pair("left", "左边"));
    dict.insert(make_pair("right", "右边"));
    for (auto& kv : dict)
    {
      //kv.first += 'x';
      kv.second += 'y';
      cout << kv.first << ":" << kv.second << endl;
    }
  }
  void test_map2()
  {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
  "苹果", "香蕉", "苹果", "西瓜", "香蕉", "草莓" };
    unordered_map<string, int> countMap;
    for (auto& e : arr)
    {
      /*if (e == "ݮ")
      {
        int i = 0;
      }*/
      countMap[e]++;
    }
    for (auto& kv : countMap)
    {
      cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;
  }
}

My_Unordered_Set.h

#include "HashTable.h"
namespace MY_Test
{
  template<class K, class Hash = HashFunc<K>>
  class unordered_set
  {
  public:
    struct SetKeyOfT
    {
      K operator()(const K& key)
      {
        return key;
      }
    };
    typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _ht.Insert(key);
    }
    iterator find(const K& key)
    {
      return _ht.Find(key);
    }
  private:
    HashTable<K, const K, SetKeyOfT, Hash> _ht;
  };
  void test_set1()
  {
    unordered_set<int> us;
    us.insert(3);
    us.insert(1);
    us.insert(5);
    us.insert(15);
    us.insert(45);
    us.insert(7);
    unordered_set<int>::iterator it = us.begin();
    while (it != us.end())
    {
      //*it += 100;
      cout << *it << " ";
      ++it;
    }
    cout << endl;
     for (auto e : us)
    {
      cout << e << " ";
    }
    cout << endl;
  }
}

HashTable.h

#include <vector>
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        size_t hash = key;
        return hash;
    }
};
template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto e : s)
        {
            hash = hash * 131 + e;
        }
        return hash;
    }
};
template<class T>
struct HashNode
{
    HashNode<T>* _next;
    T _data;
    HashNode(const T& data)
        :_next(nullptr)
        , _data(data)
    {}
};
template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
class HashTable; // 声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
struct __Hash_Iterator
{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, KeyOfT, Hash> HashTable;
    typedef __Hash_Iterator<K, T, KeyOfT, Hash> Self;
    Node* _node;
    HashTable* _ht;
    __Hash_Iterator(Node* node, HashTable* ht)
        :_node(node)
        , _ht(ht)
    {}
    Self& operator++()
    {
        if (_node->_next)
        {
            _node = _node->_next;
        }
        else
        {
            Hash hs;
            KeyOfT kot;
            size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();
            hashi++; // 从当前位置的后一个位置开始查找
            while (hashi < _ht->_tables.size())
            {
                if (_ht->_tables[hashi])
                {
                    // 找到下一个位置，跳出循环
                    _node = _ht->_tables[hashi];
                    break;
                }
                ++hashi;
            }
            if (hashi == _ht->_tables.size()) // 遍历结束，没有下一个节点
            {
                _node = nullptr;
            }
        }
        return *this;
    }
    bool operator!=(const Self& s)
    {
        return _node != s._node;
    }
    T& operator*()
    {
        return _node->_data;
    }
    T* operator->()
    {
        return &_node->_data;
    }
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:
    typedef HashNode<T> Node;
    typedef __Hash_Iterator<K, T, KeyOfT, Hash> iterator;
    template<class K, class T, class KeyOfT, class Hash> // 不能加缺省值
    friend struct __Hash_Iterator; // 友元
    HashTable()
    {
        _tables.resize(10);
    }
    pair<iterator, bool> Insert(const T& data)
    {
        KeyOfT kot;
        Hash hs;
        iterator ret = Find(kot(data)); // 未实现的 Find，返回值为 iterator
        if (ret != end())// 找到了
        {
            return make_pair(ret, false);
        }
        // 扩容 
        if (_n == _tables.size())
        {
            vector<Node*> newTables(_tables.size() * 2, 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(); // kot(data) -- 取键值；hs(键值) -- 计算映射值
        Node* newNode = new Node(data);
        newNode->_next = _tables[hashi];
        _tables[hashi] = newNode;
        _n++;
        return make_pair(iterator(newNode, this), true); // 
    }
    iterator Find(const K& key)
    {
        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 iterator(nullptr, this);
    }
    bool Erase(const K& key)
    {
        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]
                {
                    _tables[hashi]->_next = cur->_next;
                }
                else
                {
                    prev->_next = cur->_next;
                }
                delete cur;
                --_n;
                return true;
            }
            prev = cur;
            cur = cur->_next;
        }
        return false;
    }
    iterator begin()
    {
        for (size_t i = 0; i < _tables.size(); i++)
        {
            if (_tables[i])
            {
                return iterator(_tables[i], this);
            }
        }
        return iterator(nullptr, this);
    }
    iterator end()
    {
        return iterator(nullptr, this);
    }
private:
    vector<Node*> _tables;
    size_t _n = 0;
};

unordered_map 和 unordered_set

一、改造哈希桶

1.1 初步搭建 HashTable

1.2 数据插入数据查找

二、迭代器封装 __Hash_Iterator

2.1 operator++()

2.2 operator!=() operator*() operator->()

2.3 完善 HashTable

2.4 begin() end()

三、`unordered_map` `unordered_set` 封装

注意：

四、完整代码

My_Unordered_Map.h

My_Unordered_Set.h

HashTable.h

热门文章

最新文章

相关课程

相关电子书

unordered_map 和 unordered_set

一、改造哈希桶

1.1 初步搭建 HashTable

1.2 数据插入 数据查找

二、迭代器封装 __Hash_Iterator

2.1 operator++()

2.2 operator!=() operator*() operator->()

2.3 完善 HashTable

2.4 begin() end()

三、unordered_map unordered_set 封装

注意：

四、完整代码

My_Unordered_Map.h

My_Unordered_Set.h

HashTable.h

热门文章

最新文章

相关课程

相关电子书

1.2 数据插入数据查找

三、`unordered_map` `unordered_set` 封装