简述STL 中 unordered_map(hash_map)和 map 的区别,hash_map 如 何解决冲突以及扩容 ?
参考答案:
std::unordered_map
(通常也被称为hash_map
)和std::map
都是C++ STL中关联容器的一种,它们以键值对的形式存储元素,并允许我们根据键快速访问对应的值。然而,它们在内部实现、性能特点和适用场景上有一些明显的区别。
-
内部实现:
std::map
是基于红黑树实现的,它保证了元素按键值从小到大排序。std::unordered_map
则基于哈希表实现,它并不保证元素的排序。
-
性能特点:
std::map
的插入、删除和查找操作的平均时间复杂度为O(log n),在最坏情况下为O(n)(当树退化为链表时)。std::unordered_map
的插入、删除和查找操作的平均时间复杂度为O(1),但在最坏情况下可能达到O(n)(当哈希函数导致所有元素都映射到同一个桶时)。
-
适用场景:
- 如果需要按键值快速查找元素,且不关心元素的顺序,
std::unordered_map
通常是更好的选择。 - 如果需要按键值排序并快速查找元素,
std::map
是更合适的选择。
- 如果需要按键值快速查找元素,且不关心元素的顺序,
关于hash_map
如何解决冲突以及扩容的问题:
解决冲突:哈希表通过哈希函数将键映射到数组的索引上,但当两个键的哈希值相同时(即发生哈希冲突),就需要采用一些策略来解决冲突。常见的解决策略有:
- 开放寻址法:当发生冲突时,按照一定的规则(如线性探测、平方探测、双散列等)在数组中查找下一个可用的槽位。
- 链地址法:也叫做分离链接法,每个槽位都存储一个链表,当发生冲突时,将元素添加到对应槽位的链表中。
扩容:当哈希表中的元素数量达到一定阈值时,就需要进行扩容,以避免过多的哈希冲突。扩容通常会创建一个更大的数组,并将原有元素重新哈希并插入到新的数组中。扩容操作可能会涉及大量的数据搬移,因此通常是一个相对耗时的操作。为了减少扩容的频率和开销,哈希表通常会采用一个大于实际元素数量的数组来存储元素,这个比例通常称为负载因子。当元素数量达到数组容量的一定比例时,就会触发扩容操作。