（嵌入式八股）第4章 STL(二)（后续STL相关会持续补充在这里）

4.11 哈希碰撞与哈希冲突

哈希碰撞（Hash Collision）和 哈希冲突（Hash Collision）这两个术语常常被混用，但它们在某些文献中可能有略微的区别。实际上，在大多数情况下，它们指的是相同的现象：当两个不同的输入数据（或者对象）通过哈希函数映射到同一个哈希值时，发生了冲突或碰撞。

哈希碰撞：

哈希碰撞指的是，当两个不同的输入数据通过哈希函数处理后，得到了相同的哈希值。这是因为哈希函数的输出空间是有限的，而输入空间可能是无限的，因此无法避免不同的输入映射到相同的哈希值。

哈希冲突：

哈希冲突通常用于描述哈希表中的实际问题。当两个不同的键被哈希到相同的桶（即同一个哈希值）时，就发生了冲突。在哈希表中处理这种情况时，通常会使用一些解决策略，比如链地址法和开放地址法。

解决哈希冲突的方法：

1. 链地址法：使用链表来存储冲突的元素。多个元素可能会被映射到相同的哈希值，在这种情况下，这些元素会被存储在同一个链表中。
2. 开放地址法：当发生哈希冲突时，寻找另一个空的桶来存放元素。常见的方法包括线性探测、二次探测和双重哈希。

插入元素：

1. 首先插入了 "apple", "banana" 和 "orange"，每个元素都映射到哈希表中的不同桶。
2. 然后 "apple" 被再次插入并赋予新的值 4，这表示在哈希表中发生了哈希冲突。哈希表通过更新已存在的键值对来解决冲突，而不是将其放入不同的位置。

查找操作：

1. 查找 "apple" 返回的是最后插入的值 4，而不是之前的 1。这说明哈希表通过更新操作解决了冲突。
2. "banana" 和 "orange" 的查找操作返回各自正确的值。

哈希冲突的解决：

1. 该示例并没有明确使用链地址法或开放地址法来解决冲突，这部分通常由 std::unordered_map 的实现自动处理。
2. 对于哈希冲突，std::unordered_map 会根据其内部实现使用合适的方法，如链地址法，来解决键值对存储和查找的问题。

总结

• 哈希碰撞 和 哈希冲突 都指的是不同的输入映射到相同的哈希值。
• 哈希冲突在实际的哈希表中被通过链地址法或开放地址法等策略处理。
• 解决哈希冲突后，哈希表能够继续存储和检索数据，但会有一定的性能影响。

4.12 STL 容器的底层数据结构及复杂度分析

std::vector

底层实现：动态数组

操作复杂度分析：

• 插入：平均情况：O(1)（在尾部插入），因为动态数组的末尾插入不需要移动其他元素。最坏情况：O(n)（需要重新分配和复制），当当前容量不足时，需要分配一个新的更大的内存块，并复制原始数据。
• 查找：O(1)，支持通过下标进行快速随机访问。
• 删除：O(1)（在尾部删除），只需要减少容器的大小。O(n)（在中间删除），需要移动删除位置后面的所有元素。
• 空间复杂度：O(n)，因为 std::vector 需要存储其元素，并且会有一定的内存预留以减少扩容频率。

std::array

底层实现：固定大小的数组

操作复杂度分析：

• 插入：N/A，因为 std::array 的大小在编译时固定，因此不能插入元素。
• 查找：O(1)，支持通过下标进行随机访问。
• 删除：N/A，同样因为大小固定，不能删除元素。
• 空间复杂度：O(n)，因为它存储固定大小的元素。

std::deque

底层实现：分段的动态数组（块链）

操作复杂度分析：

• 插入：平均情况：O(1)（在尾部和头部插入），因为 deque 使用了分段数组，可以在两端快速插入元素。最坏情况：O(n)，当需要重新分配内存时，可能会重新分配整个 deque。
• 查找：O(1)，支持随机访问。
• 删除：O(1)，在两端删除元素。
• 空间复杂度：O(n)，存储分段数组。

std::list

底层实现：双向链表

操作复杂度分析：

• 插入：O(1)，插入操作在链表中间或两端非常高效。
• 查找：O(n)，需要遍历链表来找到元素。
• 删除：O(1)，删除操作在链表