LRUキャッシュの実装
8490 ワード
LinkedHashMapは、既存のLRU実装です.しかし,コンカレントメカニズムが欠けており,フルロード削除条件(removeEldestEntry)が実現されていないため,LinkedHashMapは拡張を予約したLRUクラスであると考えられる.
この文書では、クラスを継承してLRUキャッシュをさらに実装します.
まず、再入可能ロックを併用します.これは、読み取りロック後に書き込み可能かどうか、書き込みロック後に読み取り可能かどうかの問題です.一般的に、読んだ後、書くと汚いデータが発生します.書いた後、読むと問題ありません.
再ロック可能な読み書きロック、ロック順序テスト:
テスト結果:
LRUは、最近アクセスされたデータが常にキャッシュから最も速く読み取れることを意味する.そこで、次に、最新データの位置とキャッシュがいっぱいになったときのデータの処理をテストします.
テスト結果:
本明細書で使用するLRUキャッシュクラス:
(参考:このクラスは私のオープンソースデータベースプロジェクトで、キャッシュ部分の実装クラスです.
http://code.google.com/p/ojadbにアクセスしてプロジェクト全体を表示できます.
この文書では、クラスを継承してLRUキャッシュをさらに実装します.
まず、再入可能ロックを併用します.これは、読み取りロック後に書き込み可能かどうか、書き込みロック後に読み取り可能かどうかの問題です.一般的に、読んだ後、書くと汚いデータが発生します.書いた後、読むと問題ありません.
再ロック可能な読み書きロック、ロック順序テスト:
package lock;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LockTest1{
final static ReadWriteLock rwlock = new ReentrantReadWriteLock();
final static Lock readLock = rwlock.readLock();
final static Lock writeLock = rwlock.writeLock();
public static void main(String[] args) throws InterruptedException {
System.out.println("test readlock-writelock");
lockR2W();
System.out.println("test writelock-readlock");
lockW2R();
System.out.println("test readlock-readlock");
lockRR();
System.out.println("test writelock-writelock");
lockWW();
}
private static void lockWW() {
writeLock.lock();
System.out.println("w lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when w lock, cannot w lock again.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
writeLock.unlock();
System.out.println("w unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
private static void lockRR() {
readLock.lock();
System.out.println("r lock.");
readLock.lock();
System.out.println("r lock.");
readLock.unlock();
System.out.println("r unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockW2R() throws InterruptedException {
writeLock.lock();
System.out.println("w lock.");
if (readLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("r lock.");
else
System.out.println("when w lock, cannot r lock.");
writeLock.unlock();
System.out.println("w unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockR2W() {
readLock.lock();
System.out.println("r lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when r lock, cannot w lock.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
readLock.unlock();
System.out.println("r unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
}
テスト結果:
test readlock-writelock
r lock.
when r lock, cannot w lock.
r unlock.
test writelock-readlock
w lock.
r lock.
w unlock.
r unlock.
test readlock-readlock
r lock.
r lock.
r unlock.
r unlock.
test writelock-writelock
w lock.
w lock.
w unlock.
w unlock.
LRUは、最近アクセスされたデータが常にキャッシュから最も速く読み取れることを意味する.そこで、次に、最新データの位置とキャッシュがいっぱいになったときのデータの処理をテストします.
package lru;
import java.util.Iterator;
import java.util.Map.Entry;
public class LRUTest{
public static void main(String[] args) {
int maxCapacity = 5;
OjadbMap<Integer, String> lruMap = new OjadbMap<Integer, String>(maxCapacity);
for (int i = 0; i < maxCapacity; i++) {
lruMap.put(i, "data[" + i + "]");
}
lruMap.get(3);
Iterator<Entry<Integer, String>> iter = lruMap.entrySet().iterator();
while (iter.hasNext()) {
System.out.println(iter.next().getValue());
}
System.out.println();
lruMap.put(9, "data[ 9 ]");
Iterator<Entry<Integer, String>> iter1 = lruMap.entrySet().iterator();
while (iter1.hasNext()) {
System.out.println(iter1.next().getValue());
}
}
}
テスト結果:
data[0]
data[1]
data[2]
data[4]
data[3] // 。
data[1]
data[2]
data[4]
data[3]
data[ 9 ] // ( , )。
本明細書で使用するLRUキャッシュクラス:
(参考:このクラスは私のオープンソースデータベースプロジェクトで、キャッシュ部分の実装クラスです.
http://code.google.com/p/ojadbにアクセスしてプロジェクト全体を表示できます.
/*******************************************************************************************
* oJadb is free software: you can redistribute it and/or modify it under
* the terms of the GNU General Public License as published by the Free Software Foundation,
* either version 3 of the License, or (at your option) any later version.
*
* oJadb is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along with this library.
* If not, see <http://www.gnu.org/licenses/>.
*
* Author:EricHan
* Time:2008-8-28
******************************************************************************************/
package lru;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class OjadbMap<K, V> extends LinkedHashMap<K, V>{
private static final long serialVersionUID = -6970580442519842034L;
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//private final Lock lock = new ReentrantLock();
private final ReadWriteLock rwlock = new ReentrantReadWriteLock();
private final Lock readLock = rwlock.readLock();
private final Lock writeLock = rwlock.writeLock();
public OjadbMap(int maxCapacity) {
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
@Override
public boolean containsKey(Object key) {
try {
readLock.lock();
return super.containsKey(key);
} finally {
readLock.unlock();
}
}
@Override
public V get(Object key) {
try {
readLock.lock();
return super.get(key);
} finally {
readLock.unlock();
}
}
@Override
public V put(K key, V value) {
try {
writeLock.lock();
return super.put(key, value);
} finally {
writeLock.unlock();
}
}
public int size() {
try {
readLock.lock();
return super.size();
} finally {
readLock.unlock();
}
}
public void clear() {
try {
writeLock.lock();
super.clear();
} finally {
writeLock.unlock();
}
}
public Collection<Map.Entry<K, V>> getAll() {
try {
readLock.lock();
return new ArrayList<Map.Entry<K, V>>(super.entrySet());
} finally {
readLock.unlock();
}
}
}