ONJava.com -- The Independent Source for Enterprise Java
oreilly.comSafari Books Online.Conferences.


AddThis Social Bookmark Button

The Hashbelt Data Structure
Pages: 1, 2, 3, 4, 5

The Hashbelt Framework

Now that we've discussed the basic hashbelt algorithm, it's time to discuss the library that implements hashbelts. The hashbelt framework is contained in the packages grosso.expiration and grosso.collections (and their subpackages). The code involved in implementing hashbelts, while flexible, isn't that complicated. Without the examples, it consists of three interfaces, 13 classes, and just under 900 lines of code. More importantly, the core of the implementation consists of just three classes and two interfaces. In order, these are:

  • AbstractHashbeltExpirationSystem. This is an abstract base class. It implements the ExpirationSystem interface and handles most of the basic bookkeeping for implementations of the hashbelt algorithm.

  • StandardHashbeltExpirationSystem. This is one of two concrete subclasses of AbstractHashbeltExpirationSystem. Instances of this class automatically expire objects at the appointed time, regardless of whether or not the object has been used in the interim.

  • UpdatingHashbeltExpirationSystem. This is one of two concrete subclasses of AbstractHashbeltExpirationSystem. Instances of this class automatically extend the lifetime of objects that have been recently accessed.

  • HashbeltContainer. This is an interface that defines the basic functionality required of each container in the hashbelt. There are three implementations: FastIteratingHashbeltContainer, StandardHashbeltContainer, and HashlistBasedHashbeltContainer.

  • ExpirationHandler. This is an interface that defines a single method, handleExpiredContainer. When an instance of AbstractHashbeltExpirationSystem is created, it is given an instance of ExpirationHandler to use at the appropriate time.

In order to use hashbelts in your program, you will need to do the following:

  1. Choose a subclass of AbstractHashbeltExpirationSystem (either StandardHashbeltExpirationSystem or UpdatingHashbeltExpirationSystem).
  2. Choose a type of container to use. All of the implementations of HashbeltContainer have the same semantics; choosing the appropriate container is simply an optimization and will depend on how you expect the system to be used.
  3. Write an expiration handler. Since an expiration system can store any type of object, and is a library being provided without any knowledge of your code, it makes sense that you have to provide the actual code that performs the expiration.

This is all summarized in the following UML diagram:

Diagram -- click for full-size view.
Figure 4. The hashbelt object hierarchy (Click for full-size view).

We'll now proceed to talk about the various parts of the framework in more detail.

The ExpirationSystem Interface

The first part of the code we're going to discuss is the ExpirationSystem interface. This interface plays a very simple role in the code: it isolates the clients from the implementation of the code that expires data. A program that uses a hashbelt-based expiration system naturally divides into three parts:

  • Initialization code. This code, which is usually static and often very simple, creates the expiration system and puts everything in motion. As such, this code encapsulates domain-specific algorithmic decisions (which type of container to use, which type of hashbelt to use, and how to expire objects) and must be written by the application programmer.
  • The implementation of the expiration system. This is the code in the framework.
  • Code that accesses the expiration system. This is usually the majority of the application-specific code. While the initialization code only occurs once, is a fixed cost, and is located in only a few objects, the code that accesses the expiration system is often spread throughout the program and is written while the programmer is thinking of something else.

This last bullet is the reason for using a simple interface to the expiration system. Doing so simplifies the majority of the code application programmers must write. The interface is basically a simplified version of java.util.Map (with a halt method thrown in). This reflects the goal of the interface -- from the point of view of the application code, an expiration system should look like a container class, and none of the methods called on an expiration system should result in an object being expired. Here's the code for the ExpirationSystem interface:

	package grosso.expiration;

	import java.util.*;

	public interface ExpirationSystem<K,V>{
		public void put(K key, V expirableObject);
		public void remove(K key);
		public void clear();	
		public V get(K key);
		public void halt();

Note: We could have added methods like expire or expireAll (to force the expiration of a single object or all of the objects in the system, respectively), but there are two reasons for not doing so. The first is that it's rarely necessary; with the possible exception of server shutdowns, you should never want to expire all of the objects in an expiration system. And the second reason is that doing so seems contrary to the spirit of the library -- the application programmer (and her code) should treat the expiration system like just another container data structure. If you find that you need an expire or expireAll method, I'd love to hear about it. More generally, I'm planning on maintaining this code (and keeping it up to date) for the foreseeable future; suggestions for changes or enhancements are welcome.

Writing most of the application to this interface also makes it easier to replace hashbelts with a different data structure, should it be necessary for specific applications.

I've also defined an abstract base class, AbstractExpirationSystem, and an associated helper class, ExpirationSystemExpirationThread. Neither AbstractExpirationSystem nor ExpirationSystemExpirationThread do much; ExpirationSystemExpirationThread extends Thread in order to define a background thread that occasionally wakes up to expire objects and AbstractExpirationSystem is a base class for expiration systems that starts the expiration thread going. Basically, these classes formalize code we've seen more than once in the first article, and place it in an abstract base class.

Here's the code for AbstractExpirationSystem and ExpirationSystemExpirationThread:

  package grosso.expiration;
  import java.util.*;

  public abstract class AbstractExpirationSystem <K,V>implements ExpirationSystem<K,V> {

    protected abstract void expireObjects();
    private ExpirationSystemExpirationThread _expirationThread;

    public AbstractExpirationSystem() {
      _expirationThread = new ExpirationSystemExpirationThread(this);

    public AbstractExpirationSystem(long timeToSleep) {
      _expirationThread = new ExpirationSystemExpirationThread(timeToSleep, this);

    public synchronized void halt() {

  package grosso.expiration;
  import java.util.*;

  public class ExpirationSystemExpirationThread extends Thread {
    public static final long FIFTEEN_SECONDS = 15 * 1000;
    public static final long REAPER_THREAD_SLEEP_TIME = FIFTEEN_SECONDS;
    private boolean _shouldKeepRunning = true;
    private long _timeToSleep;
    private AbstractExpirationSystem _owner;
    public ExpirationSystemExpirationThread(AbstractExpirationSystem owner) {
      this(REAPER_THREAD_SLEEP_TIME, owner);

    public ExpirationSystemExpirationThread(long timeToSleep, AbstractExpirationSystem owner) {
      _owner = owner;
      _timeToSleep = timeToSleep;

    public synchronized void halt() {
      _shouldKeepRunning = false;

    public void run() {
      while(shouldKeepRunning()) {
        try {
        catch (InterruptedException ignored){}

    private synchronized boolean shouldKeepRunning() {
      return _shouldKeepRunning;

There is one point to note here -- AbstractExpirationSystem defines a new abstract method called expireObjects. This is a protected abstract method that is called by the background thread. It is a convenient method; subclasses of AbstractExpirationSystem implement it in order to expire objects when enough time has elapsed. Application programmers don't need to implement or call expireObject and it is therefore not in the ExpirationSystem interface.

Pages: 1, 2, 3, 4, 5

Next Pagearrow