26

I have a class that internally is just an array of integers. Once constructed the array never changes. I'd like to pre-compute a good hashcode so that this class can be very efficiently used as a key in a Dictionary. The length of the array is less than about 30 items, and the integers are between -1000 and 1000 in general.

Improve this question
4
  • 1
    Dictionary key is unique and if your object store array of values, and key is computed based on them then there is no guarantee that you can get a unique hash key for the dictionary Commented Aug 4, 2010 at 10:59
  • 2
    @Fadrian: The OP does not want to compute a key but a HashValue. Look up what that means. Hashvalues are pseudo-unique. Commented Aug 4, 2010 at 11:57
  • Thanks Henk. I know how hash value are suppose to work and I may have misread the intend of the question when I posted the comment and its great that you pointed that out. Commented Aug 4, 2010 at 12:04
  • Fadrian, Henk was right. My intent was not to get a unique code but to get something pretty close to that that is quickly computable so that I dont need to do a full Equals very often. I realise that if you know the data you expect fairly well that it is possible to make a more appropriate choice which is what my question is seeking. A lot of the answers below are quite mathematical and I will need time to understand them. Commented Aug 4, 2010 at 13:01

10 Answers 10

Reset to default
32

Not very clever, but sufficient for most practical purposes:

EDIT: changed due to comment of Henk Holterman, thanks for that.

  int hc = array.Length;
  foreach (int val in array)
  {
      hc = unchecked(hc * 314159 + val);
  }

If you need something more sophisticated, look here.

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

Looks OK, but 314159 might be a bit large. A number like 17 or 31 would do nicely too. And: hc=unchecked(hc*SHIFTVAL+array[i]); to be independent of compiler settings.
Yes, one can improve that surely in many different ways, upvoted your comment.
@chhenning: so what?
@chhenning hash collisions may happen, no one claimed this would be "hash collision safe". This is where overriding Equals method take action. As far as I remember, the dicionary uses the Equals method to differ objects with the same hash (that's why the Equals method shouldn't realy on the hash itself).
@chhenning: or, if you prefer this: given two finite sets X and Y where X has a larger cardinality than Y, any function f:X->Y is necessarily non-injective. This is well know as the pidgeon-hole principle, I guess you have heard of it.
|
8

For an array of values generally between -1000 and 1000, I would probably use something like this:

static int GetHashCode(int[] values)
{
   int result = 0;
   int shift = 0;
   for (int i = 0; i < values.Length; i++)
   {
      shift = (shift + 11) % 21;
      result ^= (values[i]+1024) << shift;
   }
   return result;
}
Improve this answer

1 Comment

FYI, I chose the number 11 because 11 bits is what is necessary to store a range of 2048 distinct values (-1000 to +1000 is 2000, which is close). I chose the number 21 because 32-bit integer minus 11 bits equals 21 bits. Shifting left 21 bits will leave 11 bits to contain a value from 0 to 2048.
5

You can use Linq methods too:

var array = new int[10];
var hashCode = array.Aggregate(0, (a, v) => 
    HashCode.Combine(a, v.GetHashCode()));
Improve this answer

Comments

1

You may use CRC32 checksum. Here is the code:

[CLSCompliant(false)]
public class Crc32 {
    uint[] table = new uint[256];
    uint[] Table { get { return table; } }

    public Crc32() {
        MakeCrcTable();
    }
    void MakeCrcTable() {
        for (uint n = 0; n < 256; n++) {
            uint value = n;
            for (int i = 0; i < 8; i++) {
                if ((value & 1) != 0)
                    value = 0xedb88320 ^ (value >> 1);
                else
                    value = value >> 1;
            }
            Table[n] = value;
        }
    }
    public uint UpdateCrc(uint crc, byte[] buffer, int length) {
        uint result = crc;
        for (int n = 0; n < length; n++) {
            result = Table[(result ^ buffer[n]) & 0xff] ^ (result >> 8);
        }
        return result;
    }
    public uint Calculate(Stream stream) {
        long pos = stream.Position;
        const int size = 0x32000;
        byte[] buf = new byte[size];
        int bytes = 0;
        uint result = 0xffffffff;
        do {
            bytes = stream.Read(buf, 0, size);
            result = UpdateCrc(result, buf, bytes);
        }
        while (bytes == size);
        stream.Position = pos;
        return ~result;
    }
}
Improve this answer

3 Comments

That seems overly complex for an array of ~30 integers from -1000 to 1000. It requires converting the array of integers into an array of bytes or a stream first because there's no function that accepts an array of integers as an input, right?
It is easy to convert each int to byte[]: int value = 0; byte[] bytes = BitConverter.GetBytes(value); These bytes may be used to calculate checksum instead of bytes read from stream.
Yes, but you neglected the fact that you have to convert the whole array to bytes. That too is easy, but still ends up being some significant overhead in code complexity and at runtime relative to a solution specifically targeted at hashing an array of integers directly.
1

I'm using this here

var arrayHash = string.Join(string.Empty, array).GetHashCode();

If a element changed in the array, you will get a new hash.

Improve this answer

1 Comment

array should be ordered: array.Order()
0

You could take a different approach and use a recursive dictionary for each value in your int array. This way you can leave .net to do primitive type hashing.

internal class DictionaryEntry<TKey, TValue>
{
    public Dictionary<TKey, DictionaryEntry<TKey, TValue>> Children { get; private set; }
    public TValue Value { get; private set; }
    public bool HasValue { get; private set; }

    public void SetValue(TValue value)
    {
        Value = value;
        HasValue = true;
    }

    public DictionaryEntry()
    {
        Children = new Dictionary<TKey, DictionaryEntry<TKey, TValue>>();
    }
}

internal class KeyStackDictionary<TKey, TValue>
{
    // Helper dictionary to work with a stack of keys
    // Usage:
    // var dict = new KeyStackDictionary<int, string>();
    // int[] keyStack = new int[] {23, 43, 54};
    // dict.SetValue(keyStack, "foo");
    // string value;
    // if (dict.GetValue(keyStack, out value))
    // {   
    // }

    private DictionaryEntry<TKey, TValue> _dict;

    public KeyStackDictionary()
    {
        _dict = new DictionaryEntry<TKey, TValue>();
    }

    public void SetValue(TKey[] keyStack, TValue value)
    {
        DictionaryEntry<TKey, TValue> dict = _dict;

        for (int i = 0; i < keyStack.Length; i++)
        {
            TKey key = keyStack[i];
            if (dict.Children.ContainsKey(key))
            {
                dict = dict.Children[key];
            }
            else
            {
                var child = new DictionaryEntry<TKey, TValue>();
                dict.Children.Add(key, child);
                dict = child;
            }

            if (i == keyStack.Length - 1)
            {
                dict.SetValue(value);
            }
        }
    }

    // returns false if the value is not found using the key stack
    public bool GetValue(TKey[] keyStack, out TValue value)
    {
        DictionaryEntry<TKey, TValue> dict = _dict;

        for (int i = 0; i < keyStack.Length; i++)
        {
            TKey key = keyStack[i];

            if (dict.Children.ContainsKey(key))
            {
                dict = dict.Children[key];
            }
            else
            {
                break;
            }

            if (i == keyStack.Length - 1 && dict.HasValue)
            {
                value = dict.Value;
                return true;
            }
        }

        value = default(TValue);
        return false;
    }
}
Improve this answer

Comments

-1

I think choosing a good hash-algorithm would have to be based on the distribution (in a probability sense) of the integer values.

Have a look at Wikipedia for a list of algorithms

Improve this answer

Comments

-1

Any CRC (or even XOR) should be ok.

Improve this answer

3 Comments

The XOR would never shift outside the -/+ 1000 window
@Henk Holterman: Sorry, I dont get it. You will still have 10 bits of valid CRC if the values are limited. Edit: Actually the rest of the bits would flip depending on sign.
CRC is OK but overkill, simply XOR-ing the values (without shifting) is not OK.
-1

Method via string:

Guid hash = string.Join(':', array.Order()).MD5Hash();

An array should be ordered. Use any separator for recognizing different arrays, e.g. [1, 11] and [111] after join. GetHashCode() for string can give the same code for absolutely different strings (https://learn.microsoft.com/en-us/dotnet/api/system.string.gethashcode?view=net-9.0), so use MD5 algorithm to get hash code of string as Guid. Sure consider the performance MD5 in case thousands ops per sec., but for most regular tasks it's pretty applicable.

public static Guid MD5Hash(this string text)
{
    var hashed = MD5.HashData(Encoding.Unicode.GetBytes(text));
    return Guid.Parse(BitConverter.ToString(hashed, 0).Replace("-", string.Empty));
}
Improve this answer

Comments

-3

I would recommend:

HashCode.Combine(array)

For .NET Core 2.1 / .NET Standard 2.1 / .NET 5 and later.

Improve this answer

2 Comments

This will just be a hash code based on the address of the array in memory - not a hash code based on the contents of the array.
The edit queue for this answer is full but a correct solution based on HashCode.Add() is given in stackoverflow.com/questions/59375124/….

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.