0

I am confused about the hash function. This is a good hash function

private int hash(K key) {
    return (key.hashCode() & 0x7fffffff) % M;
    }

How would I turn that into a very bad hash function, would it be like this?

private int hash(K key) {
    return (key.hashCode() & 17) % M;
    }
C G
  • 31
  • 4
  • 1
    The worst valid `hashCode() ` implentation is one that always returns the same constant value, e.g. `1`. This still fulfills the contract, but is obviously not very uniformly distributed. – Hulk Oct 25 '20 at 23:52
  • so it could be any number like 1 or 17? ((key.hashCode() & 17)) – C G Oct 25 '20 at 23:53
  • Yes. What makes it bad is that it reduces your bucket count to 1, thus turning your hash map into a linked list or an array, or what ever data structure is used to store information in the buckets. – WJS Oct 25 '20 at 23:54
  • See [Object.hashCode()](https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/lang/Object.html#hashCode()) for the general contract (also see the one for `equals`, they are closely related). – Hulk Oct 25 '20 at 23:57
  • Yes, thank you so much. – C G Oct 26 '20 at 00:01
  • Basically, there are multiple ways to calculate reasonably well-distributed hash codes - most of them involve prime numbers. They differ in performance characteristics and details of the distribution they produce. – Hulk Oct 26 '20 at 00:01

0 Answers0