| | |
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:
Simplify debugging. The innards of immutable classes don't change. So when an unexpected change happens, that's one less place to have to look.
Provide safety in the presence of hostile code. The classic example of this is the String class. There are many reasons why this class is immutable, but prominent among these is that the java classloader uses this class in the course of loading classes. Imagine if one was trying to load the java.sql.Connection class, but the referenced value has been changed to myhacked.Connection which can then do unwanted things to one's database!
Simplify concurrent programming. One can write programs that juggle the execution of multiple threads of code -- but these need to be careful that one thread of code doesn't unintentionally alter what another thread of code may be attempting to do. As immutable objects can't be altered once they are created, they are "thread-safe".
"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:
final, so it can't be extended.
private, so that direct access is not allowed.final, so that their values may only be assigned once.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) {
this.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;
this.day = 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;
this.data = new double[n]; // here we make a defensive copy of the mutable
for (int i=0; i < n; i++) // reference variable, data
this.data[i] = data[i];
}
... // they aren't shown here, but assume no instance
// methods that change the instance variables
}