Say I have an object that stores a byte array and I want to be able to efficiently generate a hashcode for it. I've used the cryptographic hash functions for this in the past because they are easy to implement, but they are doing a lot more work than they should to be cryptographically oneway and I don't care about that (I'm just using the hashcode as a key into a hashtable).
Here's what I have today:
struct SomeData : IEquatable<SomeData>
{
private readonly byte[] data;
public SomeData(byte[] data)
{
if (null == data || data.Length <= 0)
{ throw new ArgumentException("data"); }
this.data = new byte[data.Length];
Array.Copy(data, this.data, data.Length);
}
public override bool Equals(object obj)
{ return obj is SomeData && Equals((SomeData)obj); }
public bool Equals(SomeData other)
{
if (other.data.Length != data.Length)
{ return false; }
for (int i = 0; i < data.Length; ++i)
{
if (data[i] != other.data[i])
{ return false; }
}
return true;
}
public override int GetHashCode()
{ return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0); }
}
Any thoughts?
-
So you need to generate a key for your hashtable entries that needs to be unique but doesn't really mean anything in and of itself?
-
If you are looking for performance, I tested a few hash keys and I recommend Bob Jenkin's hash function. It is both crazy fast to compute and will give as little collisions as the cryptographic hash you used until now.
I don't know C# at all and I don't know if it can link with C, but here is its implementation in C.
-
The hash code of an object shouldn't be unique.
The checking rule is: hash codes are equal? Then call the full (slow) Equals method
Hash codes are not equal? Then the two items are definitely not equal.
All you want is a
GetHashCodealgorithm that splits up your collection into roughly even groups - it shouldn't form the key as theHashTableorDictionary<>will need to use the hash to optimise retrieval.How long do you expect the data to be? How random? If lengths vary greatly (say for files) then just return the length. If lengths are likely to be similar look at a subset of the bytes that varies.
GetHashCode should be a lot quicker than Equals, but doesn't need to be unique.
Andrew Hare : +1 That was one of the clearest explanations I have ever heard for why it is beneficial to override Equals *and* GetHashcode. -
Is using the existing hashcode from the byte array field not good enough? Also note that in the Equals method you should check that the arrays are the same size before doing the compare.
-
Generating a good hash is easier said than done. Remember, you're basically representing n bytes of data with m bits of information. The larger your data set and the smaller m is, the more likely you'll get a collision ... two pieces of data resolving to the same hash.
The simplest hash I ever learned was simply XORing all the bytes together. It's easy, faster than most complicated hash algorithms and a halfway decent general-purpose hash algorithm for small data sets. It's the Bubble Sort of hash algorithms really. Since the simple implementation would leave you with 8 bits, that's only 256 hashes ... not so hot. You could XOR chunks instead of individal bytes, but then the algorithm gets much more complicated.
So certainly, the cryptographic algorithms are maybe doing some stuff you don't need ... but they're also a huge step up in general-purpose hash quality. The MD5 hash you're using has 128 bits, with billions and billions of possible hashes. The only way you're likely to get something better is to take some representative samples of the data you expect to be going through your application and try various algorithms on it to see how many collisions you get.
So until I see some reason to not use a canned hash algorithm (performance, perhaps?), I'm going to have to recommend you stick with what you've got.
-
Have you compared with the SHA1CryptoServiceProvider.ComputeHash method? It takes a byte array and returns a SHA1 hash, and I believe it's pretty well optimized. I used it in an Identicon Handler that performed pretty well under load.
Jonathan C Dickinson : SHA1 is slower than MD5. If you are not worried about security then use MD5. -
dp: You are right that I missed a check in Equals, I have updated it. Using the existing hashcode from the byte array will result in reference equality (or at least that same concept translated to hashcodes). for example:
byte[] b1 = new byte[] { 1 }; byte[] b2 = new byte[] { 1 }; int h1 = b1.GetHashCode(); int h2 = b2.GetHashCode();With that code, despite the two byte arrays having the same values within them, they are referring to different parts of memory and will result in (probably) different hash codes. I need the hash codes for two byte arrays with the same contents to be equal.
-
RuntimeHelpers.GetHashCode might help:
From Msdn:
Serves as a hash function for a particular type, suitable for use in hashing algorithms and data structures such as a hash table.
-
Whether you want a perfect hashfunction (different value for each object that evaluates to equal) or just a pretty good one is always a performance tradeoff, it takes normally time to compute a good hashfunction and if your dataset is smallish you're better of with a fast function. The most important (as your second post points out) is correctness, and to achieve that all you need is to return the Lenght of the array. Depending on your dataset that might even be ok. If it isn't (say all your arrays are equally long) you can go with something cheap like looking at the first and last value and XORing their values and then add more complexity as you see fit for your data.
A quick way to see how your hashfunction performs on your data is to add all the data to a hashtable and count the number of times the Equals function gets called, if it is too often you have more work to do on the function. If you do this just keep in mind that the hashtable's size needs to be set bigger than your dataset when you start, otherwise you are going to rehash the data which will trigger reinserts and more Equals evaluations (though possibly more realistic?)
For some objects (not this one) a quick HashCode can be generated by ToString().GetHashCode(), certainly not optimal, but useful as people tend to return something close to the identity of the object from ToString() and that is exactly what GetHashcode is looking for
Trivia: The worst performance I have ever seen was when someone by mistake returned a constant from GetHashCode, easy to spot with a debugger though, especially if you do lots of lookups in your hashtable
-
Borrowing from the code generated by JetBrains software, I have settled on this function:
public override int GetHashCode() { unchecked { var result = 0; foreach (byte b in _key) result = (result*31) ^ b; return result; } }The problem with just XOring the bytes is that 3/4 (3 bytes) of the returned value has only 2 possible values (all on or all off). This spreads the bits around a little more.
Setting a breakpoint in Equals was a good suggestion. Adding about 200,000 entries of my data to a Dictionary, sees about 10 Equals calls (or 1/20,000).
-
Don't use cryptographic hashes for a hashtable, that's ridiculous/overkill.
Here ya go... Modified FNV Hash in C#
http://bretm.home.comcast.net/hash/6.html
public static int ComputeHash(params byte[] data) { unchecked { const int p = 16777619; int hash = (int)2166136261; for (int i = 0; i < data.Length; i++) hash = (hash ^ data[i]) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } }Mark : You rock! This seems to work well for unique filenames :) -
Following post contains code snippet to generate MD5 hash code using C#:
http://www.etechplanet.com/post/2009/03/29/Generate-MD5-Hash-code-from-a-string-using-C.aspx
0 comments:
Post a Comment