unordered_map的底层原理

unordered_map 是 C++ STL 中的一个关联容器，它提供了基于键值对的快速查找功能。它的底层实现是基于哈希表（hash table）。

在 unordered_map 中，每个键值对都被存储在一个桶（bucket）中。通过计算键的哈希值，可以确定键值对应该存储在哪个桶中。当需要访问特定键值对时，通过哈希值可以快速定位到对应的桶，进而提高查找效率。

在 unordered_map 的底层实现中，使用了一个动态数组，每个元素是一个桶。每个桶中存储的是一个链表或红黑树，用于解决哈希冲突（即出现相同哈希值的键）。当发生哈希冲突时，新的键值对会被添加到链表或红黑树中，使得同一个桶中可以存储多个键值对。

当进行插入、查找或删除操作时，unordered_map 首先通过哈希函数计算键的哈希值，然后定位到对应的桶。对于查找操作，unordered_map 会遍历链表或红黑树来找到匹配的键值对。由于哈希表的查找操作具有平均时间复杂度 O(1)，所以 unordered_map 提供了快速的查找能力。

总结来说，unordered_map 通过哈希表实现了键值对的快速查找，通过哈希函数和桶来解决哈希冲突，提供了高效的插入、查找和删除操作。

相关问题

unordered_set、unordered_multiset、unordered_map、unordered_multimap底层原理

unordered_set、unordered_multiset、unordered_map和unordered_multimap的底层原理是基于哈希表实现的。哈希表是一种数据结构，通过将关键字映射到哈希表中的一个位置来快速查找和插入元素。在哈希表中，每个元素被存储在一个桶中，桶的数量和大小根据哈希表的大小和负载因子动态调整。

当插入一个元素时，哈希表首先使用哈希函数计算关键字的哈希值，然后根据哈希值找到对应的桶。如果桶是空的，则直接插入元素；如果桶不为空，则通过开放定址法或链地址法解决冲突，将元素插入到合适的位置。插入操作的平均时间复杂度是常数级别的。

当查找一个元素时，哈希表通过哈希函数计算关键字的哈希值，然后根据哈希值找到对应的桶。如果桶中有元素，则通过比较关键字找到目标元素；如果桶中没有元素，则表示目标元素不存在。查找操作的平均时间复杂度是常数级别的。

删除一个元素的操作也类似于查找操作，先找到元素所在的桶，然后删除元素。删除操作的平均时间复杂度也是常数级别的。

unordered_map实现原理

unordered_map的底层使用哈希表（hash table）来实现。哈希表是一种高效的数据结构，它可以在常数时间内进行插入、查找和删除操作。unordered_map使用哈希函数将键（key）映射到哈希值，然后将哈希值映射到存储桶（bucket）。每个存储桶中可以存储一个或多个键值对，具体的实现方式可以通过链表、红黑树等数据结构来解决哈希冲突。

当插入或查找一个键值对时，unordered_map会使用哈希函数计算键的哈希值，并找到对应的存储桶。如果存储桶为空，则直接插入键值对；如果存储桶不为空，则根据键值对的键与存储桶中已有的键进行比较，如果存在相同的键，则进行更新操作；如果不存在相同的键，则将键值对插入到存储桶中。

在unordered_map中，存储桶的数量通常是根据当前容量和负载因子（load factor）来确定的。负载因子是指哈希表中键值对的数量除以存储桶的数量。当负载因子超过一定阈值时，unordered_map会自动调整存储桶的数量，以保持哈希表的性能。

总之，unordered_map底层使用哈希表来实现，通过哈希函数将键映射到存储桶中，并使用链表、红黑树等数据结构来解决哈希冲突。这种实现方式使得unordered_map能够在常数时间内进行插入、查找和删除操作，具有高效的性能特点。 <span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [unordered_map、unordered_set底层哈希表的实现机理](https://blog.csdn.net/qq_35987777/article/details/106668695)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [C++——unordered_map浅析](https://blog.csdn.net/ly0724ok/article/details/117362251)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]