Arrays/Lists and computing hashvalues (VB, C#)

Question

I feel bad asking this question but I am currently not able to program and test this as I'm writing this on my cell-phone and not on my dev machine :P (Easy rep points if someone answers! XD )

Anyway, I've had experience with using hashvalues from String objects. E.g., if I have StringA and StringB both equal to "foo", they'll both compute out the same hashvalue, because they're set to equal values.

Now what if I have a List, with T being a native data type. If I tried to compute the hashvalue of ListA and ListB, assuming that they'd both be the same size and contain the same information, wouldn't they have equal hashvalues as well?

Assuming as sample dataset of 'byte' with a length of 5 {5,2,0,1,3}

Answer 1

It depends on how you calculate the hash value and how you define equality. For example, two different instances of an array which happen to contain the same values may not be considered equal depending on your application. In this case you may include the address or some other unique value per array as part of the hash function.

However, if you want to consider to distinct arrays which contain the same values equal you would calculate the list hash using only the values in the array. Of course, then you have to consider if ordering matters to you or not in determining equality (and thus influencing your hash function).

Answer 2

If your talking about the built-in list types, then no, they will not be equal. Why? Because List<T> is a reference type, so equality will do a comparison to see if the references are the same. If you are creating a custom list type, then you could override the Equals and GetHashCode methods to support this behavior, but it isn't going to happen on the built in types.

Answer 3

If the order of items is important then you could generate a sequence hashcode like this.

public static int GetOrderedHashCode<T>(this IEnumerable<T> source)
{
    unchecked
    {
        int hash = 269;
        foreach (T item in source)
        {
            hash = (hash * 17) + item.GetHashCode;
        }
        return hash;
    }
}

If the order of items isn't important, then you could do something like this instead:

public static int GetUnorderedHashCode<T>(this IEnumerable<T> source)
{
    unchecked
    {
        int sum = 907;
        int count = 953;
        foreach (T item in source)
        {
            sum = sum + item.GetHashCode();
            count++
        }
        return 991 * sum * count;
    }
}

(Note that both of these methods will have poor performance for larger collections, in which case you might want to implement some sort of cache and only recalculate the hashcode when the collection changes.)