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容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的

2.hash_map如何解决冲突

2.1开放地址法

（1）线性探测再散列
放入元素，如果发生冲突，就往后找没有元素的位置；
（2）平方探测再散列
如果发生冲突，放到(冲突+1平方)的位置，如果还发生冲突，就放到(冲突-1平方)的位置；如果还有人就放到(冲突+2平方)的位置，以此类推，要是负数就倒序数。

优点

1.记录更容易进行序列化操作
2.如果记录总数可以预知，可以创建完美的哈希函数，尽量避免hash冲突，提高效率；

缺点

1.扩容成本太高；
2.使用探测序列，造成额外计算时间；
3.删除的时候需要设置删除标记，造成额外的空间和操作；

2.2拉链法

如果发生冲突，就继续往前一个元素上链接，形成一个链表，Java的hashmap就是这种方法。

优点

1.对于记录总数频繁可变的情况处理的较好；
2.结点是动态分配，不会造成内存的浪费；
3.删除记录比较方便，可是直接通过指针操作；

缺点

1.存储的记录是随机分布在内存中的，跳转访问时会带来额外的开销；
2.由于使用指针，记录不容易进行序列化操作；

3. 再哈希

如果发生冲突，就用另一个方法计算hashcode，两次结果值不一样就不会发生hash冲突；

4. 建立公共溢出区

将哈希表分为基本表和溢出表两部分，与基本表发生冲突的元素，一律填入溢出表。

参考：

阿秀、HashMap解决冲突的四种方法

3.hash_map如何扩容

哈希表（如std::unordered_map）的扩容是一个重要的过程，它在装载因子（即哈希表中当前元素数量与哈希表大小的比值）达到或超过某个阈值（例如0.75）时发生。装载因子过高会增加哈希冲突的可能性，从而降低哈希表的性能。

以下是哈希表扩容的基本步骤：

1. 分配新内存：首先，哈希表会分配一个新的、更大的内存块。新哈希表的大小通常是原来的两倍，但具体的扩展策略可能因具体的哈希表实现和特定的应用需求而不同。

2. 元素重新哈希：然后，哈希表会遍历原来的所有元素，并使用哈希函数重新计算每个元素的哈希值。由于哈希表的大小已经改变，这通常会导致元素的哈希值也随之改变。

3. 元素迁移：接着，哈希表会根据每个元素新的哈希值，将元素移动到新哈希表的相应位置。

4. 释放旧内存：最后，一旦所有的元素都被成功地迁移到新的哈希表，就可以释放旧的哈希表占用的内存。

值得注意的是，哈希表的扩容操作需要对所有元素进行重新哈希和迁移，因此时间复杂度为O(n)，其中n是哈希表中的元素数量。尽管这是一个代价高昂的操作，但它可以帮助减少哈希冲突，提高哈希表的性能。另外，如果能够预测到哈希表的大小需求，可以在创建哈希表时就指定一个足够大的初始大小，以减少运行时的扩容操作。