Comparing immutable data types

Question

Is there a commonly accepted way of how to compare immutable objects that might contain long lists of values?

So far, my interfaces are as follows:

interface Formula : IEquatable<Formula> {
   IList<Symbol> Symbols {get;}
}

interface Symbol : IEquatable<Symbol> {
   String Value {get;}
}

Here, the immutable datatype Formula represents a sequence of Symbol's. So in a formula:

x -> y

symbols would be x,->,y.

I want to compare two Formulas based on their content (e.g. a list of symbols). So new Formula(symbols) would equal new Formula(symbols) for some arbitrary list of symbols.

However, I don't want to iteratively compare two lists all the time.

I was thinking, in implementation, of creating some kind of calculated value during the initialization of the Formula - and using that for comparison. However, that will require me to add a method of some sort to my interface. What would I call that method?

I am not sure if it is appropriate to use hash code for this, as it seems to be limited to integers.

Any help appreciated - and if something is not clear I will revise my question. Thank you!

Answer 1

You could definitely use a hash code for this. Don't forget that a hash code doesn't have to be unique - it just helps if it doesn't give collisions (two unequal sequences with the same hash code) terribly often. (At least, try to come up with an approach which avoids equal hash codes for obvious situations.)

So you could compute the hash code once on construction (by combining the hash codes of each symbol in turn), then return that from GetHashCode without recomputing it each time. That would mean that you'd only ever need to compare sequences with equal hash codes - which would rarely happen for non-equal sequences.