0

I see that the implementation of the hashmap applies some kind of transformation to the hashCode to get the actual hash.
Could some one please help me understand how this transformation works and additionally if it would make any difference if the object to store is just an integer?

Jim
  • 18,826
  • 34
  • 135
  • 254
  • What are you trying to achieve? – Ritesh Karwa May 13 '15 at 20:59
  • *Which* implementation of HashMap? – aioobe May 13 '15 at 20:59
  • @aioobe Does `HashMap` have another child apart of `LinkedHashMap`? – Luiggi Mendoza May 13 '15 at 21:00
  • @aioobe:Is it different in IBM vs Java vs OpenJDK you mean? – Jim May 13 '15 at 21:02
  • No, but there's more than one JRE out there., @Jim, yes. Are you referring to OpenJDK? – aioobe May 13 '15 at 21:02
  • hashCode() function which returns an integer value is the Hash function. The important point to note that , this method is present in Object class ( Mother of all class ) . This is the code for the hash function(also known as hashCode method) in Object Class : public native int hashCode(); The most important point to note from the above line : hashCode method return int value . So the Hash value is the int value returned by the hash function . – Ritesh Karwa May 13 '15 at 21:03
  • As of recent versions of Java, java.util.HashMap no longer applies an additional "mix" on the hashCode to get a new hash. – Brett Kail May 13 '15 at 21:03
  • @RiteshK:You are wrong. That hashcode is first "transformed" by bit manipulation and then used – Jim May 13 '15 at 21:04
  • @RiteshK He is not talking about the `hashCode` implementation of `Hashmap`. – Tom May 13 '15 at 21:04
  • @bkail:You mean Java 8? – Jim May 13 '15 at 21:05
  • @aioobe: We could use OpenJDK as a "teaching" example yes – Jim May 13 '15 at 21:05
  • 1
    @Jim, if you include the code you're curious about in the question it would be self contained and it would be easier to answer the question. – aioobe May 13 '15 at 21:06
  • 1
    @Jim have you read the JavaDoc of the `hash` method? Try [this](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.hash%28int%29) and [this](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#HashMap.hash%28java.lang.Object%29) and maybe the other versions, if they also have different descriptions. (If you open these links, please scroll a few lines up to see the JavaDoc) – Tom May 13 '15 at 21:06
  • @Tom: That is my question. How does this bit manipulation do what they describe *and* also if it makes sense to do it if the keys are integers – Jim May 13 '15 at 21:08
  • @Jim I was wrong, the HashMap.hash function was simplified in Java 8, but it still exists (as Laf's answer highlights). – Brett Kail May 13 '15 at 21:13
  • It doesn't hurt significantly to do it no matter what, and there's no really good way to do it only for some types. – Louis Wasserman May 13 '15 at 21:40
  • @LouisWasserman:Let me rephrase: If for integers we did not apply this, would we lose some benefit? – Jim May 13 '15 at 22:12
  • @Jim: It's a difficult-to-predict tradeoff, but generally, spreading out inputs is good no matter what, so I'd say yes? Either way, making this not apply just for integers would almost certainly hurt more than it helped. – Louis Wasserman May 13 '15 at 22:14

1 Answers1

2

As taken from the Javadoc of the method hash(Object) in the OpenJDK Java 8 HashMap implementation (assuming this is the JVM you are concerned about):

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Stuart Marks
  • 127,867
  • 37
  • 205
  • 259
Laf
  • 7,965
  • 4
  • 37
  • 52