Java에서 LRU 캐시를 구현하려면 어떻게 해야 합니까?
EHCache, OSCache 등이라고 말하지 마세요.이 질문의 목적상 SDK(실행으로 학습)만을 사용하여 자신의 SDK를 구현하고 싶다고 가정합니다.캐시가 멀티스레드 환경에서 사용되는 경우 어떤 데이터 구조를 사용하시겠습니까?Linked Hash Map과 Collections #synchronized Map을 사용하여 이미 구현했습니다만, 새로운 동시 컬렉션이 더 적합한지 궁금합니다.
업데이트: Yegge의 최신 정보를 읽다가 이 덩어리를 발견했습니다.
상시 액세스가 필요하고 삽입 순서를 유지하려면 Linked Hash Map을 사용하는 것이 가장 좋습니다.Linked Hash Map은 정말 훌륭한 데이터 구조입니다.더 멋질 수 있는 유일한 방법은 동시 버전이 있는 경우입니다.하지만 슬프다.
는 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★LinkedHashMap+Collections#synchronizedMap구현에 대한 자세한 내용은 다음과 같습니다.내가 그냥 뭔가를 간과하지 않았다는 걸 알게 돼서 다행이야.
지금까지의 답변으로 볼 때, 매우 동시적인 LRU를 위한 최선의 방법은 다음과 같은 논리를 사용하여 Concurrent Hash Map을 확장하는 것입니다.LinkedHashMap를 사용합니다
는 이런, 것 .LinkedHashMap+Collections.synchronizedMap 아마 수 것 같아요.ConcurrentHashMapLinkedHashMap를 확장하다HashMap.
갱신:
요청하신 대로 현재 구현의 요지를 알려드리겠습니다.
private class LruCache<A, B> extends LinkedHashMap<A, B> {
private final int maxEntries;
public LruCache(final int maxEntries) {
super(maxEntries + 1, 1.0f, true);
this.maxEntries = maxEntries;
}
/**
* Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
* created.
*
* <p>
* This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
* <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
* <code>LinkedHashMap</code>.
* </p>
*
* @param eldest
* the <code>Entry</code> in question; this implementation doesn't care what it is, since the
* implementation is only dependent on the size of the cache
* @return <tt>true</tt> if the oldest
* @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
*/
@Override
protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
return super.size() > maxEntries;
}
}
Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));
만약 내가 오늘 처음부터 다시 한다면, 나는 Guava의 것을 사용할 것입니다.
이건 2라운드야.
첫 번째 라운드는 제가 생각해낸 것입니다.그리고 저는 그 도메인을 머릿속에 조금 더 깊이 새겨두고 다시 댓글을 읽었습니다.
다음으로 유닛 테스트를 통해 다른 버전을 기반으로 동작하는 가장 간단한 버전을 보여 줍니다.
먼저 비동시 버전:
import java.util.LinkedHashMap;
import java.util.Map;
public class LruSimpleCache<K, V> implements LruCache <K, V>{
Map<K, V> map = new LinkedHashMap ( );
public LruSimpleCache (final int limit) {
map = new LinkedHashMap <K, V> (16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
return super.size() > limit;
}
};
}
@Override
public void put ( K key, V value ) {
map.put ( key, value );
}
@Override
public V get ( K key ) {
return map.get(key);
}
//For testing only
@Override
public V getSilent ( K key ) {
V value = map.get ( key );
if (value!=null) {
map.remove ( key );
map.put(key, value);
}
return value;
}
@Override
public void remove ( K key ) {
map.remove ( key );
}
@Override
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
True 플래그는 gets와 puts의 액세스를 추적합니다.JavaDocs 를 참조해 주세요.컨스트럭터에 대한 진정한 플래그가 없는removeEdelstEntry는 FIFO 캐시만 구현합니다(FIFO 및 removeEldestEntry에 대한 다음 주 참조).
LRU 캐시로서 기능하는 것을 증명하는 테스트는 다음과 같습니다.
public class LruSimpleTest {
@Test
public void test () {
LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
cache.put ( 4, 4 );
cache.put ( 5, 5 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
if ( !ok ) die ();
}
이제 동시 버전...
패키지 org.cache;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {
final CacheMap<K, V>[] cacheRegions;
private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
private final ReadWriteLock readWriteLock;
private final int limit;
CacheMap ( final int limit, boolean fair ) {
super ( 16, 0.75f, true );
this.limit = limit;
readWriteLock = new ReentrantReadWriteLock ( fair );
}
protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
return super.size () > limit;
}
@Override
public V put ( K key, V value ) {
readWriteLock.writeLock ().lock ();
V old;
try {
old = super.put ( key, value );
} finally {
readWriteLock.writeLock ().unlock ();
}
return old;
}
@Override
public V get ( Object key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = super.get ( key );
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
@Override
public V remove ( Object key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = super.remove ( key );
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
public V getSilent ( K key ) {
readWriteLock.writeLock ().lock ();
V value;
try {
value = this.get ( key );
if ( value != null ) {
this.remove ( key );
this.put ( key, value );
}
} finally {
readWriteLock.writeLock ().unlock ();
}
return value;
}
public int size () {
readWriteLock.readLock ().lock ();
int size = -1;
try {
size = super.size ();
} finally {
readWriteLock.readLock ().unlock ();
}
return size;
}
public String toString () {
readWriteLock.readLock ().lock ();
String str;
try {
str = super.toString ();
} finally {
readWriteLock.readLock ().unlock ();
}
return str;
}
}
public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
int cores = Runtime.getRuntime ().availableProcessors ();
int stripeSize = cores < 2 ? 4 : cores * 2;
cacheRegions = new CacheMap[ stripeSize ];
for ( int index = 0; index < cacheRegions.length; index++ ) {
cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
}
}
public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {
cacheRegions = new CacheMap[ concurrency ];
for ( int index = 0; index < cacheRegions.length; index++ ) {
cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
}
}
private int stripeIndex ( K key ) {
int hashCode = key.hashCode () * 31;
return hashCode % ( cacheRegions.length );
}
private CacheMap<K, V> map ( K key ) {
return cacheRegions[ stripeIndex ( key ) ];
}
@Override
public void put ( K key, V value ) {
map ( key ).put ( key, value );
}
@Override
public V get ( K key ) {
return map ( key ).get ( key );
}
//For testing only
@Override
public V getSilent ( K key ) {
return map ( key ).getSilent ( key );
}
@Override
public void remove ( K key ) {
map ( key ).remove ( key );
}
@Override
public int size () {
int size = 0;
for ( CacheMap<K, V> cache : cacheRegions ) {
size += cache.size ();
}
return size;
}
public String toString () {
StringBuilder builder = new StringBuilder ();
for ( CacheMap<K, V> cache : cacheRegions ) {
builder.append ( cache.toString () ).append ( '\n' );
}
return builder.toString ();
}
}
비동시 버전을 먼저 다루는 이유를 알 수 있습니다.위에서는 잠금 경합을 줄이기 위해 몇 가지 스트라이프를 작성하려고 합니다.키를 해시하고 해시를 검색하여 실제 캐시를 찾습니다.따라서 키 해시 알고리즘이 얼마나 잘 분산되어 있는지에 따라 상당한 오차 내에서 제한 크기가 제안 또는 추측에 가까워집니다.
이것은 동시 버전이 동작하는 것을 나타내는 테스트입니다. :) (실제로는 테스트입니다.
public class SimpleConcurrentLRUCache {
@Test
public void test () {
LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
cache.put ( 4, 4 );
cache.put ( 5, 5 );
puts (cache);
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
cache.put ( 8, 8 );
cache.put ( 9, 9 );
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
puts (cache);
if ( !ok ) die ();
}
@Test
public void test2 () {
LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
for (int index =0 ; index < 5_000; index++) {
cache.get(0);
cache.get ( 1 );
cache.put ( 2, index );
cache.put ( 3, index );
cache.put(index, index);
}
boolean ok = cache.getSilent ( 0 ) == 0 || die ();
ok |= cache.getSilent ( 1 ) == 1 || die ();
ok |= cache.getSilent ( 2 ) != null || die ();
ok |= cache.getSilent ( 3 ) != null || die ();
ok |= cache.size () < 600 || die();
if ( !ok ) die ();
}
}
마지막 투고입니다.첫 번째 게시물은 LRU 캐시가 아닌 LFU였기 때문에 삭제했습니다.
한 번 더 해볼까 했는데표준 JDK를 사용한 가장 단순한 버전의 LRU 캐시를 생각하려고 했습니다.너무 많은 구현이 필요 없습니다.
내가 생각해낸 건 이거야.첫 번째 시도는 및 LRU가 아닌 LFU를 구현하고 FIFO와 LRU 지원을 추가했기 때문에 약간 실패했습니다.괴물이 되고 있다는 걸 깨달았어요그리고 거의 관심이 없는 친구 John과 이야기를 나누기 시작했습니다.그리고 LFU, LRU, FIFO의 실장 방법과 간단한 ENUM arg로 전환하는 방법에 대해 자세히 설명했습니다.그리고 제가 진정으로 원하는 것은 단순한 LRU뿐이라는 것을 깨달았습니다.앞의 투고는 무시하고 LRU에 대해 알려주시기 바랍니다.열거형으로 바꿀 수 있는... 아닌가? 좋아..여기 있습니다.
JDK만을 사용하는 가장 심플한 LRU.동시 버전과 비동시 버전을 모두 구현했습니다.
공통 인터페이스를 작성했습니다(필요한 기능이 몇 개 없기 때문에 미니멀리즘이지만, 사용 예에서는 도움이 됩니다만, XYZ의 기능을 보고 싶은 경우는 알려 주십시오).코드를 쓰기 위해 살고 있습니다.)
public interface LruCache<KEY, VALUE> {
void put ( KEY key, VALUE value );
VALUE get ( KEY key );
VALUE getSilent ( KEY key );
void remove ( KEY key );
int size ();
}
get Silent가 무엇인지 궁금할 수 있습니다.테스트에 사용합니다.getSilent는 항목의 LRU 점수를 변경하지 않습니다.
우선 비동시...
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {
Map<KEY, VALUE> map = new HashMap<> ();
Deque<KEY> queue = new LinkedList<> ();
final int limit;
public LruCacheNormal ( int limit ) {
this.limit = limit;
}
public void put ( KEY key, VALUE value ) {
VALUE oldValue = map.put ( key, value );
/*If there was already an object under this key,
then remove it before adding to queue
Frequently used keys will be at the top so the search could be fast.
*/
if ( oldValue != null ) {
queue.removeFirstOccurrence ( key );
}
queue.addFirst ( key );
if ( map.size () > limit ) {
final KEY removedKey = queue.removeLast ();
map.remove ( removedKey );
}
}
public VALUE get ( KEY key ) {
/* Frequently used keys will be at the top so the search could be fast.*/
queue.removeFirstOccurrence ( key );
queue.addFirst ( key );
return map.get ( key );
}
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
public void remove ( KEY key ) {
/* Frequently used keys will be at the top so the search could be fast.*/
queue.removeFirstOccurrence ( key );
map.remove ( key );
}
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
queue.removeFirstOccurrence는 캐시가 큰 경우 비용이 많이 드는 작업입니다.LinkedList를 예로 들어 요소 간 역방향 조회 해시 맵을 추가하여 제거 작업을 훨씬 빠르고 일관되게 수행할 수 있습니다.나도 시작했는데 그게 필요없다는 걸 깨달았어.하지만... 어쩌면...
put이 호출되면 키가 큐에 추가됩니다.get이 호출되면 키가 삭제되고 큐의 맨 위에 다시 추가됩니다.
캐시가 작고 아이템을 구축하는 데 비용이 많이 든다면 캐시가 좋습니다.캐시가 매우 큰 경우 특히 캐시의 핫 영역이 없는 경우 선형 검색이 병목일 수 있습니다.핫스팟의 강도가 높을수록 핫 아이템이 항상 선형 검색의 맨 위에 있으므로 선형 검색 속도가 빨라집니다.아무튼...이 처리를 고속화하기 위해 필요한 것은 삭제 조작이 있는 다른 Linked List를 작성하는 것입니다.이 작업을 통해 삭제는 해시 맵에서 키를 삭제하는 것과 같은 속도로 이루어집니다.
캐시가 1,000개 미만일 경우 문제가 없습니다.
다음은 동작 상황을 보여주는 간단한 테스트입니다.
public class LruCacheTest {
@Test
public void test () {
LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );
cache.put ( 0, 0 );
cache.put ( 1, 1 );
cache.put ( 2, 2 );
cache.put ( 3, 3 );
boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 0 ) == 0 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
cache.put ( 4, 4 );
cache.put ( 5, 5 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 0 ) == null || die ();
ok |= cache.getSilent ( 1 ) == null || die ();
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == 4 || die ();
ok |= cache.getSilent ( 5 ) == 5 || die ();
if ( !ok ) die ();
}
}
마지막 LRU 캐시는 단일 스레드이므로 동기화된 것으로 랩하지 마십시오.
여기 동시 버전에 대한 시도가 있습니다.
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;
public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {
private final ReentrantLock lock = new ReentrantLock ();
private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
private final Deque<KEY> queue = new LinkedList<> ();
private final int limit;
public ConcurrentLruCache ( int limit ) {
this.limit = limit;
}
@Override
public void put ( KEY key, VALUE value ) {
VALUE oldValue = map.put ( key, value );
if ( oldValue != null ) {
removeThenAddKey ( key );
} else {
addKey ( key );
}
if (map.size () > limit) {
map.remove ( removeLast() );
}
}
@Override
public VALUE get ( KEY key ) {
removeThenAddKey ( key );
return map.get ( key );
}
private void addKey(KEY key) {
lock.lock ();
try {
queue.addFirst ( key );
} finally {
lock.unlock ();
}
}
private KEY removeLast( ) {
lock.lock ();
try {
final KEY removedKey = queue.removeLast ();
return removedKey;
} finally {
lock.unlock ();
}
}
private void removeThenAddKey(KEY key) {
lock.lock ();
try {
queue.removeFirstOccurrence ( key );
queue.addFirst ( key );
} finally {
lock.unlock ();
}
}
private void removeFirstOccurrence(KEY key) {
lock.lock ();
try {
queue.removeFirstOccurrence ( key );
} finally {
lock.unlock ();
}
}
@Override
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
@Override
public void remove ( KEY key ) {
removeFirstOccurrence ( key );
map.remove ( key );
}
@Override
public int size () {
return map.size ();
}
public String toString () {
return map.toString ();
}
}
주요 차이점은 HashMap 대신 Concurrent HashMap을 사용하는 것과 Lock을 사용하는 것입니다(동기화할 수 있었지만...).
테스트한 적은 없지만 단순한 LRU 캐쉬처럼 보입니다. 단순한 LRU 맵이 필요한 사용 사례의 80%에 해당됩니다.
a, b, c 라이브러리를 사용하지 않는 이유를 제외하고 피드백을 환영합니다.제가 항상 라이브러리를 사용하지 않는 이유는 모든 전쟁 파일이 80MB가 되는 것은 아니며, 라이브러리를 쓰기 때문에 충분한 솔루션을 갖춘 libs를 플러그에 연결할 수 있고, 다른 캐시 공급자를 원할 때 플러그에 연결할 수 있기 때문입니다.:) 누군가 Guava나 ehcache 등을 필요로 할 때 포함시키고 싶지 않지만, 캐시를 플러그 대응으로 하면 제외하지 않습니다.
의존성 감소에는 그 나름의 보상이 있다.저는 이 작업을 더 단순하게, 더 빠르게, 또는 둘 다로 만드는 방법에 대한 피드백을 받고 싶습니다.
그리고 만약 누군가 떠날 준비가 되어 있다는 것을 안다면...
그래, 무슨 생각인지 알아Linked Hash Map에서 removeEldest 엔트리를 사용하지 않는 이유는 무엇입니까?그건 그렇고...단, LRU가 아닌 FIFO로 LRU를 구현하려고 했습니다.
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
위의 코드에 대해 이 테스트는 실패합니다.
cache.get ( 2 );
cache.get ( 3 );
cache.put ( 6, 6 );
cache.put ( 7, 7 );
ok |= cache.size () == 4 || die ( "size" + cache.size () );
ok |= cache.getSilent ( 2 ) == 2 || die ();
ok |= cache.getSilent ( 3 ) == 3 || die ();
ok |= cache.getSilent ( 4 ) == null || die ();
ok |= cache.getSilent ( 5 ) == null || die ();
removeEldestEntry를 사용한 빠르고 더러운 FIFO 캐시를 다음에 나타냅니다.
import java.util.*;
public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {
final int limit;
Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {
@Override
protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
return this.size () > limit;
}
};
public LruCacheNormal ( int limit ) {
this.limit = limit;
}
public void put ( KEY key, VALUE value ) {
map.put ( key, value );
}
public VALUE get ( KEY key ) {
return map.get ( key );
}
Java에서 LRU 캐시를 구현하려면 어떻게 해야 합니까?
public VALUE getSilent ( KEY key ) {
return map.get ( key );
}
public void remove ( KEY key ) {
map.remove ( key );
}
public int size () {
return map.size ();
}
public String toString() {
return map.toString ();
}
}
선입선출은 빠르다.찾아다니지 마세요.LRU 앞에 FIFO를 배치하여 대부분의 핫엔트리를 적절하게 처리할 수 있습니다.더 나은 LRU를 사용하려면 이 역요소-노드 기능이 필요합니다.
아무튼...코드를 작성했으니 다른 답을 살펴봅시다. 제가 뭘 놓쳤는지...처음 스캔했을 때요
LinkedHashMapO(1동기화가 합니다.수레바퀴를 재창조할 필요는 없습니다.
동시성을 높이기 위한 두 가지 옵션:
개를 . 수수성 。LinkedHashMap예: , 「 」, 「 」, 「 」:LinkedHashMap[4], index 0, 1, 2, 3로 .를 합니다.key%4 (오류)binary OR[key, 3]put/get/remove를
'는 2. ' LRU를 확장하여 할 수 .ConcurrentHashMap각 영역에 링크된 해시 맵과 같은 구조를 가지고 있습니다.은 금이 a a a a a a a a a a보다 더 발생합니다.LinkedHashMap동기화되어 있습니다. 。put ★★★★★★★★★★★★★★★★★」putIfAbsent리스트의 앞부분과 뒷부분만 잠근다(지역별).삭제 또는 취득 시 전체 영역을 잠글 필요가 있습니다.어떤 종류의 원자성 링크 리스트가 도움이 될지 궁금합니다. 리스트의 선두도 마찬가지일 것입니다.아마도 더 많이.
이 구조에서는 전체 순서가 유지되지 않고 지역별 순서만 유지됩니다.엔트리 수가 지역 수보다 훨씬 많은 경우 대부분의 캐시에서 이 정도면 충분합니다.각 영역에는 독자적인 엔트리 카운트가 필요합니다.이 값은 제거 트리거에 글로벌카운트가 아니라 사용됩니다. 수.ConcurrentHashMap열여섯 살
적당한 동시성 아래에서는 쓰기 쉽고 빠릅니다.
쓰기는 더 어렵지만 매우 높은 동시성으로 훨씬 더 잘 확장됩니다.에서는(「」나 「」와 ) 속도가 .
ConcurrentHashMapHashMap★★★★★★★★★★★★★★★★★★★★★★★」
두 가지 오픈소스 구현이 있습니다.
Apache Solr에는 동시 사용 가능LRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html
Concurrent Linked Hash Map용 오픈소스 프로젝트가 있습니다.http://code.google.com/p/concurrentlinkedhashmap/
java.util.concurrent 사용을 검토하겠습니다.Priority Blocking Queue. 각 요소의 "number Of Uses" 카운터에 의해 priority가 결정됩니다."number Of Uses" 카운터는 요소가 불변할 수 없음을 의미하므로 모든 동기화를 올바르게 하기 위해 매우 주의합니다.
요소 개체는 캐시 내의 개체에 대한 래퍼입니다.
class CacheElement {
private final Object obj;
private int numberOfUsers = 0;
CacheElement(Object obj) {
this.obj = obj;
}
... etc.
}
이것이 도움이 되기를 바랍니다.
import java.util.*;
public class Lru {
public static <K,V> Map<K,V> lruCache(final int maxSize) {
return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {
private static final long serialVersionUID = -3588047435434569014L;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
};
}
public static void main(String[] args ) {
Map<Object, Object> lru = Lru.lruCache(2);
lru.put("1", "1");
lru.put("2", "2");
lru.put("3", "3");
System.out.println(lru);
}
}
LRU 캐시는 멀티스레딩 시나리오에서도 사용할 수 있는 ConcurrentLinkedQueue 및 ConcurrentHashMap을 사용하여 구현할 수 있습니다.큐의 선두는 큐에 가장 오래 있었던 요소입니다.큐의 끝부분은 큐에 가장 짧은 시간 동안 있었던 요소입니다.맵에 요소가 있는 경우 LinkedQueue에서 해당 요소를 제거하고 꼬리에 삽입할 수 있습니다.
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
public class LRUCache<K,V> {
private ConcurrentHashMap<K,V> map;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size) {
this.size = size;
map = new ConcurrentHashMap<K,V>(size);
queue = new ConcurrentLinkedQueue<K>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
queue.remove(key);
queue.add(key);
return map.get(key);
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if(key == null || value == null) throw new NullPointerException();
if(map.containsKey(key) {
queue.remove(key);
}
if(queue.size() >= size) {
K lruKey = queue.poll();
if(lruKey != null) {
map.remove(lruKey);
}
}
queue.add(key);
map.put(key,value);
}
}
여기 LRU를 위한 구현이 있습니다. Priority를 사용했습니다.큐: 기본적으로 FIFO로 동작하며 스레드 세이프가 아닙니다.[ Used Comparator ]는 페이지 시간 작성과 에 근거하여 가장 최근에 사용한 시간에 대한 페이지 순서를 수행합니다.
검토 페이지 : 2, 1, 0, 2, 8, 2, 4
: 2 입니다.
: 1 입니다.
0 입니다.
2번: 2번입니다. time updated (최종 접근 시간 됨)
장애PAGE:, PAGE: 8로됨, PAGE: 1, PAGE: 8
8 입니다.
2번: 2번입니다. time updated (최종 접근 시간 됨)
장애PAGE: PAGE: 4로, 0, 4로 대체
: 4 입니다.
산출량
LRUCache 페 l l
8, : 8, : 136595701974
2, : 2, () : 1365957020074
4, : 4, : ) : 1365957020174
여기에 코드를 입력합니다.
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
public class LRUForCache {
private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
public static void main(String[] args) throws InterruptedException {
System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
System.out.println("----------------------------------------------\n");
LRUForCache cache = new LRUForCache();
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("1"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("0"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("8"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("2"));
Thread.sleep(100);
cache.addPageToQueue(new LRUPage("4"));
Thread.sleep(100);
System.out.println("\nLRUCache Pages");
System.out.println("-------------");
cache.displayPriorityQueue();
}
public synchronized void addPageToQueue(LRUPage page){
boolean pageExists = false;
if(priorityQueue.size() == 3){
Iterator<LRUPage> iterator = priorityQueue.iterator();
while(iterator.hasNext()){
LRUPage next = iterator.next();
if(next.getPageName().equals(page.getPageName())){
/* wanted to just change the time, so that no need to poll and add again.
but elements ordering does not happen, it happens only at the time of adding
to the queue
In case somebody finds it, plz let me know.
*/
//next.setPageCreationTime(page.getPageCreationTime());
priorityQueue.remove(next);
System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
pageExists = true;
break;
}
}
if(!pageExists){
// enable it for printing the queue elemnts
//System.out.println(priorityQueue);
LRUPage poll = priorityQueue.poll();
System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());
}
}
if(!pageExists){
System.out.println("Page added into cache is : " + page.getPageName());
}
priorityQueue.add(page);
}
public void displayPriorityQueue(){
Iterator<LRUPage> iterator = priorityQueue.iterator();
while(iterator.hasNext()){
LRUPage next = iterator.next();
System.out.println(next);
}
}
}
class LRUPage{
private String pageName;
private long pageCreationTime;
public LRUPage(String pagename){
this.pageName = pagename;
this.pageCreationTime = System.currentTimeMillis();
}
public String getPageName() {
return pageName;
}
public long getPageCreationTime() {
return pageCreationTime;
}
public void setPageCreationTime(long pageCreationTime) {
this.pageCreationTime = pageCreationTime;
}
@Override
public boolean equals(Object obj) {
LRUPage page = (LRUPage)obj;
if(pageCreationTime == page.pageCreationTime){
return true;
}
return false;
}
@Override
public int hashCode() {
return (int) (31 * pageCreationTime);
}
@Override
public String toString() {
return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
}
}
class LRUPageComparator implements Comparator<LRUPage>{
@Override
public int compare(LRUPage o1, LRUPage o2) {
if(o1.getPageCreationTime() > o2.getPageCreationTime()){
return 1;
}
if(o1.getPageCreationTime() < o2.getPageCreationTime()){
return -1;
}
return 0;
}
}
동기화된 블록 없이 LRU 캐시를 동시에 구현하여 테스트한 최고의 성능을 보여 줍니다.
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
/**
* @param key - may not be null!
* @param value - may not be null!
*/
public void put(final Key key, final Value value) {
if (map.containsKey(key)) {
queue.remove(key); // remove the key from the FIFO queue
}
while (queue.size() >= maxSize) {
Key oldestKey = queue.poll();
if (null != oldestKey) {
map.remove(oldestKey);
}
}
queue.add(key);
map.put(key, value);
}
/**
* @param key - may not be null!
* @return the value associated to the given key or null
*/
public Value get(final Key key) {
return map.get(key);
}
}
이 LRU 캐시는 LinkedHashMap을 캡슐화하고 쥬시 스팟을 보호하는 간단한 동기화 잠금으로 동시성을 처리합니다.사용하면서 요소를 '촉각'하여 '최신' 요소가 다시 '최신' 요소가 되도록 합니다.또한 저는 최소 수명을 가진 요소를 요구했습니다.이것을 '최대 아이돌 시간'이라고 생각할 수도 있습니다.그러면 퇴출 대상이 됩니다.
하지만, 저는 행크의 결론에 동의하고 답변을 받아들였습니다. 만약 제가 오늘 이것을 다시 시작한다면, 저는 Guava의 것을 확인했을 것입니다.CacheBuilder.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class MaxIdleLRUCache<KK, VV> {
final static private int IDEAL_MAX_CACHE_ENTRIES = 128;
public interface DeadElementCallback<KK, VV> {
public void notify(KK key, VV element);
}
private Object lock = new Object();
private long minAge;
private HashMap<KK, Item<VV>> cache;
public MaxIdleLRUCache(long minAgeMilliseconds) {
this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
this(minAgeMilliseconds, idealMaxCacheEntries, null);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
this.minAge = minAgeMilliseconds;
this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
private static final long serialVersionUID = 1L;
// This method is called just after a new entry has been added
public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
// let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
long age = System.currentTimeMillis() - eldest.getValue().birth;
if (age > MaxIdleLRUCache.this.minAge) {
if ( callback != null ) {
callback.notify(eldest.getKey(), eldest.getValue().payload);
}
return true; // remove it
}
return false; // don't remove this element
}
};
}
public void put(KK key, VV value) {
synchronized ( lock ) {
// System.out.println("put->"+key+","+value);
cache.put(key, new Item<VV>(value));
}
}
public VV get(KK key) {
synchronized ( lock ) {
// System.out.println("get->"+key);
Item<VV> item = getItem(key);
return item == null ? null : item.payload;
}
}
public VV remove(String key) {
synchronized ( lock ) {
// System.out.println("remove->"+key);
Item<VV> item = cache.remove(key);
if ( item != null ) {
return item.payload;
} else {
return null;
}
}
}
public int size() {
synchronized ( lock ) {
return cache.size();
}
}
private Item<VV> getItem(KK key) {
Item<VV> item = cache.get(key);
if (item == null) {
return null;
}
item.touch(); // idle the item to reset the timeout threshold
return item;
}
private static class Item<T> {
long birth;
T payload;
Item(T payload) {
this.birth = System.currentTimeMillis();
this.payload = payload;
}
public void touch() {
this.birth = System.currentTimeMillis();
}
}
}
캐시에서는 일반적으로 프록시 오브젝트(URL, String...)를 통해 데이터를 검색하기 때문에 인터페이스적으로는 맵이 필요하지만 큐와 같은 구조가 필요합니다.내부적으로는 Priority-Queue와 HashMap의 두 가지 데이터 구조를 유지합니다.이것은 O(1)시간 내에 모든 것을 실행할 수 있는 실장입니다.
여기 내가 꽤 빨리 만든 수업이 있다.
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
int maxSize;
int currentSize = 0;
Map<K, ValueHolder<K, V>> map;
LinkedList<K> queue;
public LRUCache(int maxSize)
{
this.maxSize = maxSize;
map = new HashMap<K, ValueHolder<K, V>>();
queue = new LinkedList<K>();
}
private void freeSpace()
{
K k = queue.remove();
map.remove(k);
currentSize--;
}
public void put(K key, V val)
{
while(currentSize >= maxSize)
{
freeSpace();
}
if(map.containsKey(key))
{//just heat up that item
get(key);
return;
}
ListNode<K> ln = queue.add(key);
ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
map.put(key, rv);
currentSize++;
}
public V get(K key)
{
ValueHolder<K, V> rv = map.get(key);
if(rv == null) return null;
queue.remove(rv.queueLocation);
rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
return rv.value;
}
}
class ListNode<K>
{
ListNode<K> prev;
ListNode<K> next;
K value;
public ListNode(K v)
{
value = v;
prev = null;
next = null;
}
}
class ValueHolder<K,V>
{
V value;
ListNode<K> queueLocation;
public ValueHolder(V value, ListNode<K> ql)
{
this.value = value;
this.queueLocation = ql;
}
}
class LinkedList<K>
{
ListNode<K> head = null;
ListNode<K> tail = null;
public ListNode<K> add(K v)
{
if(head == null)
{
assert(tail == null);
head = tail = new ListNode<K>(v);
}
else
{
tail.next = new ListNode<K>(v);
tail.next.prev = tail;
tail = tail.next;
if(tail.prev == null)
{
tail.prev = head;
head.next = tail;
}
}
return tail;
}
public K remove()
{
if(head == null)
return null;
K val = head.value;
if(head.next == null)
{
head = null;
tail = null;
}
else
{
head = head.next;
head.prev = null;
}
return val;
}
public void remove(ListNode<K> ln)
{
ListNode<K> prev = ln.prev;
ListNode<K> next = ln.next;
if(prev == null)
{
head = next;
}
else
{
prev.next = next;
}
if(next == null)
{
tail = prev;
}
else
{
next.prev = prev;
}
}
}
이걸 어떻게 하는지 보여줄게.키는 목록 앞쪽에 있는 가장 오래된 키와 함께 링크된 목록에 저장됩니다(새 키는 뒤로 이동). 따라서 무언가를 '꺼내기'해야 할 때는 큐 앞에서 해당 키를 사용하여 맵에서 값을 삭제합니다.항목이 참조되면 맵에서 ValueHolder를 가져온 후 큐엘로케이션 변수를 사용하여 큐의 현재 위치에서 키를 제거한 후 큐의 맨 뒤에 배치합니다(현재 가장 최근에 사용됨).물건을 더하는 것은 거의 같다.
여기에는 분명 많은 오류가 있을 것이고, 저는 어떤 동기화도 구현하지 않았습니다.단, 이 클래스는 O(1)캐시에 추가, O(1)오래된 아이템의 삭제, O(1)캐시 아이템의 취득을 제공합니다.사소한 동기화(모든 공개 메서드를 동기화)라도 실행 시간으로 인해 잠금 경합이 거의 발생하지 않습니다.만약 누군가 교묘한 동기화 기술을 가지고 있다면 나는 매우 흥미가 있을 것이다.또한 맵에 대해 max size 변수를 사용하여 구현할 수 있는 몇 가지 추가 최적화가 있을 것입니다.
Concurrent Skip List Map을 참조하십시오.요소가 이미 캐시에 포함되어 있는 경우 테스트 및 삭제하기 위한 로그(n) 시간과 요소를 다시 추가하기 위한 일정한 시간이 주어집니다.
LRU 오더를 강제로 주문하고 캐시가 꽉 찼을 때 최신 아이템을 폐기하려면 카운터 등 몇 가지와 래퍼 요소만 있으면 됩니다.
저의 짧은 실장입니다.비판이나 개선 부탁드립니다!
package util.collection;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* Limited size concurrent cache map implementation.<br/>
* LRU: Least Recently Used.<br/>
* If you add a new key-value pair to this cache after the maximum size has been exceeded,
* the oldest key-value pair will be removed before adding.
*/
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private int currentSize = 0;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
private synchronized void freeSpace() {
Key key = queue.poll();
if (null != key) {
map.remove(key);
currentSize = map.size();
}
}
public void put(Key key, Value val) {
if (map.containsKey(key)) {// just heat up that item
put(key, val);
return;
}
while (currentSize >= maxSize) {
freeSpace();
}
synchronized(this) {
queue.add(key);
map.put(key, val);
currentSize++;
}
}
public Value get(Key key) {
return map.get(key);
}
}
여기 이 문제에 대한 저만의 구현이 있습니다.
simplelrucache는 스레드 세이프하고 매우 단순한 분산되지 않은 LRU 캐싱을 TTL 지원으로 제공합니다.다음 두 가지 구현이 있습니다.
- ConcurrentLinkedHashMap을 기반으로 동시 실행
- Linked Hash Map을 기반으로 동기화됨
다음 URL에서 찾을 수 있습니다.http://code.google.com/p/simplelrucache/
가장 좋은 방법은 요소의 삽입 순서를 유지하는 Linked Hash Map을 사용하는 것입니다.다음은 샘플 코드입니다.
public class Solution {
Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
this.cache = new LinkedHashMap<Integer,Integer>(capacity);
this.capacity = capacity;
}
// This function returns false if key is not
// present in cache. Else it moves the key to
// front by first removing it and then adding
// it, and returns true.
public int get(int key) {
if (!cache.containsKey(key))
return -1;
int value = cache.get(key);
cache.remove(key);
cache.put(key,value);
return cache.get(key);
}
public void set(int key, int value) {
// If already present, then
// remove it first we are going to add later
if(cache.containsKey(key)){
cache.remove(key);
}
// If cache size is full, remove the least
// recently used.
else if (cache.size() == capacity) {
Iterator<Integer> iterator = cache.keySet().iterator();
cache.remove(iterator.next());
}
cache.put(key,value);
}
}
자바 코드를 사용하여 더 나은 LRU 캐시를 찾고 있습니다. LRU 캐시 를 Java 를 사용하여 할 수 ?LinkedHashMap ★★★★★★★★★★★★★★★★★」Collections#synchronizedMap 사용하고 있는LRUMap implements Map는 정상적으로 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ArrayIndexOutofBoundException는, 을 사용해 주세요.메서드는 최근 개체를 큐 앞으로 이동합니다.
private void moveToFront(int index) {
if (listHead != index) {
int thisNext = nextElement[index];
int thisPrev = prevElement[index];
nextElement[thisPrev] = thisNext;
if (thisNext >= 0) {
prevElement[thisNext] = thisPrev;
} else {
listTail = thisPrev;
}
//old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
// prev[0 old head] = new head right ; next[new head] = old head
prevElement[index] = -1;
nextElement[index] = listHead;
prevElement[listHead] = index;
listHead = index;
}
}
get(Object key) ★★★★★★★★★★★★★★★★★」put(Object key, Object value)는 위의 메서드를 합니다.moveToFront★★★★★★ 。
행크가 준 답변에 코멘트를 추가하고 싶었지만 어떻게 할 수 없는지를 코멘트로 취급해 주십시오.
LinkedHashMap은 컨스트럭터에서 전달된 파라미터에 따라 접근순서도 유지합니다.순서를 유지하기 위해 두 줄로 된 목록을 유지합니다(LinkedHashMap 참조).엔트리)
@pacerier, 요소가 다시 추가되면 Linked Hash Map이 반복하는 동안 동일한 순서를 유지하는 것은 맞지만, 이는 삽입 순서 모드일 경우에만 해당됩니다.
Linked Hash Map의 Java 문서에서 찾은 내용입니다.엔트리 오브젝트
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
이 메서드는 최근에 접근한 요소를 목록의 끝으로 이동합니다.따라서 Linked Hash Map은 모두 LRUCache를 구현하기 위한 최적의 데이터 구조입니다.
Java의 Linked Hash Map 컬렉션을 사용한 다른 아이디어와 간단한 구현.
LinkedHashMap은 removeEldestEntry 메서드를 제공했습니다.이 메서드는 예에서 설명한 방법으로 덮어쓸 수 있습니다.기본적으로는 이 컬렉션 구조의 구현은 false입니다.이 구조의 참과 크기가 초기 용량을 초과하면 오래된 요소나 오래된 요소가 제거됩니다.
pageno가 정수이고 page content가 pageno 값 문자열을 유지하는 경우 pageno와 페이지 내용을 가질 수 있습니다.
import java.util.LinkedHashMap; import java.util.Map; /** * @author Deepak Singhvi * */ public class LRUCacheUsingLinkedHashMap { private static int CACHE_SIZE = 3; public static void main(String[] args) { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99"); System.out.println("----------------------------------------------\n"); // accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map, LinkedHashMap<Integer,String> lruCache = new LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) { private static final long serialVersionUID = 1L; protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) { return size() > CACHE_SIZE; } }; lruCache.put(2, "2"); lruCache.put(1, "1"); lruCache.put(0, "0"); System.out.println(lruCache + " , After first 3 pages in cache"); lruCache.put(2, "2"); System.out.println(lruCache + " , Page 2 became the latest page in the cache"); lruCache.put(8, "8"); System.out.println(lruCache + " , Adding page 8, which removes eldest element 2 "); lruCache.put(2, "2"); System.out.println(lruCache+ " , Page 2 became the latest page in the cache"); lruCache.put(4, "4"); System.out.println(lruCache+ " , Adding page 4, which removes eldest element 1 "); lruCache.put(99, "99"); System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 "); } }
위의 코드 실행 결과는 다음과 같습니다.
Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
{2=2, 1=1, 0=0} , After first 3 pages in cache
{2=2, 1=1, 0=0} , Page 2 became the latest page in the cache
{1=1, 0=0, 8=8} , Adding page 8, which removes eldest element 2
{0=0, 8=8, 2=2} , Page 2 became the latest page in the cache
{8=8, 2=2, 4=4} , Adding page 4, which removes eldest element 1
{2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8
@sanjanab 컨셉(단, 수정 후)에 따라 필요에 따라 삭제한 아이템을 조작할 수 있는 컨슈머를 제공하는 LRUCache 버전을 만들었습니다.
public class LRUCache<K, V> {
private ConcurrentHashMap<K, V> map;
private final Consumer<V> onRemove;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size, Consumer<V> onRemove) {
this.size = size;
this.onRemove = onRemove;
this.map = new ConcurrentHashMap<>(size);
this.queue = new ConcurrentLinkedQueue<>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
if (queue.remove(key)) {
queue.add(key);
return map.get(key);
}
return null;
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");
V existing = map.get(key);
if (existing != null) {
queue.remove(key);
onRemove.accept(existing);
}
if (map.size() >= size) {
K lruKey = queue.poll();
if (lruKey != null) {
V removed = map.remove(lruKey);
onRemove.accept(removed);
}
}
queue.add(key);
map.put(key, value);
}
}
Android는 LRU 캐시를 구현합니다.코드는 명확하고 간단합니다.
언급URL : https://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java
'programing' 카테고리의 다른 글
| href 태그 사용 안 함 (0) | 2023.01.20 |
|---|---|
| UTC 시간 가져오기(PHP) (0) | 2023.01.20 |
| 라디오 버튼을 끄려면 어떻게 해야 하나요? (0) | 2023.01.20 |
| SELECT의 변수 할당 평가 순서는 반환되는 행 순서와 다를 수 있습니다.어떤 상황에서 이런 일이 일어날 수 있나요? (0) | 2023.01.20 |
| 요소에 JavaScript의 클래스가 포함되어 있는지 확인하시겠습니까? (0) | 2023.01.20 |