除了 LRU 缓存的结构之外，我还没有读过太多关于它的内容，但我仍然对它比常规哈希图快得多感到惊讶。

我做了一个测试，一个递归组合问题，使用常规哈希图来保存递归期间的结果结果（动态编程），并做了相同的操作，唯一的区别是使用了 LRU 缓存实现（大小 1024）。

性能从1秒下降到0.006秒！

现在，这非常令人惊讶，我不知道为什么会这样。对于大多数操作来说，哈希图的时间复杂度为 O(1)，并且 LRU 缓存需要哈希图和双向链表。

语境：

• 我在这个项目中使用 C++。所讨论的 hashmap 是一个 unordered_map，以字符串作为键，以整数作为值。我听说过 unordered_map 最坏情况的复杂度为N或N ²，但据我所知，它通常在O(1)中执行所有操作。

• LRU 缓存实现是从堆栈溢出复制粘贴的：D

代码

使用 LRU 缓存

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

template <typename T,typename U>                                                   
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")


// LRU Cache implementation
template <class KEY_T, class VAL_T> class LRUCache{ …