17.STL中unordered_map(hash_map)和map的区别，hash_map如何解决冲突以及扩容

1.区别

1.1需要引入的头文件不同

map: #include < map >

unordered_map: #include < unordered_map >

1.2内部实现机理不同

map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。哈希表详细介绍

1.3使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。

std::map是一个排序的关联容器，需要对键值进行比较，以确定元素的存储位置。默认情况下，std::map使用operator<来比较键，因此，如果你使用的键是自定义类型，那么你需要重载该类型的operator<。
std::unordered_map是一个基于哈希的关联容器，它使用哈希函数来确定元素的存储位置，同时也需要一个比较函数来处理哈希冲突。默认情况下，std::unordered_map使用std::hash作为哈希函数，operator==作为比较函数。如果你使用的键是自定义类型，你需要为其定义自己的哈希函数，并重载operator==。

下面是一个使用自定义类型作为std::unordered_map键的例子，这个例子展示了如何定义哈希函数并重载operator==：

#include <iostream>
#include <unordered_map>

struct MyKey
{
    int x, y;

    bool operator==(const MyKey& other) const
    {
        return x == other.x && y == other.y;
    }
};

struct MyHash 
{
    std::size_t operator()(const MyKey& key) const
    {
        return std::hash<int>()(key.x) ^ std::hash<int>()(key.y);
    }
};

int main() 
{
    std::unordered_map<MyKey, int, MyHash> um;

    um[MyKey{ 2, 3 }] = 10;
    um[MyKey{ 1, 4 }] = 20;

    for (const auto& pair : um)
    {
        std::cout << "(" << pair.first.x << ", " << pair.first.y << ") : " << pair.second << std::endl;
    }

    return 0;
}

在这个例子中，MyKey结构体重载了operator==，MyHash结构体定义了哈希函数。当我们创建std::unordered_map时，我们把MyHash作为第三个模板参数传递给std::unordered_map，从而使用自定义的哈希函数。

那么如果是自定义类型，那么就需要自己重载operator<或者hash_value()了。

当你在std::map或std::unordered_map中使用自定义类型作为键（key）时，你需要提供一种方式来比较（对于std::map）或哈希（对于std::unordered_map）这些键。这通常意味着你需要重载你的自定义类型的operator<或定义一个哈希函数。

这是因为std::map依赖于能够比较键的能力来在内部保持元素的排序，而std::unordered_map则依赖于能够哈希键的能力来在内部进行元素的组织。

此外，对于std::unordered_map，你还需要为自定义类型重载operator==，因为当哈希函数产生冲突（也就是两个不同的键产生相同的哈希值）时，std::unordered_map需要一种方式来确定两个键是否实际上是相等的。

如果你的自定义类型没有提供这些必需的操作符重载或哈希函数，编译器将无法正确地使用这些类型作为std::map或std::unordered_map的键。

1.4优缺点以及适用处

map：

（1）优点

①有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

②红黑树，内部实现一个红黑树使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

（2）缺点：

空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

（3）适用处：

对于那些有顺序要求的问题，需要内部元素自动排序，用map会更高效一些

unordered_map：

（1）优点：

因为内部实现了哈希表，因此其查找速度非常的快

（2）缺点：

哈希表的建立比较耗费时间

（3）适用处：

对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

总结：

1.内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder_map占用的内存要高。
2.但是unordered_map执行效率要比map高很多
3.对于unordered_map或unordered_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的