1

If you were creating creating a generic hash table in Java (assume it didn't already have one), then how would you implement its default hash function? I know you can pass one in (via an interface), but most data structures have defaults.

My Attempt:

As Java generics require reference types, and all reference types in Java implement hashCode(), I figured that you could just use T.hashCode() % backingArraySize as the hash function, and that this would be sufficient. After all, the implementer of any type you may store in the hash table should give their type an appropriate hashCode() function, right?

Is there a better way to do this?

John Humphreys
  • 37,047
  • 37
  • 155
  • 255
  • Define **better**. There are many ways of implementing an hash table (open addressing, chaining, kind of buckets, etc) and there are multiple kind of data and distribution which could lead to different hashing function requirements. – Jack May 26 '14 at 15:40
  • Interesting... Why would the implementation matter; whether you're open addressing or chaining, less collisions is still more efficient right? – John Humphreys May 26 '14 at 15:45
  • Why generic? Since all classes implement `hashCode()`, just make the parameter `Object` and be done with it. Generics (which offers type bounds) serves no purpose. – Bohemian May 26 '14 at 16:04
  • 2
    By the way, `hashCode()` can be negative, in that case `hashcode() % size` can also be negative. – harold May 26 '14 at 17:41

1 Answers1

1

In my hashtable implementation I decided to use plain hashCode() % backingArraySize (i. e. yours suggestion) when the algorithm isn't a subject of primary clustering and hashCode() * 2654435761 (the constant is taken from this answer) when it is, i. e. for linear hashing implementation. The reason is that many default hashCode() implementations don't distribute values across full int range well (all numberic boxed types, String, List), and when the keys are somehow biased linear hashing may suffer from primary clustering.

Community
  • 1
  • 1
leventov
  • 14,760
  • 11
  • 69
  • 98