Introduction
Caching is an extremely useful concept to improve performance. There are many commercial and open-source caching packages available for Java. These packages usually involve installing jars, editing config files, and hooking into framework (JNDI, logging, JDBC), etc. This is fine, but sometimes we just want a quick and simple solution - the kind of solution that involves only a couple of classes which we can insert directly into our own code; the kind of code that you could copy and paste right off of a Web page. That is what we present here.
First, we define a caching interface so that later on, if we change our mind, we can use a different caching strategy or hook in to a more sophisticated caching package.
public interface Cache<K extends Comparable, V> {
V get(K obj);
void put(K key, V obj);
void put(K key, V obj, long validTime);
void remove(K key);
Pair[] getAll();
int size();
}
This caching interface gives us the ability to assign a expiration time for the cached objects. This can be very useful for cases where we know the data we are caching will change over time but it is not critical that people always see the absolute latest data and some delay is acceptable. For example, if we are retrieving content from a database to display in a Web page, it is often not necessary that users see the absolute latest data every time. If we are getting 100 queries per second without caching, even if we were to only cache for one second we would reduce the number of queries by 100. Often caching for 5 to 15 minutes is more than acceptable. We have implemented the least recently used (LRU) algorithm for caching, which discards the least recently used items first. This requires keeping track of what was used when.
We have only one public supporting object to allow us to retrieve all of the cached objects from the cache.
public class Pair<K extends Comparable, V> implements Comparable<Pair> {
public Pair(K key1, V value1) {
this.key = key1;
this.value = value1;
}
public K key;
public V value;
public boolean equals(Object obj) {
if(obj instanceof Pair) {
Pair p = (Pair)obj;
return key.equals(p.key)&&value.equals(p.value);
}
return false;
}
@SuppressWarnings("unchecked")
public int compareTo(Pair p) {
int v = key.compareTo(p.key);
if(v==0) {
if(p.value instanceof Comparable) {
return ((Comparable)value).compareTo(p.value);
}
}
return v;
}
@Override
public int hashCode() {
return key.hashCode()^value.hashCode();
}
@Override
public String toString() {
return key+": "+value;
}
}
Finally, the code for the implementation of the cache is:
public class LRUCache<K extends Comparable, V> implements Cache<K, V>,
Serializable {
private static final long serialVersionUID = 3674312987828041877L;
Map<K, Item> m_map = Collections.synchronizedMap(new HashMap<K, Item>());
Item m_start = new Item();
Item m_end = new Item();
int m_maxSize;
Object m_listLock = new Object();
static class Item {
public Item(Comparable k, Object v, long e) {
key = k;
value = v;
expires = e;
}
public Item() {}
public Comparable key;
public Object value;
public long expires;
public Item previous;
public Item next;
}
void removeItem(Item item) {
synchronized(m_listLock) {
item.previous.next = item.next;
item.next.previous = item.previous;
}
}
void insertHead(Item item) {
synchronized(m_listLock) {
item.previous = m_start;
item.next = m_start.next;
m_start.next.previous = item;
m_start.next = item;
}
}
void moveToHead(Item item) {
synchronized(m_listLock) {
item.previous.next = item.next;
item.next.previous = item.previous;
item.previous = m_start;
item.next = m_start.next;
m_start.next.previous = item;
m_start.next = item;
}
}
public LRUCache(int maxObjects) {
m_maxSize = maxObjects;
m_start.next = m_end;
m_end.previous = m_start;
}
@SuppressWarnings("unchecked")
public Pair[] getAll() {
Pair p[] = new Pair[m_maxSize];
int count = 0;
synchronized(m_listLock) {
Item cur = m_start.next;
while(cur!=m_end) {
p[count] = new Pair(cur.key, cur.value);
++count;
cur = cur.next;
}
}
Pair np[] = new Pair[count];
System.arraycopy(p, 0, np, 0, count);
return np;
}
@SuppressWarnings("unchecked")
public V get(K key) {
Item cur = m_map.get(key);
if(cur==null) {
return null;
}
if(System.currentTimeMillis()>cur.expires) {
m_map.remove(cur.key);
removeItem(cur);
return null;
}
if(cur!=m_start.next) {
moveToHead(cur);
}
return (V)cur.value;
}
public void put(K key, V obj) {
put(key, obj, -1);
}
public void put(K key, V value, long validTime) {
Item cur = m_map.get(key);
if(cur!=null) {
cur.value = value;
if(validTime>0) {
cur.expires = System.currentTimeMillis()+validTime;
}
else {
cur.expires = Long.MAX_VALUE;
}
moveToHead(cur);
return;
}
if(m_map.size()>=m_maxSize) {
cur = m_end.previous;
m_map.remove(cur.key);
removeItem(cur);
}
long expires=0;
if(validTime>0) {
expires = System.currentTimeMillis()+validTime;
}
else {
expires = Long.MAX_VALUE;
}
Item item = new Item(key, value, expires);
insertHead(item);
m_map.put(key, item);
}
public void remove(K key) {
Item cur = m_map.get(key);
if(cur==null) {
return;
}
m_map.remove(key);
removeItem(cur);
}
public int size() {
return m_map.size();
}
}
The cache works essentially like a map except that you can pass along an optional expiration time. Create, store, use -- simple.
History
- 30th October, 2005: Initial post
