davidflanagan.com: Failure to override

Failure to override

22 months ago, I wrote this article for ONJava.com (part of the O'Reilly Network.

I'd pretty much forgotten about the article, until I got an e-mail today from a New Zealand reader known simply as "Hemi". He was the first of (presumably) several thousand readers to point out an error in this code from the article:

public class LRUCache extends java.util.LinkedHashMap {
    public LRUCache(int maxsize) {
	super(maxsize*4/3 + 1, 0.75f, true);
	this.maxsize = maxsize;
    }
    protected int maxsize;
    protected boolean removeEldestEntry() { 
       return size() > maxsize; 
    }
}

This code is supposed to implement a least-recently-used (LRU) cache on top of the java.util.LinkedHashMap class. Can you spot the error? Hint: the class functions as a cache, but fails the LRU part.

Read on to see what I did wrong and learn how you can avoid this category of errors yourself.

My class attempts, but fails, to override the removeEldestEntry() method of LinkedHashMap. The problem is that I got the signature wrong. The method I wanted to override takes a Map.Entry object as an argument. My method takes no arguments, and therefore does not actually override anything. The point of overriding this method is to prune old entries from the cache. (See the javadoc for LinkedHashMap for details.)

My code looks like it overrides the method, but it doesn't. The upshot is that the cache never purges the least-recently used elements, and just grows and grows.

I should have tested my code.

Now, getting on to the main point of this post: Java 1.5 has a solution to this general problem of failing to override the method you intend to override. The new Java metadata/annotation language feature defined by JSR-175 specifes an @Overrides annotation that solves exactly this problem.

Update: In the proposed final draft for JSR-175, this annotation has been renamed @Override.

If I had been writing the article about Java 1.5, and had annotated my method with @Overrides, then the compiler would have issued an error when it noticed that my method did not, in fact, override anything.

Here's the code as I should have written it, updated for Java 1.5, and still untested:

public class LRUCache extends java.util.LinkedHashMap {
    public LRUCache(int maxsize) {
	super(maxsize*4/3 + 1, 0.75f, true);
	this.maxsize = maxsize;
    }
    protected int maxsize;
    @Overrides protected boolean removeEldestEntry(Map.Entry eldest) { 
        return size() > maxsize; 
    }
}