Is there a "good enough" hash function for the average programmer?

We are told that we should implement hashCode() for our classes but most people like me have no real idea of how to do this or what happens if we get it "wrong". For example I have a need for a hash function for indexing nodes in a tree (Finding the most frequent subtrees in a collection of (parse) trees). In this case I need to recursively generate hashcodes based on ordered child nodes, e.g.

hashCode = function(c开发者_StackOverflow中文版hild1.hashCode, child2.hashCode, ...)

In a recent discussion of hashCodes answers included a hash for strings (based on a long prime and 31) and also bitshifting. The String hash is:

// adapted from String.hashCode()
public static long hash(String string) {
  long h = 1125899906842597L; // prime
  int len = string.length();

  for (int i = 0; i < len; i++) {
    h = 31*h + string.charAt(i);
  }
  return h;
}

I'm not interested in security and don't mind collisions. Is there a "universal function" for combining hashcodes of ordered objects that will do more good than harm (and more good than not calling it at all)?

Also is there a site where we can look up common cases? strings, lists, etc.)

I didn't specify a language as I was hoping there were universal approaches. But if it is seriously language-specific then please indicate the language and why it's not universal.

UPDATE Two suggestions are to use the IDE's hashCode generator. That seems an excellent default; Here's Netbeans:

public int hashCode() {
    int hash = 5;
// objects
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0);
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0);
// a string
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0);
    return hash;
}

There is an excellent hashCode() in Joshua Bloch's Effective Java. Sample Chapter 3, "Methods Common to All Objects" was free (well, it used to be back when there was a page on Sun's old site for it. If you search you might still find a PDF version of that chapter lying around somewhere).

You could also look at the source for HashCodeBuilder in Apache Commons Lang, but just don't copy it for class without citing it. It is time well spent to actually learn about this -- it will make you a better person.

Though missing the tag, I'll assume you're talking about Java.

One "lazy" solution comes packaged with Eclipse 3.5, which will generate hash codes for you at the push of a button. toString() and equals(), too. Very nice! I suspect you can find similar functionality in IDEA and NetBeans.

Other than that, practically any hash function that consistently generates the same value for the same input will do. This will (probably) only impact the efficiency of stuff like HashMaps.

If you're speaking in regards to defining hashcodes for custom classes, the best bet is to define some sort of mathematical concatenation of all of your fields hashcode functions.

In defining the hashcode, your goal is typically to minimize collisions so if you do something like this, you'll typically be in the clear.

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)...

If you're on Windows, you can use HashData().

This is a hash code combining function that I use (in C#):

public static int CombineHashCodes(params int[] hashCodes)
{
    unchecked
    {
        var result = 0;
        foreach (var hash in hashCodes)
            result = (result * 397) ^ hash;
        return result;
    }
}

The intuitive reasoning is that the combination aspect is the XOR operator. This is how .NET 4 does it for Tuples:

public static int CombineHashCodes(int h1, int h2)
{
    return ((h1 << 5) + h1) ^ h2;
} 

To answer your question of what can go wrong: the hashcode generated by your function will be used to find the place for instances of your class if you put it in a hashtable (dictionary/map). If your hashfunction generates too many collisions, the performance of you hashtables can be as bad as O(n).

In any managed environment the raw implementation of an objects hash function is the memory address itself. If you do not care about the properties of an hash function any value will do, as long as some kind of equivalence relation exists between to separate instances that represents the same value.

If your familiar with relational database design, think about your object's primary key? What values constitutes the primary key?

Say that it's a, b and c, well, then your implementation of hashCode would look like this

return a.hashCode() ^ b.hashCode() ^ c.hashCode();

^ is the XOR (exclusive OR) bit-wise operation, this way you can chain together any number of values to form a hash value, and still maintain a decent spread.