2

HashMap produces a hashCode using the key user submits. Following can be two cases:

1) If two keys (Object) are same:

for instance 

hashmap.put(1,"one");
hashmap.put(1,"another one");

Now , initially "one" will be inserted and then it will be overridden by "another one".

2) If the hashCode for two different objects are same: for instance , if I have a bucket of size 5 and I try to:

hashmap.put(5,"this is five");
hashmap.put(25,"this is twenty five");

since hash % (SIZE-1) will point to the same location , LinkedList will be created to store the values as: "this is twenty five" -> "this is five"

Please correct me if I am wrong

Pournima Bedarkar
  • 392
  • 2
  • 10
  • 5
    You're almost right. However, Java doesn't necessarily use a linked list to store values that go in the same bucket. If there are enough values in the bucket, it will use a red-black tree (a kind of binary search tree) instead of a list. This is a new feature of Java 8 and can speed things up in some cases. Other than that detail, your basic understanding is correct. – ajb Sep 25 '15 at 07:01
  • 2
    From a functional point of view you can ignore `HashMap` and just use the contract specified for `Map`. That the implementation is a `HashMap` becomes only interesting if you deal with non-functional aspects like performance. – Henry Sep 25 '15 at 07:33

1 Answers1

1

Your first question is about Map's in general. The behavior of a Map when you call .put() with the same key is a documented part of the Map public contract. Any (reasonable) Map implementation must behave this way, regardless of the specific implementation.

Your second question is about the implementation of HashMap; how HashMap resolves collisions is not part of its contract (though the documentation does describe the behavior), and therefore could (and does) change between releases. Not all Map implementations rely on .hashCode() and such implementations have no need to resolve such collisions.

The difference conceptually is between "correctness" and "efficiency". Because the collision resolution behavior is not a documented part of the contract it can change over time. Before Java 8 HashMap used a linked-list structure (not to be confused with java.util.LinkedList), as of Java 8 they instead sometimes use a red-black tree structure (not to be confused with java.util.TreeMap) for improved efficiency.

You might also be interested in my answer to this question, which explores the relationship between an Object's hashcode and equality.

Community
  • 1
  • 1
dimo414
  • 47,227
  • 18
  • 148
  • 244