ObjectIDGenerator vs. HashSet<T>

Question

Can anyone tell me how is ObjectIDGenerator better (worse?) then using HashSet when traversing an hierarchy of objects (that might be recurvise/circular), and not wanting to traverse the same object twice?

Answer 1

The basic difference is in how each one does equality.

ObjectIdGenerator looks at referential identity. When checking to see if an object is present already it will simply do an == call on the two object instances. This will boil down to a reference comparison because the objects are statically type to be object at this point. This is fine unless your object explicitly uses .Equals() for equality. If two objects are equal via .Equals() but different references, ObjectIDGenerator will consider them different objects. Likely not what you want.

HashSet on the other hand allows you to customize the way in which you compare objects via the IEqualityComparer<T> parameter. If none is specified it will use EqualityComparer<T>.Default which will use value equality. This method will call into .Equals() and depend on it to determine if two objects are equal. In the case where you didn't define a .Equals() method for your types it will default back to reference equality which is almost certainly what you want.

In short, go with HashSet :)

Sample Code showing the difference:

class Person
{
    public readonly string Name;
    public Person(string name) { Name = name; }
    public override int GetHashCode()
    {
        return Name.GetHashCode();
    }
    public override bool Equals(object obj)
    {
        var other = obj as Person;
        if (other == null)
        {
            return false;
        }
        return StringComparer.Ordinal.Equals(Name, other.Name);
    }
}

public static void Example()
{
    var gen = new ObjectIDGenerator();
    bool isFirst;
    var person1 = new Person("John");
    var person2 = new Person("Bob");
    gen.GetId(person1, out isFirst);    // isFirst = true
    gen.GetId(person1, out isFirst);    // isFirst = true
    gen.GetId(person2, out isFirst);    // isFirst = false
    gen.GetId(new Person("John"), out isFirst); // isFirst = true even though they are .Equals()

    var set = new HashSet<Person>();
    set.Add(person1);
    var contains1 = set.Contains(person1);              // true
    var contains2 = set.Contains(new Person("John"));   // true
}