0

I gone through the Java's HashMap implementation methods put() and get(). I noticed that, when collision occurs, they compares hash of previous object with current one and also uses equals method for comparison. why is this necessary?. I feel comparing via equals method is enough. Please confirm if my assumption is correct. Please check below "else" part.

 //Put method logic    
         if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
         else {
                 Node<K,V> e; K k;
   //talking about below logic
              if (p.hash == hash && 
                ((k = p.key) == key || (key != null && key.equals(k))))
                            e = p;
vijaya kumar
  • 824
  • 2
  • 12
  • 21
  • take `"DFHXR"` and `"GCVUR"` - run to see their hashCode (last 5 bits actually). Is it the same? If it is, are they equal? – Eugene Sep 19 '21 at 02:37
  • They're strings. The point is that the hash code might collide, so check using equals as well. – Dave Newton Sep 19 '21 at 02:50
  • 6
    Could be just an optimisation. You check the hashcode first, which is fast. If they are unequal, you don't have to call `equals`, which could be relatively slow, to know that the objects are unequal. – Sweeper Sep 19 '21 at 02:53
  • @DaveNewton OP is not asking "why not just check hashcode". OP is asking "why not just check `equals`". – Sweeper Sep 19 '21 at 02:54
  • Sweeper is right. checking `==` for `hashCode` could be far less expensive than `equals`, my comment was supposed to get OP into starting to investigate that. – Eugene Sep 19 '21 at 02:56
  • @Eugene Hash codes of DFHXR and GCVUR are 64956800, 67651351 respectively. Sweeper's point makes sense to me. I'd like to understand your thought. pls explain – vijaya kumar Sep 19 '21 at 03:03
  • it will be complicated to explain if you do not know the internal details of `HashMap`. I'll give you a few hints, you can start working form here`public static void main(String[] args) { System.out.println(Integer.toBinaryString(hash("GCVUR") & 31)); System.out.println(Integer.toBinaryString(hash("DFHXR") & 31)); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }` – Eugene Sep 19 '21 at 03:10
  • it seems [this](https://stackoverflow.com/questions/46056113/java-hashmap-resizing/46069815#46069815) will get you in a starting position too, or [this](https://stackoverflow.com/questions/44745811/why-hashmap-resize-in-case-of-collision-or-worst-case/44746644#44746644) – Eugene Sep 19 '21 at 03:22
  • 1
    I think that your starting point for understanding why both `equals` and `hashCode` are used should be to read about [how hashtables work](https://en.wikipedia.org/wiki/Hash_table). Note that Java `HashMap` uses a form of "separate chaining" for collisions ... and that is when `equals` comes into play. The `hashCode()` result is used to find the correct bucket, and `equals(...)` calls are used to search the bucket. – Stephen C Sep 19 '21 at 05:35
  • Because it's a hash map. If it only used `equals()` it would be a linear search. – user207421 Sep 19 '21 at 06:37
  • @user207421 and Stephen C pls try to understand my question. and also check Sweeper's comment. – vijaya kumar Sep 24 '21 at 07:19

0 Answers0