3

I read in a book where it was mentioned that when we put elements in HashMap, internally it is stored in bucket. My question is

  1. Does hashmap store key-value pair altogether in the form of linked list? or does it store in linked list only when there is a collision?

  2. How does it retrieve the object when 2 different objects are stored in the same bucket?

Thanks!

Raedwald
  • 46,613
  • 43
  • 151
  • 237
Mike
  • 7,606
  • 25
  • 65
  • 82
  • possible duplicate of [HashMap collision](http://stackoverflow.com/questions/2239345/hashmap-collision) – Matt Ball Jul 07 '11 at 20:15
  • My question is very specific that does it have linked list even when there is no collision? – Mike Jul 07 '11 at 20:17
  • This could be useful: http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html#.ThYUH2GqLFk – zw324 Jul 07 '11 at 20:18
  • To know more about all these things read my [Internal life of HashMap](http://volodial.blogspot.com/2013/07/internal-life-of-hashmap-in-java.html) tutorial – Volodymyr Levytskyi Jul 25 '13 at 10:57

3 Answers3

4

Lots of details at http://en.wikipedia.org/wiki/Hash_table

See also Internal implementation of java.util.HashMap and HashSet

And of course you can use the source, Luke.

Updated: to specifically answer your Q, it stores an Entry, which has a reference to the next item in the bucket (if any). If there is only one item in the bucket then the reference will be null:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
Community
  • 1
  • 1
DNA
  • 42,007
  • 12
  • 107
  • 146
  • Let's say if I add only 1 item & its going to unique bucket with unique hash code, then in this case, how this bucket stores the key-value pair? Does it still store in the form of linked list or how exactly? – Mike Jul 07 '11 at 20:21
  • There will be a single Entry, containing the key and the value, but the 'next' variable will be null. This is a linked list for the special case of only one entry, i.e. there are no links! – DNA Aug 01 '11 at 10:58
3

The data type of the bucket Array is Map.Entry. When multiple entries fall in the same bucket they are stored in what is conceptually a unidirectional linked list, by holding references to the next Entry. Just the Entry at the 'head' is inside the array that is the buckets. However, there is never any use a java.util.LinkedList or some actual list class. The entries just form a list in and of themselves by holding references to their bucket-mates.

When there's more than one in a bucket, it starts with the one that's actually in the Map.Entry[], which is the head of the list, and just starts traversing and checking .equals() until it finds a match or next is null.

Affe
  • 47,174
  • 11
  • 83
  • 83
0

Best way to understand is by tracing source

  • In eclipse If configured jdk hit ctrl+shift+T type HashMap and AbstractMap
  • AbstractMap and HashMap

You only need to do it once !

Prashant Bhate
  • 10,907
  • 7
  • 47
  • 82