CODEWITHSUNDEEP
c#data-structuresc#-3.0
VictorB
VictorB

Reputation: 23

How do I implement IEqualityComparer for HashSet correctly?

I am writing some code which maps LDAP property names to friendly names and back. There are just simple classes called DirectoryProperty:

public class DirectoryProperty
{
  public string Id { get; set; }
  public string Name { get; set; }
  public string HelpText {get; set; }

  public DirectoryProperty(string id, string name)
  {
    Id = id;
    Name = name;
  }
}

I then have code using a HashSet to build up a collection of these objects. I've got a fiexed set of properties that I supply but I want to allow others to add their own items. A set seems like a good structure for this because when you query LDAP you don't want to have repeating properties, and this also applies to UI where users select from a list of properties.

public class PropertyMapper
{
  readonly HashSet<DirectoryProperty> props = new HashSet<DirectoryProperty>(new DirectoryPropertyComparer());

 public PropertyMapper() // Will eventually pass data in here
 {
   props.Add(new DirectoryProperty("displayName", "Display Name"));
   props.Add(new DirectoryProperty("displayName", "Display Name")); //err
   props.Add(new DirectoryProperty("xyz", "Profile Path")); //err
   props.Add(new DirectoryProperty("samAccountName", "User Account Name"));
   props.Add(new DirectoryProperty("mobile", "Mobile Number"));
   props.Add(new DirectoryProperty("profilePath", "Profile Path"));
 }

 public List<string> GetProperties()
 {
   return props.Select(directoryProperty => directoryProperty.Id).OrderBy(p => p).ToList();
 }

 public List<string> GetFriendlyNames()
 {
   return props.Select(directoryProperty => directoryProperty.Name).OrderBy(p => p).ToList();
 }
}

As you can see I've got 2 problem data items in the constructor right now. The first of these is an obvious duplicate, and the other is a duplicate based on the Name property of DirectoryProperty.

My initial implementation of IEqualityComparer looks like:

class DirectoryPropertyComparer : IEqualityComparer<DirectoryProperty>
{
  public bool Equals(DirectoryProperty x, DirectoryProperty y)
  {
    if (x.Id.ToLower() == y.Id.ToLower() || x.Name.ToLower() == y.Name.ToLower())
    {
      return true;
    }

    return false;
  }

  public int GetHashCode(DirectoryProperty obj)
  {
    return (obj.Id.Length ^ obj.Name.Length).GetHashCode();
  }
}

Is there anything I can do to ensure that the Id, and Name properties of DirectoryProperty are both checked for uniqueness to ensure that duplicates based on either are caught? I'm probably being too strict here and I live with my existing code because it seems like it handles duplicate Id's OK but I'm interested in learning more about this.

Upvotes: 2

Views: 2963

Answers (2)

Jeffrey L Whitledge
Jeffrey L Whitledge

Reputation: 59473

This approach is not going to work. The Equals method needs to define an equivalence relationship, and such a relationship cannot be defined in this manner.

An equivalence relationship must be transitive, but this relation is not transitive.

{"A", "B"} == {"C", "B"}
and
{"A", "B"} == {"A", "D"}
but
{"C", "B"} != {"A", "D"}

A better approach would be to create two dictionaries—one for ID and one for Name—and check both dictionaries for collisions before adding a new value.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500893

It´s unclear exactly what you´re trying to do:

  • Your equality method considers two values equal if either their names or their IDs are the same
  • Your GetHashCode method includes both values, so (accidental collisions aside) you´re only matching if both the name and the ID have the same lengths in two objects

Fundamentaly, the first approach is flawed. Consider three entries:

A = { Name=¨N1¨, ID=¨ID1¨ }
B = { Name=¨N2¨, ID=¨ID1¨ }
C = { Name=¨N2¨, ID=¨ID2¨ }

You appear to want:

A.Equals(B) - true
B.Equals(C) - true
A.Equals(C) - false

That violates the rules of Equality (transitivity).

I strongly suggest you simply have two sets - one comparing values by ID, the other comparing values by Name. Then write a method to only add an entry to both sets if it doesn´t occur in either of them.

Upvotes: 3

Related Questions