最も簡単なLRUアルゴリズムが実現され、スレッドが安全です。

LRUアルゴリズムは用途の広さはもちろん、cacheを使うところでその姿を見ることができます。特にスレッドが多く、同時に高さがあり、データ量が大きい環境で。
jdk 1.5はいいですね。LinkdhashMap.javaのソースコードの中に直接このような文字があります。「This kind of map is well-sulled to building LRU caches....The removeEldest Entry（Map.Entry）method may be overridn to impose to impose thericdmademadematmatmaregs.theregmatmatmatmatmatre。」つまり自分でremoveEldest EntEntryを書いても大丈夫です。私は当時自分で一つ書きました。
以下はコードです。スレッドの安全コードを追加しました。

import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V>
{
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final Lock lock = new ReentrantLock();

    public LRULinkedHashMap(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 V get(Object key)
    {
        try {
            lock.lock();
            return super.get(key);
        }
        finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value)
    {
        try {
            lock.lock();
            return super.put(key, value);
        }
        finally {
            lock.unlock();
        }
    }
}

なお、getとputだけはスレッドが安全です。
本来は入門フォーラムに置いておきたいのですが、LRUアルゴリズムを使うなら、Reentrant Lockを知っている人も初心者ではないようです。