Reading 12: Equality

In the previous readings we’ve developed a rigorous notion of data abstraction by creating types that are characterized by their operations, not by their representation. For an abstract data type, the abstraction function explains how to interpret a concrete representation value as a value of the abstract type, and we saw how the choice of abstraction function determines how to write the code implementing each of the ADT’s operations.

In this reading we turn to how we define the notion of equality of values in a data type: the abstraction function will give us a way to cleanly define the equality operation on an ADT.

In the physical world, every object is distinct – at some level, even two snowflakes are different, even if the distinction is just the position they occupy in space. (This isn’t strictly true of all subatomic particles, but true enough of large objects like snowflakes and baseballs and people.) So two physical objects are never truly “equal” to each other; they only have degrees of similarity.

In the world of human language, however, and in the world of mathematical concepts, you can have multiple names for the same thing. So it’s natural to ask when two expressions represent the same thing: 1+2, √9, and 3 are alternative expressions for the same ideal mathematical value.

Formally, we can regard equality in several ways.

Using an abstraction function . Recall that an abstraction function f: R → A maps concrete instances of a data type to their corresponding abstract values. To use f as a definition for equality, we would say that a equals b if and only if f(a)=f(b).

Using a relation . An equivalence is a relation E ⊆ T x T that is:

• reflexive: E(t,t) ∀ t ∈ T
• symmetric: E(t,u) ⇒ E(u,t)
• transitive: E(t,u) ∧ E(u,v) ⇒ E(t,v)

To use E as a definition for equality, we would say that a equals b if and only if E(a,b).

These two notions are equivalent. An equivalence relation induces an abstraction function (the relation partitions T, so f maps each element to its partition class). The relation induced by an abstraction function is an equivalence relation (check for yourself that the three properties hold).

A third way we can talk about the equality between abstract values is in terms of what an outsider (a client) can observe about them:

Using observation . We can say that two objects are equal when they cannot be distinguished by observation – every operation we can apply produces the same result for both objects. Consider the set expressions {1,2} and {2,1}. Using the observer operations available for sets, cardinality |…| and membership ∈, these expressions are indistinguishable:

• |{1,2}| = 2 and |{2,1}| = 2
• 1 ∈ {1,2} is true, and 1 ∈ {2,1} is true
• 2 ∈ {1,2} is true, and 2 ∈ {2,1} is true
• 3 ∈ {1,2} is false, and 3 ∈ {2,1} is false
• … and so on

In terms of abstract data types, “observation” means calling operations on the objects. So two objects are equal if and only if they cannot be distinguished by calling any operations of the abstract data type.

Example: Duration

public class Duration
{
    private int mins;
    private int secs;
    // rep invariant:
    //    mins >= 0, secs >= 0
    // abstraction function:
    //    represents a span of time of mins minutes and secs seconds

    // Make a duration lasting for m minutes and s seconds. 
    public Duration(int m, int s)
    {
        mins = m; secs = s;
    }

    // return length of this duration in seconds 
    public int GetLength()
    {
        return mins*60 + secs;
    }
}
       

Duration d1 = new Duration (1, 2);
Duration d2 = new Duration (1, 3);
Duration d3 = new Duration (0, 62);
Duration d4 = new Duration (1, 2);

Like many languages, Java and C# has two different operations for testing equality, with different semantics.

• The == operator compares references. More precisely, it tests referential equality. Two references are == if they point to the same storage in memory. In terms of the snapshot diagrams we’ve been drawing, two references are == if their arrows point to the same object bubble.
• The Equals() operation compares object contents – in other words, Object equality, in the sense that we’ve been talking about in this reading. The Equals operation has to be defined appropriately for every abstract data type.

For comparison, here are the equality operators in several languages:

Note that == unfortunately flips its meaning between Java/C# and Python. Don’t let that confuse you: == in Java/C# just tests reference identity, it doesn’t compare object contents.

As programmers in any of these languages, we can’t change the meaning of the referential equality operator. In Java, == always means referential equality. But when we define a new data type, it’s our responsibility to decide what object equality means for values of the data type, and implement the Equals() operation appropriately. C# additionally defines a method ReferenceEquals() for all objects which can be used to test for reference equality. This allows programmers to avoid any ambiguity if == is overridden.

The Equals() method is defined by Object , and its default implementation looks like this:

    // Returns a boolean indicating if the passed in Object obj is 
    // Equal to this.  Equality is defined as Object equality for reference
    // types and bitwise equality for value types using a loader trick to
    // replace Equals with EqualsValue for value types).
    // 
    
    public virtual bool Equals(Object obj)
    {
        return RuntimeHelpers.Equals(this, obj);
    }

In other words, the default meaning of Equals() is the same as referential equality. For immutable data types, this is almost always wrong. So you have to override the Equals() method, replacing it with your own implementation.

Here’s our first try for Duration :

public class Duration {
    ...   
    // Problematic definition of Equals()
    public bool Equals(Duration that) {
        return this.GetLength() == that.GetLength();        
    }
}

There’s a subtle problem here. Why doesn’t this work? Let’s try this code:

Duration d1 = new Duration (1, 2);
Duration d2 = new Duration (1, 2);
Object o2 = d2;
d1.Equals(d2) → true
d1.Equals(o2) → false

You can see this code in action for Java . You’ll see that even though d2 and o2 end up referring to the very same object in memory, you still get different results for them from Equals() .

What’s going on? It turns out that Duration has overloaded the Equals() method, because the method signature was not identical to Object ’s. We actually have two Equals() methods in Duration : an implicit Equals(Object) inherited from Object , and the new Equals(Duration) .

    // explicit method that we declared:
    public bool Equals(Duration duration)
    {
        return GetLength() == duration.GetLength();
    }

    // implicit method inherited from Object:
    public bool Equals(Object duration)
    {
        return this == duration;
    }

We’ve seen overloading since the very beginning of the course. Recall that the compiler selects between overloaded operations using the compile-time type of the parameters. For example, when you use the / operator, the compiler chooses either integer division or float division based on whether the arguments are ints or floats. The same compile-time selection happens here. If we pass an Object reference, as in d1.Equals(o2) , we end up calling the Equals(Object) implementation. If we pass a Duration reference, as in d1.Equals(d2) , we end up calling the Equals(Duration) version. This happens even though o2 and d2 both point to the same Object at runtime! Equality has become inconsistent.

It’s easy to make a mistake in the method signature, and overload a method when you meant to override it. This is such a common error that the C# compiler warns us when we override a method without explicitly using the override keyword. Duration2a.cs(30,17): warning CS0114: 'Duration.Equals(Object)' hides inherited member 'Object.Equals(Object)'. To make the current member override that implementation, add the override keyword. Otherwise add the new keyword.

So here’s the right way to implement Duration ’s Equals() method:

public override bool Equals(Object obj)
{
  // Check for null and compare run-time types dynamically
  if ((obj == null) || ! this.GetType().Equals(obj.GetType()))
  {
     return false;
  }
  else
  {
     Duration p = (Duration) obj; // cast from base class to child
     return GetLength() == p.GetLength();
  }
}

This fixes the problem:

Duration d1 = new Duration(1, 2);
Duration d2 = new Duration(1, 2);
Object o2 = d2;
d1.Equals(d2) → true
d1.Equals(o2) → true

You can see this code in action for Java in the Online Python Tutor.

GetType()

The specification of the Object class is so important that it is often referred to as the Object Contract . The contract can be found in the method specifications for the Object class. Here we will focus on the contract for Equals . When you override the Equals method, you must adhere to its general contract. It states that:

• Equals must define an equivalence relation – that is, a relation that is reflexive, symmetric, and transitive;
• Equals must be consistent: repeated calls to the method must yield the same result provided no information used in Equals comparisons on the object is modified;
• for a non-null reference x , x.Equals(null) should return false;
• GetHashCode must produce the same result for two objects that are deemed equal by the Equals method.

Breaking the Equivalence Relation

private static int CLOCK_SKEW = 5;
public override bool Equals(Object obj)
{
  //Check for null and compare run-time types dynamically
  if ((obj == null) || ! this.GetType().Equals(obj.GetType()))
  {
     return false;
  }
  else
  {
     Duration p = (Duration) obj; // cast from base class to child
     return Math.Abs(GetLength() - p.GetLength()) < CLOCK_SKEW;
  }
}

Breaking Hash Tables

public class Object {
  ...
  public boolean Equals(Object that) { return this == that; }
  public int GetHashCode() { return /* the memory address of this */; }
}

Duration d1 = new Duration(1, 2);
Duration d2 = new Duration(1, 2);
d1.Equals(d2) → true
d1.GetHashCode() → 2392
d2.GetHashCode() → 4823

public override int GetHashCode()
{
  return GetLength();
}

We’ve been focusing on equality of immutable objects so far in this reading. What about mutable objects?

Recall our definition: two objects are equal when they cannot be distinguished by observation. With mutable objects, there are two ways to interpret this:

• when they cannot be distinguished by observation that doesn’t change the state of the objects , i.e., by calling only observer, producer, and creator methods. This is often strictly called observational equality , since it tests whether the two objects “look” the same, in the current state of the program.
• when they cannot be distinguished by any observation, even state changes. This interpretation allows calling any methods on the two objects, including mutators. This is often called behavioral equality , since it tests whether the two objects will “behave” the same, in this and all future states.

For immutable objects, observational and behavioral equality are identical, because there aren’t any mutator methods.

For mutable objects, it’s tempting to implement strict observational equality. Java uses observational equality for most of its mutable data types, in fact. If two distinct List objects contain the same sequence of elements, then Equals() reports that they are equal.

But using observational equality leads to subtle bugs, and in fact allows us to easily break the rep invariants of other collection data structures. Recall our Date class from the reading on rep invariance. In the Tweet example, Date was a mutable class. Suppose we implement Equals() to use observational equality:

public override bool Equals(Object o)
{
   if (o == null || o.GetType() != GetType())
   {
      return false;
   }

   Date date = (Date) o;
   return (_day == date._day) && 
          (_month == date._month) && 
          (_year == date._year);
}

public override int GetHashCode()
{    
   return _day + _month + _year;
}

Date date = new Date(11,28,1019);
HashSet<Date> set = new HashSet<Date>();
set.Add(date);

We can check that the set contains the list we put in it, and it does:

set.Contains(date) → true

But now we mutate the date:

date.Month = 12;

And it no longer appears in the set!

set.Contains(date) → false!

It’s worse than that, in fact: when we iterate over the members of the set, we still find the list in there, but Contains() says it’s not there!

foreach (Date d in set)
{
   Console.WriteLine("Date: "+d);
}

If the set’s own iterator and its own Contains() method disagree about whether an element is in the set, then the set clearly is broken. You can see this code in action in Java (for a mutable list object). on Online Python Tutor. Note that if you try the example using List<string> in C#, it works as expected.

What’s going on? Date is a mutable object. In the implementation of Date , mutations affect the result of Equals() and GetHashCode() . When the date is first put into the HashSet , it is stored in the hash bucket corresponding to its GetHashCode() result at that time. When the date is subsequently mutated, its GetHashCode() changes, but HashSet doesn’t realize it should be moved to a different bucket. So it can never be found again.

When Equals() and GetHashCode() can be affected by mutation, we can break the rep invariant of a hash table that uses that object as a key.

Here’s a telling quote from the specification of java.util.Set :

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

The Java library is unfortunately inconsistent about its interpretation of Equals() for mutable classes. Collections use observational equality, but other mutable classes (like StringBuilder ) use behavioral equality.

The lesson we should draw from this example is that Equals() should implement behavioral equality . In general, that means that two references should be Equals() if and only if they are aliases for the same object. So mutable objects should just inherit Equals() and GetHashCode() from Object . For clients that need a notion of observational equality (whether two mutable objects “look” the same in the current state), it’s better to define a new method, e.g., similar() .

For immutable types :

• Equals() should compare abstract values. This is the same as saying Equals() should provide behavioral equality.
• GetHashCode() should map the abstract value to an integer.

So immutable types must override both Equals() and GetHashCode() .

For mutable types :

• Equals() should compare references, just like == . Again, this is the same as saying Equals() should provide behavioral equality.
• GetHashCode() should map the reference into an integer.

So mutable types should not override Equals() and GetHashCode() at all, and should simply use the default implementations provided by Object . Java doesn’t follow this rule for its collections, unfortunately, leading to the pitfalls that we saw above.

Summary