patterncsharpMinor
Calculating GetHashCode efficiently with unordered list
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
As you can see the
Here are the simple classes involved:
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:
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.