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);`
`}`

Enjoy,
Tom