Approach (summary):- Use segmentation to avoid a single global lock: split the cache into S independent segments. Each segment holds ~capacity/S items and uses a ConcurrentHashMap for O(1) lookup plus a doubly-linked list for LRU order. Each segment protects its list updates with a ReentrantLock. This gives thread-safety and high throughput; LRU is maintained per-segment (approximate global LRU). Trade-off: ordering is exact within a segment but only approximate globally.java
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
public class SegmentedLRUCache<K,V> {
private final Segment<K,V>[] segments;
private final int segmentMask;
private final int capacityPerSegment;
@SuppressWarnings("unchecked")
public SegmentedLRUCache(int capacity, int segmentsCount) {
if (Integer.bitCount(segmentsCount) != 1) throw new IllegalArgumentException("segmentsCount must be power of two");
this.segments = new Segment[segmentsCount];
this.segmentMask = segmentsCount - 1;
this.capacityPerSegment = Math.max(1, capacity / segmentsCount);
for (int i = 0; i < segmentsCount; i++) segments[i] = new Segment<>(capacityPerSegment);
}
private final int segIndex(Object key) {
return (key.hashCode() >>> 1) & segmentMask;
}
public V get(K key) {
return segments[segIndex(key)].get(key);
}
public void put(K key, V value) {
segments[segIndex(key)].put(key, value);
}
// Inner segment: hashmap + doubly linked list protected by lock
private static final class Segment<K,V> {
private final ConcurrentHashMap<K, Node<K,V>> map = new ConcurrentHashMap<>();
private final ReentrantLock lock = new ReentrantLock();
private final int capacity;
private Node<K,V> head; // most recent
private Node<K,V> tail; // least recent
Segment(int capacity){ this.capacity = capacity; }
V get(K key){
Node<K,V> n = map.get(key);
if (n == null) return null;
// move to head under lock
lock.lock();
try {
moveToHead(n);
} finally { lock.unlock(); }
return n.value;
}
void put(K key, V value){
Node<K,V> n = map.get(key);
lock.lock();
try {
if (n != null) {
n.value = value;
moveToHead(n);
return;
}
n = new Node<>(key, value);
linkAtHead(n);
map.put(key, n);
if (map.size() > capacity) removeTail();
} finally { lock.unlock(); }
}
private void moveToHead(Node<K,V> n){
if (n == head) return;
// unlink
if (n.prev != null) n.prev.next = n.next;
if (n.next != null) n.next.prev = n.prev;
if (n == tail) tail = n.prev;
// link at head
n.prev = null; n.next = head;
if (head != null) head.prev = n;
head = n;
if (tail == null) tail = head;
}
private void linkAtHead(Node<K,V> n){
n.prev = null; n.next = head;
if (head != null) head.prev = n;
head = n;
if (tail == null) tail = head;
}
private void removeTail(){
if (tail == null) return;
Node<K,V> old = tail;
map.remove(old.key);
if (old.prev != null){
tail = old.prev;
tail.next = null;
} else {
head = tail = null;
}
old.prev = old.next = null;
}
}
private static final class Node<K,V> {
final K key;
volatile V value;
Node<K,V> prev, next;
Node(K k, V v){ key = k; value = v; }
}
}
