The Collections framework

List classes

A List is an ordered collection, which allows positional access and search.

The classes implementing List are ordered by index position. An ArrayList enables fast iteration and constant speed positional access. A Vector is similar to ArrayList, only slower because it is synchronized. LinkedList allows fast insertion and deletion at the beginning or end. It is commonly used for implementing stacks and queues. For instance:

ArrayList list = new ArrayList();
list.add("mango");
list.add("apple");
list.add("mango");
list.add("banana");
Iterator i = list.iterator();
while(i.hasNext())
  System.out.print(i.next());  // Prints "mango apple mango banana"

Map classes

The classes implementing the Map interface map unique keys to specific values.

The HashMap class is not sorted or ordered. It allows one null key and many null values.

Hashtable is similar to HashMap, but does not allow null keys and values. It's also slower than HashMap because it is synchronized. The J2SE 1.4 LinkedHashMap class iterates by insertion or last accessed order. It allows one null key and many null values.

TreeMap is a map in ascending key order, sorted according to the natural order for the key's class.

The equals() method of java.lang.Object

The equals() method, shown below, should implement an equivalence relation:

public boolean equals(Object obj)

In addition, the equals() method is:

• Reflexive: For any reference value x, x.equals(x) should return true.


• Symmetric: For any reference values x and y, x.equals(y) should return true only if y.equals(x) returns true.


• Transitive: For any reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.


• Consistent: For any reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equal comparisons on the object is modified.

For any non-null reference value x, x.equals(null) should return false.

The hashCode() method of java.lang.Object

The hashCode() method, shown below, of the java.lang.Object class returns the hash code value for the object. The hash code value of an object gives an integer that can be used by some collection classes like HashSet and Hashtable to map its objects into buckets in memory. The process of hashing enables efficient storage and retrieval of objects from the collection.

public int hashCode()

If two objects are equal as given by the equals() method, then their hash codes must be the same. So whenever equals() is overridden, hashCode() also should be implemented.

However, the reverse is not required. Two objects that are not equal can have the same hash code. This is because it is not always possible to ensure unique hash codes. However, it is better to have distinct hash codes for distinct objects to improve efficiency and performance.

The object comparison logic used by the equals() method usually involves instance variables of the two objects. The same instance variables should also be used by the hashCode() implementation. For instance:

public class Test
{
      int i;
      public boolean equals(Object o)
      {
          Test t = (Test)o;
          if (t.i == this.i)
          return true;
          return false;
      }
      public int hashCode()
      {
          return i * 31;
      }
}

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode() method must consistently return the same integer, provided no information used in equal comparison on the object is modified. It is inappropriate to involve a random number when computing the hash code, because it would not return the same hash code for multiple invocations of the method. The hash code of a null element is defined as zero.

When you implement the equals() and hashCode() methods, it is not appropriate to use transient variables.