Hash calculation for array of long values in C#

Question

Can the following function be improved in terms of performance?

I am calculating millions of such hashes. The long array represents a record from data table where all values are encoded as long values. Usually in one calculation stream all arrays are of the same length but in some rare cases this rule does not apply. Typical length of the array vary from 300 to 1 elements.

I was wondering whether using SIMD (SSE / AVX) instructions in System.Numerics.Vectors library of .NET 4.6 could help?

public static int GetHashCode(long[] array)
{
    if (array == null) return 0;
    unchecked
    {
        int hash = 17;
        for(int i = 0; i < array.Length; i++)
            hash = 31 * hash + array[i].GetHashCode();
        return hash;
    }
}

Do rows sometimes only differ is small parts? If not, you could simply leave out some of the inputs. — CodesInChaos
– CodesInChaos, Commented Aug 23, 2016 at 9:18
@CodesInChaos this is 64-bit process. Yes rows often differ only in small parts. — Sebastian Widz
– Sebastian Widz, Commented Aug 23, 2016 at 15:18
A common approach is to only hash the first x (like 6-20) rows. — paparazzo
– paparazzo, Commented Aug 23, 2016 at 17:46
More important is how is it going to be used? Hash is only Int 32. You are using multiple long just to find a bucket. Right now this imperfect hash is more expensive than a comparison (equals). Equal would check length and then element by element compare and stop once it finds an inequality. In real life I bet you would be better with length and the first 6 values. With different primes so order matters. Sorry but to use up to 300 long to create an Int 32 is silly. — paparazzo
– paparazzo, Commented Aug 23, 2016 at 18:20

JanDotNet · Accepted Answer · 2016-08-23 06:48:00Z

4

You could use XOR to combine hashes which is much faster than your calculation:

int hash = 0;
for(int i = 0; i < array.Length; i++)
    hash ^= array[i].GetHashCode();
return hash;

answered Aug 23, 2016 at 6:48

JanDotNet

8,6082 gold badges22 silver badges48 bronze badges

1

\$\begingroup\$ Doing nothing but XOR has issues with hash collisions, both because XOR is commutative (e.g., abc hashes to the same value as cba) and because it biases to zero values (a XOR b = 0 for any a = b, which happens frequently in real-world data). You could toss in a multiplication with a prime number before or after the XOR function to resolve that, though. \$\endgroup\$

Dan Lyons
– Dan Lyons

2016-08-23 17:49:00 +00:00
Commented Aug 23, 2016 at 17:49
\$\begingroup\$ @DanLyons Multiplication is also commutative. \$\endgroup\$

paparazzo
– paparazzo

2016-08-23 17:51:22 +00:00
Commented Aug 23, 2016 at 17:51
1

\$\begingroup\$ @Paparazzi: Whether multiplication is commutative is irrelevant; it is not commutative with xor. (A * B) ^ C and A * (B ^ C) can have completely different values; consider A, B, C all equal to 2, for example. \$\endgroup\$

Eric Lippert
– Eric Lippert

2016-08-23 17:59:55 +00:00
Commented Aug 23, 2016 at 17:59
\$\begingroup\$ @DanLyons: Can you briefly explain why prime numbers have a desirable property as a multiplicand? \$\endgroup\$

Eric Lippert
– Eric Lippert

2016-08-23 18:00:32 +00:00
Commented Aug 23, 2016 at 18:00
1

\$\begingroup\$ @Paparazzi: The proposal for mixing them is the comment you replied to. It is in the sentence "... toss in a multiplication ... before or after the XOR". \$\endgroup\$

Eric Lippert
– Eric Lippert

2016-08-23 18:08:22 +00:00
Commented Aug 23, 2016 at 18:08

| Show 7 more comments

JanDotNet · Accepted Answer · 2016-08-23 21:34:44Z

After discussion in comments of my other answer I did some investigation and found this interesting 5 years old article form Eric Lippert. It says

[...] In particular, be careful of “xor”. It is very common to combine hash codes together by xoring them, but that is not necessarily a good thing. Suppose you have a data structure that contains strings for shipping address and home address. Even if the hash algorithm on the individual strings is really good, if the two strings are frequently the same then xoring their hashes together is frequently going to produce zero. “xor” can create or exacerbate distribution problems when there is redundancy in data structures. [..]

Therefore XOR seems not to be the best solution for combining hash codes in general. Not sure if that is true in your case because the quality of the hash functions depends on the distribution of the data.

However, if XOR is still to slow, you could try to simplify the hash function. Of course, that will increases the number of collisions, but probably it performs better than a GetHashCode method that is much slower than Equals.

You could try something like that for example:

public static int GetHashCode(long[] array)
{
    if (array == null) return 0;
    if (array.Length == 0) return -1;
    unchecked
    {
        int hash = 17;
        hash = 31 * hash + array[0].GetHashCode();
        hash = 31 * hash + array[array.Length/2].GetHashCode();
        hash = 31 * hash + array[array.Length-1].GetHashCode();
        hash = 31 * hash + array.Length;
        return hash;
    }
}

Stack Exchange Network

Hash calculation for array of long values in C#

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Hash calculation for array of long values in C#

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions