- 正确答案：实现一个线程安全的LRU（Least Recently Used）缓存，通常结合双向链表和哈希表，并通过锁机制保证多线程环境下的安全性。可以使用Java中的ConcurrentHashMap配合ReentrantReadWriteLock，或使用synchronized关键字、ReadWriteLock等同步机制来保护共享数据结构。 - 解答思路： 1. LRU缓存的核心是维护最近最少使用的顺序：当访问某个元素时，将其移到“最近使用”位置；当缓存满时，淘汰最久未使用的元素。 2. 使用双向链表维护访问顺序：头结点表示最新使用，尾结点表示最久未使用。 3. 使用哈希表（如HashMap）实现O(1)的键值查找。 4. 在多线程环境下，多个线程可能同时读写缓存，因此必须对插入、查询、删除操作加锁，防止数据竞争。 5. 考虑性能，应尽量减少锁的粒度，例如使用读写锁（Read-Write Lock），允许多个读操作并发执行，仅在写操作时独占锁。 - 深度知识讲解： LRU缓存的本质是一个有序映射结构，要求支持以下操作： - get(key): 获取值，若存在则返回并更新为最近使用；否则返回null。 - put(key, value): 插入或更新键值对，若已存在则更新值并移到头部；若不存在且容量超限，则删除尾部节点后插入新节点到头部。数据结构选择原因： - 双向链表：可以在O(1)时间内将节点从任意位置移至头部，也能在知道指针的情况下O(1)删除尾节点。 - 哈希表：提供O(1)的键到节点的映射查找。线程安全的关键在于所有共享状态的操作都必须同步。共享状态包括： - 哈希表（map） - 双向链表的头尾指针及节点连接关系 - 当前大小（size）若不加锁，在并发场景下可能出现： - A线程正在遍历链表，B线程修改了next指针 → 链表断裂或死循环 - 两个线程同时put导致同一key被插入两次 - size计数错误，导致缓存溢出或提前淘汰锁的选择： - synchronized：简单但粗粒度，所有操作互斥，性能差。 - ReentrantReadWriteLock：读操作共享，写操作独占，适合读多写少场景（如缓存），显著提升并发性能。扩展优化方向： - Java中可使用ThreadLocal + 分段锁模拟ConcurrentHashMap的思想进行更高并发设计。 - 使用volatile修饰头尾指针（但不足以保证整体一致性，仍需锁）。 - 使用CAS+自旋实现无锁化（复杂，适用于高性能中间件）。底层原理补充： - 双向链表节点结构包含prev、next、key、value。 - 哈希冲突由哈希表内部处理，不影响LRU逻辑。 - 内存回收：当节点从链表和map中移除后，不再引用，可被GC回收。 - 伪代码示例（以Java风格描述）： ``` class ThreadSafeLRUCache { private final int capacity; private final Map> map; private final ReadWriteLock lock = new ReentrantReadWriteLock(); private final Lock readLock = lock.readLock(); private final Lock writeLock = lock.writeLock(); private Node head; // 最新使用 private Node tail; // 最久未使用 private int size; static class Node { K key; V value; Node prev; Node next; Node(K k, V v) { key = k; value = v; } } public ThreadSafeLRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<>(); this.size = 0; this.head = null; this.tail = null; } public V get(K key) { readLock.lock(); try { Node node = map.get(key); if (node == null) return null; // 提升为最近使用（需要写锁） moveToHead(node); return node.value; } finally { readLock.unlock(); } } // 注意：get中调用moveToHead涉及结构修改，实际应升级为写锁或整体用写锁 // 更稳妥做法：get也用写锁，或复制一份路径避免锁升级问题 // 改进方案：统一使用writeLock保护所有结构性修改 public void put(K key, V value) { writeLock.lock(); try { Node existing = map.get(key); if (existing != null) { existing.value = value; moveToHead(existing); } else { Node newNode = new Node<>(key, value); map.put(key, newNode); addToHead(newNode); size++; if (size > capacity) { Node toRemove = tail; removeNode(toRemove); map.remove(toRemove.key); size--; } } } finally { writeLock.unlock(); } } private void removeNode(Node node) { if (node.prev != null) node.prev.next = node.next; else head = node.next; if (node.next != null) node.next.prev = node.prev; else tail = node.prev; } private void addToHead(Node node) { node.next = head; node.prev = null; if (head != null) head.prev = node; head = node; if (tail == null) tail = node; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } } ``` - 特别说明：上述伪代码中，get方法在获取值后调用了moveToHead，这会改变链表结构，因此不能只用读锁。正确的做法是： - 方案一：get和put都使用writeLock（牺牲并发读性能） - 方案二：使用全写锁，但在高并发下可用分段锁思想改进 - 方案三：采用CopyOnWrite思想（不适合频繁写场景） - 方案四：使用synchronized(this)统一同步块，简化控制推荐实际实现中将get和put均用writeLock保护，因为LRU的get具有副作用（改变顺序），属于“读-改-写”复合操作，不具备无干扰性。 - 扩展知识点： - Java标准库中LinkedHashMap可通过重写removeEldestEntry方法实现简易LRU，但非线程安全。可通过Collections.synchronizedMap包装，但无法解决复合操作的原子性。 - Guava Cache提供了线程安全的本地缓存实现，支持LRU、TTL、权重淘汰等策略，底层基于ConcurrentHashMap和队列维护顺序。 - Redis的LRU实现采用近似LRU算法（随机采样），避免全量维护排序带来的开销。综上，实现线程安全的LRU需综合考虑数据结构选择、锁机制、操作原子性与性能平衡。

亚信安全一面

全站热榜

创作者周榜