Java로 LRU 캐시를 어떻게 구현 하시겠습니까?
EHCache 또는 OSCache 등을 말하지 마십시오.이 질문의 목적 상 SDK 만 사용하여 직접 구현하고 싶다고 가정합니다. 캐시가 멀티 스레드 환경에서 사용될 것이라면 어떤 데이터 구조를 사용 하시겠습니까? 이미 LinkedHashMap 과 Collections # synchronizedMap을 사용하여 구현 했지만 새로운 동시 컬렉션 중 하나가 더 나은 후보가 될지 궁금합니다.
업데이트 : 이 너겟을 발견했을 때 Yegge의 최신 내용을 읽었습니다 .
지속적인 액세스가 필요하고 게재 신청서를 유지하려는 경우 정말 훌륭한 데이터 구조 인 LinkedHashMap보다 더 나은 방법은 없습니다. 더 멋진 방법은 동시 버전이있는 경우뿐입니다. 그러나 아아.
위에서 언급 한 LinkedHashMap+ Collections#synchronizedMap구현을 시작하기 전에 거의 똑같은 생각을했습니다 . 내가 그냥 간과하지 않았다는 것을 알고 반갑습니다.
지금까지의 답변에 따르면, 동시성이 높은 LRU에 대한 최선의 방법은 사용하는 동일한 논리를 사용 하여 ConcurrentHashMap 을 확장 하는 것 같습니다 LinkedHashMap.
나는 이러한 제안을 많이 좋아하지만, 지금은 LinkedHashMap+를 고수 할 것이라고 생각 Collections.synchronizedMap합니다. 나중에 이것을 다시 방문하면 extends ConcurrentHashMap와 같은 방식으로 LinkedHashMap확장 작업을 수행 할 것입니다 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));
또는이 Apache Commons 데이터 구조를 사용하십시오.
오늘 처음부터 다시이 작업을 수행 한 경우 Guava 's를 사용 CacheBuilder합니다.
이것은 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 플래그는 가져 오기 및 넣기 액세스를 추적합니다. JavaDocs를 참조하십시오. 생성자에 대한 true 플래그가없는 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.boon.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 인수로 전환 할 수있는 방법에 대해 깊이있게 설명한 다음, 제가 원했던 모든 것을 깨달았습니다 간단한 LRU였습니다. 따라서 이전 게시물을 무시하고 열거 형을 통해 전환 할 수있는 LRU / LFU / FIFO 캐시를보고 싶다면 알려주십시오. 알았어
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 ();
}
getSilent 가 무엇인지 궁금 할 것 입니다. 나는 이것을 테스트에 사용한다. 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를 예로 들어 요소에서 노드로 역 조회 해시 맵을 추가하여 제거 작업을보다 신속하고 일관성있게 만들 수 있습니다. 나도 시작했지만 필요하지 않다는 것을 깨달았다. 그러나 아마도...
때 풋이 라고, 키는 큐에 추가됩니다. 때 GET가 호출되면 키가 제거됩니다 큐의 상단에 다시는-했다.
캐시가 작고 아이템을 만드는 데 비용이 많이 든다면 캐시가 좋습니다. 캐시가 실제로 큰 경우, 특히 캐시 공간이 부족한 경우 선형 검색이 병목 현상이 될 수 있습니다. 핫스팟이 더 강할수록 핫 항목이 항상 선형 검색의 맨 위에 있으므로 선형 검색이 더 빨라집니다. 어쨌든 ... 이보다 빠르게 진행되는 데 필요한 것은 remove에 대한 노드 조회를 역으로 수행하는 remove 작업이있는 다른 LinkedList를 작성하는 것입니다. 제거하면 해시 맵에서 키를 제거하는 것만 큼 빠릅니다.
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 대신 ConcurrentHashMap을 사용하고 Lock을 사용한다는 것입니다 (동기화로 벗어날 수는 있지만 ...).
나는 그것을 테스트하지 않았지만 간단한 LRU 맵이 필요한 사용 사례의 80 %에서 작동 할 수있는 간단한 LRU 캐시처럼 보입니다.
라이브러리 a, b 또는 c를 사용하지 않는 이유를 제외하고 피드백을 환영합니다. 항상 라이브러리를 사용하지 않는 이유는 모든 war 파일이 항상 80MB가되기를 원하지 않기 때문에 라이브러리를 작성하기 때문에 라이브러리를 작성하여 충분한 솔루션을 사용하여 libs를 플러그인 가능하게 만들고 누군가가 플러그인 할 수 있기 때문입니다. 원하는 경우 다른 캐시 공급자에서-. :) 언제 누군가 Guava 또는 ehcache 또는 다른 것을 포함하고 싶지 않은지 알지 못하지만 캐싱을 가능하게 만들면 제외하지 않습니다.
의존성 감소에는 자체 보상이 있습니다. 나는 이것을 더 간단하거나 빠르게 만드는 방법에 대한 피드백을 받고 싶습니다.
또한 갈 준비가 된 사람이 있다면 ...
알았어 .. 네가 무슨 생각을하는지 알아 .. 왜 LinkedHashMap에서 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 );
}
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 ();
}
}
FIFO는 빠릅니다. 주변을 검색하지 않습니다. LRU 앞에 FIFO를 배치 할 수 있으며 대부분의 핫 엔트리를 아주 잘 처리 할 수 있습니다. 더 나은 LRU는 노드 기능에 대한 역방향 요소가 필요합니다.
어쨌든 ... 이제 코드를 작성 했으므로 다른 답변을 살펴보고 처음으로 스캔 한 내용을 보도록하겠습니다.
LinkedHashMapO (1)이지만 동기화가 필요합니다. 바퀴를 재발 명할 필요가 없습니다.
동시성 향상을위한 2 가지 옵션 :
1. 여러 개 LinkedHashMap를 만들어 해시합니다 (예 :) LinkedHashMap[4], index 0, 1, 2, 3. 키에서 key%4(또는 binary ORon [key, 3]) put / get / remove를 수행 할 맵을 선택하십시오.
2.를 확장 ConcurrentHashMap하고 내부의 각 영역에 구조와 같은 링크 된 해시 맵을 가짐 으로써 '거의'LRU를 수행 할 수 있습니다. 잠금 LinkedHashMap은 동기화 된 것보다 더 세밀하게 발생 합니다. 켜짐 put또는 putIfAbsent머리와 목록의 꼬리 만 잠금 (지역 당)이 필요하다. 제거하거나 전체 지역을 확보해야합니다. 일종의 Atomic 연결 목록이 여기에 도움이 될지 궁금합니다. 아마 더
구조는 전체 주문을 유지하지 않고 지역 당 주문 만 유지합니다. 항목 수가 영역 수보다 훨씬 많으면 대부분의 캐시에 충분합니다. 각 지역마다 고유 한 항목 수를 가져야하며 이는 제거 트리거에 대한 전체 수보다 사용됩니다. 의 기본 지역 수 ConcurrentHashMap는 16 개로 오늘날 대부분의 서버에 충분합니다.
중간 수준의 동시성에서는 쓰기가 쉽고 빠릅니다.
쓰기가 더 어려울 수 있지만 동시성이 높을수록 확장 성이 훨씬 좋습니다. 일반 액세스의 경우 속도
ConcurrentHashMap가 느려집니다 (HashMap동시성이없는 경우보다 속도가 느림 ).
두 가지 오픈 소스 구현이 있습니다.
Apache Solr에는 ConcurrentLRUCache가 있습니다 : https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html
ConcurrentLinkedHashMap을위한 오픈 소스 프로젝트가 있습니다 : http://code.google.com/p/concurrentlinkedhashmap/
각 요소의 "numberOfUses"카운터에 의해 결정된 우선 순위로 java.util.concurrent.PriorityBlockingQueue를 사용하는 것이 좋습니다. 나는 것 매우, 매우 신중 은 "numberOfUses"카운터 요소가 불변 수 없다는 것을 알 수 있듯이, 내 모든 동기화 올바른 얻을.
요소 객체는 캐시의 객체에 대한 래퍼입니다.
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 구현입니다. PriorityQueue를 사용했는데 기본적으로 스레드 안전이 아닌 FIFO로 작동합니다. 사용 된 비교기는 페이지 시간 작성을 기반으로하고 가장 최근에 사용 된 시간 동안 페이지 순서를 수행합니다.
고려할 페이지 : 2, 1, 0, 2, 8, 2, 4
캐시에 추가 된 페이지 : 2 캐시에 추가 된 페이지
: 1
캐시에 추가 된
페이지 : 0 페이지 : 2 캐시에 이미 존재합니다. 마지막 액세스 시간 업데이트
페이지 결함, PAGE : 1, PAGE : 8로 대체 됨
캐시에 추가 된 페이지는 : 8
Page : 2 캐시에 이미 존재합니다. 마지막으로 액세스 한 시간 업데이트
페이지 결함, PAGE : 0, PAGE로 대체 : 4
캐시에 추가 된 페이지는 다음과 같습니다. 4
산출
LRUCache 페이지
-------------
PageName : 8, PageCreationTime : 1365957019974
PageName : 2, PageCreationTime : 1365957020074
PageName : 4, PageCreationTime : 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을 캡슐화하고 수분이 많은 지점을 보호하는 간단한 동기화 잠금으로 동시성을 처리합니다. 사용되는 요소를 "터치"하여 다시 "최신"요소가되어 실제로 LRU가되도록합니다. 또한 내 요소에 최소 수명이 있어야하는데, "최대 유휴 시간"이 허용 된 것으로 생각하면 퇴거를 당할 수 있습니다.
그러나 나는 Hank의 결론에 동의하고 대답을 받아 들였습니다. 오늘 다시 시작한다면 Guava 's를 확인하십시오 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를 가져온 다음 queuelocation 변수를 사용하여 큐의 현재 위치에서 키를 제거한 다음 큐의 뒷면 (현재 가장 최근에 사용됨)에 키를 놓습니다. 물건을 추가하는 것은 거의 동일합니다.
여기에 많은 오류가 있다고 확신하고 동기화를 구현하지 않았습니다. 그러나이 클래스는 캐시에 O (1) 추가, 오래된 항목의 O (1) 제거 및 캐시 항목의 O (1) 검색을 제공합니다. 사소한 동기화 (모든 공용 메소드 만 동기화)조차도 런타임으로 인해 잠금 경합이 거의 없습니다. 누구든지 영리한 동기화 트릭을 가지고 있다면 매우 관심이 있습니다. 또한 맵과 관련하여 maxsize 변수를 사용하여 구현할 수있는 추가 최적화가 있다고 확신합니다.
ConcurrentSkipListMap을 살펴보십시오 . 캐시에 이미 포함 된 요소를 테스트하고 제거하는 데 필요한 log (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는 TTL을 지원하는 스레드 안전하고 매우 간단한 비 분산 LRU 캐싱을 제공합니다. 다음 두 가지 구현을 제공합니다.
- ConcurrentLinkedHashMap 기반 동시
- LinkedHashMap을 기반으로 동기화
http://code.google.com/p/simplelrucache/에서 찾을 수 있습니다.
Java 코드를 사용하여 더 나은 LRU 캐시를 찾고 있습니다. 당신이 사용하는 자바 LRU 캐시 코드를 공유 할 수 있나요 LinkedHashMap과 Collections#synchronizedMap? 현재 사용 LRUMap implements Map하고 있으며 코드는 정상적으로 작동하지만 ArrayIndexOutofBoundException아래 방법으로 500 명의 사용자를 사용하여 부하 테스트를 받고 있습니다. 이 메소드는 최근 오브젝트를 큐의 맨 앞으로 이동합니다.
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.Entry 참조).
@Pacerier 요소가 다시 추가되면 LinkedHashMap이 반복하는 동안 동일한 순서를 유지하지만 삽입 순서 모드의 경우에만 올바른 것이 맞습니다.
이것이 LinkedHashMap.Entry 객체의 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);
}
}
이 메소드는 최근에 액세스 한 요소를 목록의 끝으로 이동합니다. 따라서 LinkedHashMap은 LRUCache를 구현하기위한 최상의 데이터 구조입니다.
Java의 LinkedHashMap 컬렉션을 사용하는 또 다른 생각과 간단한 구현.
LinkedHashMap은 removeEldestEntry 메소드를 제공했으며 예제에서 언급 한 방식으로 대체 될 수 있습니다. 기본적으로이 컬렉션 구조의 구현은 false입니다. 이 구조의 크기와 크기가 초기 용량을 초과하면 가장 오래되었거나 오래된 요소가 제거됩니다.
필자의 경우 pageno와 page content를 가질 수 있습니다. pageno는 정수이며 pagecontent 나는 페이지 번호 값 문자열을 유지했습니다.
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);
}
}
안드로이드는 LRU 캐시 의 구현을 제공합니다 . 코드는 깨끗하고 간단합니다.
참고 URL : https://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java
'Programing' 카테고리의 다른 글
| 리눅스 개발 프로젝트를위한 Clang vs GCC (0) | 2020.05.29 |
|---|---|
| 컴파일러가 일반 함수보다 람다를 더 잘 최적화 할 수있는 이유는 무엇입니까? (0) | 2020.05.29 |
| 파이썬의 SFTP? (0) | 2020.05.29 |
| LINQ를 사용하여 데이터를 피벗 할 수 있습니까? (0) | 2020.05.29 |
| CSV 파일을 SQL Server로 가져 오기 (0) | 2020.05.29 |