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

1. unordered_set和unordered_map

       在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到（logN），即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，其底层结构是前一篇讲的哈希结构，本文中只对unordered_set和unordered_map进行介绍，

       unordered_multiset和unordered_multimap可查看文档介绍。unordered系列和前面学习的map和set几乎一模一样，只是多了前面的unordered。正如它的名字一样，unordered系列和map/set比起来，unordered系列打印出来的数据是无序的。

1.1 unordered_map

1. unordered_map是存储键值对的关联式容器，其允许通过keys快速索引到与其对应的value。

2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部, unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[ ])，它允许使用key作为参数直接访问value。

6. 它的迭代器至少是前向迭代器。

常用接口函数：可以参考map的函数使用，还有一些关于哈希的接口后面再讲解

1.2 unordered_set

1、无序集是一种容器，它以不特定的顺序存储唯一的元素，并允许根据元素的值快速检索单个元素。

2、在unordered_set中，元素的值同时是唯一标识它的键。键是不可变的，只可增删，不可修改。

3、在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织成桶，从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。

4、unordered_set容器比set容器更快地通过它们的键访问单个元素，尽管它们在元素子集的范围迭代中通常效率较低。

5、容器中的迭代器至少是前向迭代器。

       unordered_set 容器提供了和 unordered_map 相似的能力，但 unordered_set 可以用保存的元素作为它们自己的键。T 类型的对象在容器中的位置由它们的哈希值决定，因而需要定义一个 Hash< T > 函数。基本类型可以省去Hash< T >方法。不能存放重复元素。可指定buckets个数，可进行初始化，也可后期插入元素

常用接口函数：可以参考set的函数使用，还有一些关于哈希的接口后面再讲解

1.3 unordered系列写OJ题

（困难题唯唯诺诺，简单题多次重拳出击）

961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣（LeetCode）

难度简单

给你一个整数数组 nums ，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]

输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]

输出：2

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]

输出：5

提示：

• 2 <= n <= 5000

• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
 
    }
};

解析代码：（和map一样用）（以下代码改成map也能过，OJ平均效率低一些，后面就知道了）

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_map<int,int> countMap;
        for(const auto& e : nums)
        {
            countMap[e]++;
        }
 
        unordered_map<int,int> Map;
        for(const auto& kv : countMap)
        {
            if(kv.second == nums.size() / 2)
            {
                return kv.first;
            }
        }
        return -1; // 不会走到这，顺便返回一个值
    }
};

349. 两个数组的交集 - 力扣（LeetCode）

难度简单

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]

输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出：[9,4]

解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 
    }
};

解析代码：（这题在从C语言到C++_26讲过了）（当时用set排序了，现在不排序写写）

当时是力扣题解2，现在是力扣题解1：使用哈希集合存储元素，则可以在O（1）的时间内判断一个元素是否在集合中，从而降低时间复杂度。首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合（随便遍历一个也行，就是效率低点），判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。

该方法的时间复杂度可以降低到O（m+n）。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set s1(nums1.begin(),nums1.end()); // 去重
        unordered_set s2(nums2.begin(),nums2.end());
 
        vector<int> retV;
        if(s1.size() <= s2.size())
        {
            for(const auto& e : s1)
            {
                if(s2.find(e) != s2.end())
                {
                    retV.push_back(e);
                }
            }
        }
        else
        {
            for(const auto& e : s2)
            {
                if(s1.find(e) != s1.end())
                {
                    retV.push_back(e);
                }
            }
        }
        return retV;
    }
};

217. 存在重复元素 - 力扣（LeetCode）

难度简单

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]

输出：true

示例 2：

输入：nums = [1,2,3,4]

输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
 
    }
};

解析代码：（看看返回值，前两个和模拟实现set的一样）

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(const auto& e : nums)
        {
            if(s.insert(e).second == false)
            {
                return true;
            }
        }
        return false;
    }
};

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