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

• 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 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

• 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

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

3. How Hashtable Works

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.

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)

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