unordered_map 底层数据结构
unordered_map 是 C++ 标准库中一种关联容器，它使用哈希表来存储键值对。由于使用了哈希表，unordered_map 能够以 O(1) 的平均时间复杂度进行插入、删除和查找操作，但需要牺牲一定的排序性。
其底层数据结构主要包含以下部分：
哈希表（Hash Table）
- 哈希表是一个由桶（bucket）组成的数组。每个桶存储一组具有相同哈希值的键值对。
- 每个键在哈希表中都有一个唯一的哈希值，它是通过哈希函数计算得到的。
桶（Bucket）
- 桶是哈希表中的一个单元，它存储一组哈希值相同的键值对。
- 桶的实现通常是链表或红黑树，用于处理哈希冲突。
哈希函数（Hash Function）
- 哈希函数是一个将键映射到哈希值的函数。
- 它将键转换成一个整数，表示键在哈希表中的存储位置。
- 常见的哈希函数包括取模散列法、平方取中法和斐波那契散列法。
负载因子（Load Factor）
- 负载因子是哈希表中已用桶的数量与桶总数的比值。
- 当负载因子接近 1 时，哈希表就会变得拥挤，导致查找和插入操作变慢。
- 因此，通常会通过重新哈希（rehashing）操作来增加桶的数量，以维持较低的负载因子。
哈希冲突（Collision）
- 哈希冲突是指不同的键映射到相同的哈希值的情况。
- 当哈希冲突发生时，可以用桶中的链表或红黑树来存储这些键值对。
- 为了最大程度地减少哈希冲突，哈希函数必须均匀地将键分布到哈希表中。
以上就是unordered_map底层数据结构的详细内容，更多请关注知识资源分享宝库其它相关文章！
发表评论:
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。