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

std::unordered_map（通常也被称为hash_map）和std::map都是C++ STL中关联容器的一种，它们以键值对的形式存储元素，并允许我们根据键快速访问对应的值。然而，它们在内部实现、性能特点和适用场景上有一些明显的区别。

1. 内部实现：

   • std::map是基于红黑树实现的，它保证了元素按键值从小到大排序。
   • std::unordered_map则基于哈希表实现，它并不保证元素的排序。

2. 性能特点：

   • std::map的插入、删除和查找操作的平均时间复杂度为O(log n)，在最坏情况下为O(n)（当树退化为链表时）。
   • std::unordered_map的插入、删除和查找操作的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)（当哈希函数导致所有元素都映射到同一个桶时）。

3. 适用场景：

   • 如果需要按键值快速查找元素，且不关心元素的顺序，std::unordered_map通常是更好的选择。
   • 如果需要按键值排序并快速查找元素，std::map是更合适的选择。

关于hash_map如何解决冲突以及扩容的问题：

解决冲突：哈希表通过哈希函数将键映射到数组的索引上，但当两个键的哈希值相同时（即发生哈希冲突），就需要采用一些策略来解决冲突。常见的解决策略有：

1. 开放寻址法：当发生冲突时，按照一定的规则（如线性探测、平方探测、双散列等）在数组中查找下一个可用的槽位。
2. 链地址法：也叫做分离链接法，每个槽位都存储一个链表，当发生冲突时，将元素添加到对应槽位的链表中。

扩容：当哈希表中的元素数量达到一定阈值时，就需要进行扩容，以避免过多的哈希冲突。扩容通常会创建一个更大的数组，并将原有元素重新哈希并插入到新的数组中。扩容操作可能会涉及大量的数据搬移，因此通常是一个相对耗时的操作。为了减少扩容的频率和开销，哈希表通常会采用一个大于实际元素数量的数组来存储元素，这个比例通常称为负载因子。当元素数量达到数组容量的一定比例时，就会触发扩容操作。