Michael Bolin's 6.170 Recitation

This web site is for members of the recitation that I am teaching for 6.170 Spring 2004. The recitation meets Thursday mornings from 10-11am in 26-210. Here you will find recitation notes as well as links to software development tools that I consider important.
Recitation Notes
2/5 Recitation 1
2/12 Recitation 2
2/19 Recitation 3
2/26 Recitation 4
3/4 Recitation 5
Comments on Problem Sets
Problem Set 0
Problem Set 1
Problem Set 3
Things I Recommend
Software You Should Install
Books You Should Own
Web Sites You Should Use

2/26 Recitation 4

  1. The equals() Contract
  2. Equivalence
  3. How Hashtable Works
  4. Module Dependency Diagrams (MDDs)
  5. Object Model Diagrams

1. The equals() Contract

The equals() method has the following specified requirements for non-null references:
  • Never equal to null: x.equals(null) is always false.
  • Reflexive: x.equals(x) is always true.
  • Symmetric: If x.equals(y), then it must be that y.equals(x)
  • Transitive: If x.equals(y) and y.equals(z), then it must be that x.equals(z)
  • Consistent: Multiple invocations of x.equals(y) return the same value unless one of the objects is mutated.
Make sure that any equals() method that you write meets this contract.

Make sure that if you override equals(), then you override hashCode() so that for any two objects for which equals() is true that their hashCode() method returns the same int.

Failure to do these two things will lead to insidious bugs.

2. Equivalence

In 6.170, we talk about two types of equivalence:
  • behavioral equivalence is when two objects cannot be distinguished by any sequence of operations, including mutators and observers
  • observational equivalence is when two objects cannot be distinguished by any sequence of observer operations

In Java, == tests references for behavioral equivalence because if two references refer to the same object, then any operation performed using one reference must have the same effect as performing the operation on the other reference because they're being applied to the same object!

This may lead you to believe that only references for which == returns true are behaviorially equivalent; however, this is not true. Consider the following:

String a = new String("foo");
String b = new String("foo");
System.out.println(a == b); // prints false
In the example above, a and b are not referentially equivalent; however, they are behaviorally equivalent. The general reason why this is true is because String is an immutable type. An immutable type doesn't have any mutators, so if two immutable objects are observationally equivalent, then they must also be behaviorally equivalent.

Let's also look at an example of how to show that two things are not behaviorally equivalent:

StringBuffer b1 = new StringBuffer(), b2 = new StringBuffer();
System.out.println(b1.length() == b2.length()); // prints true
b1.append("foo");
System.out.println(b1.length() == b2.length()); // prints false
Aha! We found a sequence of mutators (a sequence of one element: b1.append("foo")) that can distinguish between b1 and b2. Thus, b1 and b2 are not behaviorally equivalent.

3. How Hashtable Works

A hashtable is a data structure that tries to provide constant-time lookup for a collection of objects. It works by using a hash of an object called a key to determine in which bucket the key's associated value should go. In Java, any Object may be a key or a value in a Hashtable. In practice, HashMap is often used in place of Hashtable because HashMap is not synchronized so it is faster. (In 6.170, it is unlikely that you will have to take advantage of Hashtable's synchronization, so just use HashMap.)

As shown in the diagram below, Hashtable gets the hash of the key by calling its hashCode() method. The Hashtable then applies further bit-shifting methods to the hash in hopes that it will spread out the number of buckets into which the value will be placed. If Hashtable did not do this, and instead determined the bucket index by evenly dividing up the range of integers into equal values, then many keys in a system would likely hash to the same bucket. Consider, for example, Card from Problem Set 1. In that case, every hash was between 0 and 52, so if Hashtable did no further operations to a Card's hash, then every Card would probably be in the same bucket of the Hashtable.

java.util.Hashtable flow chart

So what happens when two objects end up in the same bucket? This is called a collision and is undesirable because all of the objects in the same bucket are stored in a List inside the bucket. Consider the case when every object in the Hashtable has the same hash – then every value will end up in the same bucket, and that bucket will function as a LinkedList! Thus, it will require linear time to find an object in the Hashtable instead of constant time. Thus, the goal of a good hashCode() method is to spread out the values to minimize the chance of a collision. See Item 8 in Effective Java for information on how to write a good hashCode() method.

4. Module Dependency Diagrams (MDDs)

Module dependency diagrams (MDDs) demonstrate how different modules of your code are related. In 6.170, an MDD is composed of the following symbols:

Symbol Name Role in Java Example
specification interface
module class
meets extends, implements
uses . (method invocation)
weak uses not . (has a reference to a type, but does not invoke its methods)
module groupings package

As an example, here is an MDD for ps1:

Notice that this MDD is acyclic: there are no circular dependecies. You should strive for this in your code because it enforces decoupling. Decoupling is the elimination of dependencies between modules. When you eliminate dependencies in your code, then you have to make fewer changes to other modules that depend on your module. Thus, well-designed software should not have any circular dependecies.

Note that the goal of an MDD is not to capture every tiny dependency in your code; rather, the goal of the MDD is to convey information. An exacting, cluttered diagram conveys less information than a clear, imperfect one does. For example, even though CardValue uses String, we do not include String in our diagram. It is okay to leave out common classes such as those found in java.lang and java.util from your diagrams to eliminate clutter. However, if something in one of those packages is implemented or extended by your code, then it should be included in your MDD. Above, we see that Comparable is included in the diagram even though it is part of java.lang.

5. Object Model Diagrams

For now, see the "Object Model Glossary" at the end of Lecture 10 for a summary of object model diagrams.


©2004 Michael Bolin