Saturday, February 1, 2014

How to Combine Hash Codes: GetHashCodeAggregate

How do you efficiently combine hash codes?

When combining hash codes I started by generating a large string and then hashing that. However that was inefficient, so instead I was referred to this simple arithmetic solution on StackOverflow provided by Jon Skeet himself!

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

How much more efficient is this than string concatenation?

TLDR: Very! Below is a chart of the average number of ticks it takes to calculate a hash by both generating a string and Jon's method of adding ints. Each test is an average of 100,000 iterations.

Number of Keys Avg Ticks for String Avg Ticks for Int Performance Increase
2 0.90 0.15 500%
5 2.08 0.25 732%
10 3.77 0.37 918%
20 7.30 0.64 1040%
50 18.97 1.33 1326%

GetHashCodeAggregate Extension Methods

Here are some simple extension methods to help you use this new technique.

public static class EnumerableExtensions
{
    public static int GetHashCodeAggregate<T>(
        this IEnumerable<T> source)
    {
        return source.GetHashCodeAggregate(17);
    }
 
    public static int GetHashCodeAggregate<T>(
        this IEnumerable<T> source,
        int hash)
    {
        unchecked
        {
            foreach (var item in source)
                hash = hash * 31 + item.GetHashCode();
        }
 
        return hash;
    }
}

XUnit Tests

As always, here are some unit tests to show you how these extension methods work.

[Theory]
[InlineData(1, new object[] { 1, 2 })]
[InlineData(1, new object[] { 1, 2, 3 })]
[InlineData(1, new object[] { 'a', 'b' })]
[InlineData(1, new object[] { 'a', 'b', 'c' })]
[InlineData(1, new object[] { "Aa", "Bb" })]
[InlineData(1, new object[] { "Aa", "Bb", "Cc" })]
[InlineData(1, new object[] { 1, 'b' })]
[InlineData(1, new object[] { 1, 'b', "Cc" })]
public void GetHashCodeAggregate(int skip, object[] source)
{
    var hash1 = source.GetHashCodeAggregate();
    var hash2 = source.GetHashCodeAggregate();
    Assert.Equal(hash1, hash2);
 
    var reversed1 = source.Reverse().GetHashCodeAggregate();
    var reversed2 = source.Reverse().GetHashCodeAggregate();
    Assert.Equal(reversed1, reversed2);
    Assert.NotEqual(hash1, reversed2);
 
    var skipped1 = source.Skip(skip).GetHashCodeAggregate();
    var skipped2 = source.Skip(skip).GetHashCodeAggregate();
    Assert.Equal(skipped1, skipped2);
    Assert.NotEqual(hash1, skipped2);
    Assert.NotEqual(reversed1, skipped2);
}
 
[Fact]
public void GetHashCodeAggregateArgs()
{
    // No Args
    var a = new[] { 1, 2, 3 }.GetHashCodeAggregate();
 
    // Seed Arg
    var b = new[] { 1, 2 }.GetHashCodeAggregate();
    var c = new[] { 3 }.GetHashCodeAggregate(b);
 
    Assert.Equal(a, c);
}
Shout it

Enjoy,
Tom

No comments:

Post a Comment

Post a Comment

Real Time Web Analytics