缓存类为啥使用 unordered_map 而不是 map

• 性能考虑：
  • std::unordered_map 是基于哈希表实现的，而 std::map 是基于红黑树实现的。
  • 对于查找操作，std::unordered_map 的平均查找时间复杂度是 $O(1)$，而 std::map 的查找时间复杂度是 $O(logn)$。这意味着在大多数情况下，std::unordered_map 能更快地找到元素，特别是当元素数量较大时，性能优势更明显。
  • 在这个缓存类的实现中，get 操作需要频繁地查找元素，使用 std::unordered_map 可以提高查找性能。
• 元素顺序：
  • std::map 中的元素是按照键的大小顺序存储的，因为它基于二叉搜索树。这在需要元素有序存储的场景下很有用，但对于缓存类来说，元素的存储顺序通常并不重要。
  • std::unordered_map 中的元素是无序存储的，更适合不需要元素排序的场景，因为它不会花费额外的时间和空间来维护元素的顺序。

示例对比：

• 假设你有一个 std::map<int, int> 和一个 std::unordered_map<int, int>，它们都存储了 n 个元素。
  • 当你使用 map[key] 查找元素时，std::map 需要进行多次比较操作，最多需要 $O(logn)$ 次，因为它要在红黑树中搜索元素。
  • 对于 std::unordered_map，它会根据键的哈希值快速定位元素，平均只需要 $O(1)$ 次操作。

代码示例：

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <chrono>int main() {std::map<int, std::string> ordered_map;std::unordered_map<int, std::string> unordered_map;// 插入元素for (int i = 0; i < 1000000; ++i) {ordered_map[i] = "value" + std::to_string(i);unordered_map[i] = "value" + std::to_string(i);}// 测试 std::map 的查找性能auto start = std::chrono::high_resolution_clock::now();for (int i = 0; i < 1000000; ++i) {auto it = ordered_map.find(i);}auto end = std::chrono::high_resolution_clock::now();std::chrono::duration<double> ordered_time = end - start;std::cout << "std::map find time: " << ordered_time.count() << " seconds" << std::endl;// 测试 std::unordered_map 的查找性能start = std::chrono::high_resolution_clock::now();for (int i = 0; i < 1000000; ++i) {auto it = unordered_map.find(i);}end = std::chrono::high_resolution_clock::now();std::chrono::duration<double> unordered_time = end - start;std::cout << "std::unordered_map find time: " << unordered_time.count() << " seconds" << std::endl;return 0;
}

代码解释：

• 这段代码创建了一个 std::map 和一个 std::unordered_map，并插入了 100 万个元素。
• 然后，分别使用 find() 方法查找元素，并使用 std::chrono 库来测量查找操作的时间。
• 你会发现 std::unordered_map 的查找时间通常会比 std::map 短，尤其是当元素数量很大时。

总结：

• 在实现缓存类时，性能通常是重要的考虑因素，因为缓存的主要目的是快速存储和获取数据。
• 由于 std::unordered_map 具有更快的查找性能和不需要元素排序的特点，更适合作为存储键值对的容器，以实现高效的 get 和 put 操作。
• 然而，如果你的应用场景需要元素按键的顺序存储和访问，那么 std::map 会是更好的选择。但对于缓存类，通常不需要元素有序，因此 std::unordered_map 是更好的选择。