Isn't 'int GetHashCode' a bit short-sighted?

Question

Given that .Net has the ability to detect bitness via IntPtr (looking through reflector a good amount of it is marked unsafe, though - shame) I've been thinking that GetHashCode returning an int is potentially short-sighted.

I know that ultimately with a good hashing algorithm the billions of permutations offered by Int32 are absolutely adequate, but even so, the narrower the possible set of hashes the slower hashed key lookups are as more linear searching will be required.

Equally - am I the only one who finds this amusing:

struct Int64{
  public override int GetHashCode()
  {
    return (((int) this) ^ ((int) (this >> 0x20)));
  }
}

Whilst Int32 simply returns this.

If IntPtr is out of question because of performance concerns, perhaps an IHashCode that implements IEquatable etc is better?

As our platforms get larger and larger in terms of memory capacity, disk size etc, surely the days of 32 bit hashes being enough are potentially numbered?

Or is it simply the case that the overhead involved in either abstracting out the hash via interfaces, or adapting the size of the hash according to the platform outweighs any potential performance benefits?

Answer 1

The Int64 hash function is there to make sure that all the bits are considered - so basically it is XORing the top 32 bits with the bottom 32 bits. I can't really imagine a better general-purpose one. (Truncating to Int32 would be no good - how could you then properly hash 64-bit values which had all zeros in the lower 32 bits?)

If IntPtr were used as the hash return value, then code would have to have conditional branches (is it 32-bit? is it 64-bit? etc), which would slow down the hash functions, defeating the whole point.

I would say that if you have a hashtable which actually has 2 billion buckets, you're probably at the stage of writing an entire custom system anyway. (Possibly a database would be a better choice?) At that size, making sure the buckets were filled evenly would be a more pressing concern. (In other words, a better hash function would probably pay more dividends than a larger number of buckets).

There would be nothing to stop you implementing a base class which did have an equivalent 64-bit hash function, if you did want a multi-gigabyte map in memory. You'd have to write your own Dictionary equivalent however.

Answer 2

You do realize that the hash code returned by GetHashCode is used for addressing in a hash table? Using a bigger data type would be a futile exercise since all hash tables are smaller anyway. Additional information would simply be wasted because it cannot be used adequately.

Common hash tables have in the order of a few thousand to a few million entries. A 32 bit integer is more than sufficient to cover this range of indices.