As we consider the necessity of preserving heap order as we implement heaps, or symmetric order when implementing binary search trees, one thing we don't want to happen is for something we need to comparisons with to suddenly change (i.e., "mutate") without our knowledge.

For example, in our binary search tree class, we don't want a client who might have a reference to a key used in our tree to suddenly change that key -- that could break the internal symmetric order for our tree and impair its ability to retreive values or insert new key-value pairs. Similarly, we don't want a client with a reference to an item used in our heap to suddenly change that either -- heap order might then be broken and our heap would no longer function properly.

A protection against this is to insist the keys used are objects of an immutable class.

To explain what this means, recall that we often use objects to store, access, or alter the data contained in the object's instance variables. Methods that access (but don't modify) such data are called accessor methods, while those that alter the data are called mutator methods.

As an example, a "getter" method that returns the value of some instance variable is a simple type of accessor method, while the related "setter" method for that instance variable is a simple type of mutator method.

If the contents of an object can't be changed once the object is created, the object's class is said to be immutable.

There are multiple advantages to making classes immutable. In addition to being useful as keys in priority queues and symbol tables, as mentioned above, immutable objects also:

Joshua Bloch
As the person who led the design and implementation of the Java Collections Framework (among other things), has said:
"Classes should be immutable unless there's a very good reason to make them mutable. ... If a class cannot be made immutable, you should still limit its mutability as much as possible." - Joshua Bloch

To create an immutable class in Java, you should do all of the following:

  1. Declare the class as final, so it can't be extended.
  2. Mark all instance variables as private, so that direct access is not allowed.
  3. Don't provide any mutator methods.
  4. Mark all mutable instance variables as final, so that their values may only be assigned once.
  5. Initialize all instance variables via a constructor using defensive (and deep) copies.
  6. Provide no accessor methods that return or could be used to obtain a reference to a mutable part of the object in question. (If needed, return a deep copy instead.)

Hopefully the reasons for the first four steps above are clear.

To see the importance of step (5), consider the following:

public final class Name {
    private final StringBuilder sb;
    public Name(StringBuilder sb) { = sb;   // PROBLEM! We didn't make a copy of sb here
    public String toString() {
        return sb.toString();
public class Main { 
    public static void main(String[] args) {
       StringBuilder bob = new StringBuilder("Bob");
       Name name = new Name(bob);  
       System.out.println(name);   // this prints "Bob"

       bob.append(", I am not!");  // here we change bob, which changes name 
                                   //(despite all of our other precautions).

       System.out.println(name);   // this prints "Bob, I am not!"
                                   // (the Name class is not yet immutable)

In considering why we need step (6) above, note that access to a reference to a mutable part of an object provides a way to change the object as the following classes demonstrate:

public class BirthDate {
    private int year;
    private int month;
    private int day;

    public BirthDate( int year, int month, int day) {
        this.year = year;
        this.month = month; = day;

    public void setYear(int newYear) {  // With the presence of this setter, 
        year = newYear;                 // BirthDate is clearly a mutable class
    public String toString() {
        return month+"/"+day+"/"+year;
public class Student {
   private int id;
   private BirthDate birthDate;

   public Student(int ssn, int year, int month, int day) {
       id = ssn;
       birthDate = new BirthDate(year, month, day);

   public int getId()  {
       return id;

   public BirthDate getBirthDate() {
       return birthDate;   //This is a not a mutator method, but is
                           //an accessor method that returns a reference
                           //to a mutable object
   public String toString() {
       return id+" : " + birthDate;
public class Test {
    public static void main(String[] args) {
       Student student = new Student(123456, 1970, 5, 3);
       System.out.println(student);  // prints "123456 : 5/3/1970

       BirthDate date = student.getBirthDate();
       date.setYear(2010);   //Now the student birth year is changed!
       System.out.println(student);  // prints "123456 : 5/3/2010" 
                                     // (the Student class is not yet immutable)

As an example of class that has been effectively made immutable, consider the Vector class below:

public final class Vector {         // final class, so can't override instance methods
   private final int n;             // private, so not accessible outside of class; 
   private final double[] data;     // final, so they can only be assigned once; 

   public Vector(double[] data) {
      this.n = data.length; = new double[n];    // here we make a defensive copy of the mutable 
      for (int i=0; i < n; i++)     // reference variable, data[i] = data[i];

   ... // they aren't shown here, but assume no instance 
       // methods that change the instance variables