HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Calculating GetHashCode efficiently with unordered list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
efficientlyunorderedwithcalculatinggethashcodelist

Problem

I'm wondering what would be the best way to calculate the hashcode when the order of a sequence doesn't matter. Here's the custom IEqualityComparer i've implemented for an answer on Stackoverflow.

public class AccDocumentItemComparer : IEqualityComparer
{
    public bool Equals(AccDocumentItem x, AccDocumentItem y)
    {
        if (x == null || y == null)
            return false;
        if (object.ReferenceEquals(x, y))
            return true;
        if (x.AccountId != y.AccountId)
            return false;
        return x.DocumentItemDetails.Select(d => d.DetailAccountId).OrderBy(i => i)
            .SequenceEqual(y.DocumentItemDetails.Select(d => d.DetailAccountId).OrderBy(i => i));
    }

    public int GetHashCode(AccDocumentItem obj)
    {
        if (obj == null) return int.MinValue;
        int hash = obj.AccountId.GetHashCode();
        if (obj.DocumentItemDetails == null)
            return hash;
        int detailHash = 0;
        unchecked
        {
            var orderedDetailIds =  obj.DocumentItemDetails
                .Select(d => d.DetailAccountId).OrderBy(i => i);
            foreach (int detID in orderedDetailIds)
                detailHash = 17 * detailHash + detID;
        }
        return hash + detailHash;
    }  
}


As you can see the foreach in GetHashCode needs to order the (nested) sequence before it starts calculating the hashcode. If the sequence is large this seems to be inefficient. Is there a better way to calculate the hashcode if the order of a sequence can be ignored?

Here are the simple classes involved:

public class AccDocumentItem
{
    public string AccountId { get; set; }
    public List DocumentItemDetails { get; set; }
}

public class AccDocumentItemDetail
{
    public int LevelId { get; set; }
    public int DetailAccountId { get; set; }
}

Solution

If the order does not matter, use an kommutative operator to combine the hashCodes of the elements.

Possible candidates are:

^ binary xor // THIS WOULD BE MY CHOICE

+ addition // problem may be the overflow

* multiplication // problem may be the overflow

| binary or // not recommended, because after some of this operations it is likely that all bits are set, so the same hashCode would appear for quite different instances)

Context

StackExchange Code Review Q#32024, answer score: 5

Revisions (0)

No revisions yet.