Optimal way to ensure uniqueness of values in datastructure?

Question

I am required to key a dictionary based on values of a datastructure. I'm wondering what would be the optimal way to create this key?

The datastructure has 3 values: two strings and a datetime. The three of these values combined represents a "unique" key for my dictionary.

public class RouteIdentity
{
     public string RouteId {get;set;}
     public string RegionId {get;set;}
     public DateTime RouteDate {get;set;}
}

One solution that comes to mind is to add a property to RouteIdentity (called Key perhaps?) that returns some representation of the 3 unique values. The type of Key would be the type of the key value of the dictionary. Key could be a string value that simply concatenates the various properties, but this seems terribly inefficient. I suppose if there were a way to implement a fast hashing function to return a different type that might also work.

Another possibility to is override the Equals operator for RouteIdentity. I'm thinking this might be a better approach, but I'm unsure of how to override the GetHashCode() function for such a purpose.

Can anyone shed some light on what the optimal approach would be for this case? If you feel that it would be best to use operator overloading, could you please provide some guidance as to how to implement it properly?

Thanks in advance.

score 3 · Accepted Answer · answered Jul 30 '12 at 14:12

Implement Equals() and GetHashCode(), ..

public class RouteIdentity
{
    public string RouteId { get; set; }
    public string RegionId { get; set; }
    public DateTime RouteDate { get; set; }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }
        if (ReferenceEquals(this, obj))
        {
            return true;
        }
        if (obj.GetType() != typeof(RouteIdentity))
        {
            return false;
        }

        RouteIdentity other = (RouteIdentity) obj;

        return Equals(other.RouteId, RouteId) && 
               Equals(other.RegionId, RegionId) && 
               other.RouteDate.Equals(RouteDate);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (RouteId != null ? RouteId.GetHashCode() : 0);
            result = (result * 397) ^ (RegionId != null ? RegionId.GetHashCode() : 0);
            result = (result * 397) ^ RouteDate.GetHashCode();
            return result;
        }
    }
}

... and use new Dictionary<RouteIdentity, TValue>(), which internally will instantiate EqualityComparer<RouteIdentity>.Default, which uses these 2 methods to compare your RouteIdentity instances.

Thanks. Out of curiosity though, what's the significance of 397 in the GetHashCode() implementation? — pdriegen, Jul 30 '12 at 14:33
@pdriegen: This is a prime number to improve the distribution of the GetHashCode()-function (see http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus). — ulrichb, Jul 30 '12 at 14:47

score 1 · Answer 2 · answered Jul 30 '12 at 14:12

1

Implement IComparable for RouteIdentity and use HashSet<RouteIdentity>.

answered Jul 30 '12 at 14:12

Darek

4,687
31
47

Thanks Darek. Even though this wasn't what I was asking, I'll investigate this further to see if HashSet is a better datastructure to use than Dictionary for my case. – pdriegen Jul 30 '12 at 14:35
It might have better performance than Dictionary, since you are really storing a bunch of objects, instead of having a key/value pair. – Darek Jul 30 '12 at 15:08

Optimal way to ensure uniqueness of values in datastructure?

2 Answers2