- 正确答案：实现一个带有并发控制的哈希LRU缓存（Hash + LRU），即支持 O(1) 的 get 和 put 操作，并在多线程环境下通过锁保证线程安全。该结构通常结合哈希表和双向链表，使用互斥锁（如 pthread_mutex 或 std::mutex）保护共享数据。 - 解答思路： 1. 明确需求：需要一个容量有限的缓存，支持最近最少使用淘汰策略（LRU），同时允许多个线程安全地访问。 2. 数据结构选择： - 使用哈希表（unordered_map）快速定位缓存项。 - 使用双向链表维护访问顺序，头节点是最久未使用的，尾节点是最新使用的。 3. 操作逻辑： - get(key)：若存在，从哈希表中取出并移动到链表尾部（表示最新使用）；否则返回 -1。 - put(key, value)：若已存在则更新值并移至尾部；若不存在且缓存满，则删除头部节点（最久未用），插入新节点到尾部。 4. 并发控制：对整个缓存操作加互斥锁，确保同一时间只有一个线程能修改结构。 - 深度知识讲解：考察点包括： 1. LRU 缓存设计原理：核心是“访问局部性”思想，频繁访问的数据应保留在高速存储中。 2. 哈希表 + 双向链表组合优势： - 哈希表提供 O(1) 查找； - 双向链表支持 O(1) 插入/删除节点（前提能找到节点）； - 单向链表无法高效删除前驱，故必须为双向。 3. 时间复杂度分析： - get: O(1) - put: O(1) 4. 锁粒度问题： - 这里采用“全缓存一把锁”，简单但可能成为性能瓶颈； - 高级优化可使用分段锁（类似 ConcurrentHashMap）或读写锁（shared_mutex），提高并发读性能。 5. C++ 中 std::mutex 与 RAII 结合使用 lock_guard 自动管理锁生命周期，防止死锁。 6. 内存管理：手动管理时需注意释放节点；C++ 中可用智能指针（如 shared_ptr / unique_ptr）辅助，但注意循环引用。 - 代码示例（C++ 实现）： ``` #include #include #include #include struct ListNode { int key; int value; ListNode* prev; ListNode* next; ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; class HashLRUCache { private: int capacity; std::unordered_map cache; ListNode* head; // dummy head ListNode* tail; // dummy tail std::mutex mtx; // mutex for thread safety void removeNode(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void addToTail(ListNode* node) { node->prev = tail->prev; node->next = tail; tail->prev->next = node; tail->prev = node; } public: HashLRUCache(int cap) : capacity(cap) { head = new ListNode(0, 0); tail = new ListNode(0, 0); head->next = tail; tail->prev = head; } ~HashLRUCache() { while (head != nullptr) { ListNode* temp = head; head = head->next; delete temp; } } int get(int key) { std::lock_guard lock(mtx); // auto lock, auto unlock auto it = cache.find(key); if (it == cache.end()) { return -1; } ListNode* node = it->second; removeNode(node); addToTail(node); return node->value; } void put(int key, int value) { std::lock_guard lock(mtx); auto it = cache.find(key); if (it != cache.end()) { ListNode* node = it->second; node->value = value; removeNode(node); addToTail(node); } else { if (cache.size() >= capacity) { ListNode* toRemove = head->next; removeNode(toRemove); cache.erase(toRemove->key); delete toRemove; } ListNode* newNode = new ListNode(key, value); cache[key] = newNode; addToTail(newNode); } } void printCache() { std::lock_guard lock(mtx); std::cout << "Cache content: "; ListNode* cur = head->next; while (cur != tail) { std::cout << "(" << cur->key << "," << cur->value << ") "; cur = cur->next; } std::cout << std::endl; } }; // 示例使用 int main() { HashLRUCache cache(2); cache.put(1, 1); cache.put(2, 2); cache.printCache(); // (1,1) (2,2) cache.get(1); cache.printCache(); // (2,2) (1,1) cache.put(3, 3); // evicts key 2 cache.printCache(); // (1,1) (3,3) std::cout << "get(2): " << cache.get(2) << std::endl; // -1 return 0; } ``` - 扩展知识点： 1. 替代方案：可以使用 std::list 自带的双向链表功能，配合 splice 操作实现更简洁代码： - list.splice(list.end(), list, iterator) 可将某元素移到末尾，O(1)。 - cache map 存储 list::iterator。 2. 无锁化尝试：极端高性能场景下可用原子操作+RCU机制，但复杂度极高。 3. 实际应用：Redis、数据库缓冲池、CPU Cache 等均使用类似思想。 4. Java 中的 LinkedHashMap 已内置 LRU 支持（通过 accessOrder 参数）。 5. 内存对齐与缓存行：高频访问的节点尽量靠近，减少 cache miss。总结：本题综合考察数据结构设计、算法效率、并发编程三大能力，是典型中高级面试题。掌握其底层实现有助于理解系统级缓存机制。

柠檬微趣一面面经

全站热榜

创作者周榜