Immutable Key Pattern

Intent

Define an object that can be used as a key in a HashMap.

Motivation

Key objects must not change their state when they are used as keys in a HashMap. When an element is added to the HashMap, the element is placed into a bucket. The index of bucket is based on the hash code of the key. When looking up the key in the HashMap, the hash code of the key is used to search in only one bucket. This allows for reducing the number of key comparisons needed to find an element. Changing the fields of the key change the cache code without changing the bucket thus making it impossible to find the key in the HashMap. This situation is known as a key leak.

You can avoid this problem by making the key object immutable. An immutable key is an object that state cannot be changed after the object was created.

Applicability

Use the Immutable Key pattern when

  • accessing objects in a HashMap

Structure

An Immutable Key is an object that consists only of a constructor and getter methods.

Participants 

  • Immutable Key
    - uniquely identifies an object in a HashMap
  • HashMap
    - a map that uses Immutable Key's hash code to place it in a bucket

Collaborations

  • An application creates an Immutable Key and puts an element identified by the key in a HashMap. The HashMap uses Immutable Key's hash code to associate it with a bucket for fast access. The application uses the Immutable Key to retrieve the element identified by the key.

Consequences

The immutable key pattern has the following benefits and drawbacks:

  1. It eliminates the possibility of the key leak. The application can safely use HashMap.
  2. It promotes concurrency. An immutable objects can be access by multiple threads without synchronization.
  3. It increases the number of classes in the system. In addition to a mutable class that contains fields that identify it, a separate class implementing the Immutable Key is need.

Implementation

The following implementation issues are relevant to the Immuable Key pattern:

  1. Java supports declaring immutable field on the language level by proving the final modifier. A field declared as final can be assigned only once. A Java implementation of the Immutable Key pattern assigns final key object's fields in a constructor. 

Examples



/**
 * Immutable line key identifies a line item. The key contains only a constructor and read-only
 * getter methods thus making it impossible to change the state of the object after it was created.
 */
public final class LineItemKey {

   private final int invoiceID;
   private final int lineItemID;


   /**
    * Constructs LineItemKey.
    */
   public LineItemKey(final int invoiceID, final int lineItemID) {
      this.invoiceID = invoiceID;
      this.lineItemID = lineItemID;
   }


   /**
    * Simply returns the invoice ID.
    *
    * @return the invoice ID.
    */
   public int getInvoiceID() {
      return invoiceID;
   }


   /**
    * Simply returns the line item ID.
    *
    * @return the line item ID.
    */
   public int getLineItemID() {
      return lineItemID;
   }


   /**
    * Calculates hash code by accessing immutable object's fields.
    *
    * @return calcualted hash code.
    */
   public int hashCode() {
      int result;
      result = invoiceID;
      result = 29 * result + lineItemID;
      return result;
   }


   public boolean equals(final Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      final LineItemKey that = (LineItemKey)o;
      if (invoiceID != that.invoiceID) return false;
      if (lineItemID != that.lineItemID) return false;
      return true;
   }
}

Labels

 
(None)