Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Regarding traversal time in Map

 
saurabh kuma
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Friends,

I read somewhere

Traversal of a map is through one of its collection-views. For an underlying LinkedHashMap, the traversal time is proportional to the size of the map—regardless of its capacity. However, for an underlying HashMap, it is proportional to the capacity of the map.


I didn't get this line, Please help

Thanks
Saurabh
 
Richard Tookey
Bartender
Posts: 1166
17
Java Linux Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you "read somewhere" and can quote it surely you can elaborate 'somewhere' by posting a reverence.
 
saurabh kuma
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I read it in

A Programmer's Guide to Java SCJP Certification
Third Edition by Khalid A. Mughal
chapter 15, pg 824 line 3

Thanks
Saurabh
 
Steve Luke
Bartender
Posts: 4181
21
IntelliJ IDE Java Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you understand the difference between a collection's capacity and its size?

The capacity is (generally) the number of Objects it can hold, while its size is the number of Objects it does hold. What the quote says is the LinkedHashMap's speed depends on the number of Objects it actually holds, while the HashMap is dependent more on the number of Objects it can hold.
 
Ivan Jozsef Balazs
Rancher
Posts: 972
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A vague guess:
A linked hash map offers a way to wade through the elements, so the traversal time corresponds to the number of the elements, that is, the size.
If you have to go through all slots, then the capacity comes into the picture.

Does it matter much?

Well, iet us take a map, let us stuff it with elements so both the size and the capacity go high.
Then let us delete most of them, so the size goes down - does the capacity remain high?
If the capacity gets adjusted, that is, it also goes down, then there is not much difference.

 
saurabh kuma
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Hi Friends

Thanks for the help

Steve, as you said:

The capacity is (generally) the number of Objects it can hold, while its size is the number of Objects it does hold. What the quote says is the LinkedHashMap's speed depends on the number of Objects it actually holds, while the HashMap is dependent more on the number of Objects it can hold.


I understood that in LinkedHashMap traversal time is dependent on number of elements. But I have a doubt in case of HashMap. In HashMap if we have say 50 buckets(which is capacity) and 20 elements linked to this buckets, then traversal time will be 50+20 ?

Thanks
Saurabh
 
Volodymyr Lysenko
Ranch Hand
Posts: 511
1
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In HashMap if we have say 50 buckets(which is capacity) and 20 elements linked to this buckets, then traversal time will be 50+20 ?

How HashMap stores element you should learn at first.
Then you will know that your mappings in hashmap are spread around the backing array god knows on each index and some Entries even occupy the same index.
This code is from HashIterator used by entrySet() method to return next entry:

At first we check if there is one more Entry at the same bucket by (next = e.next) == null and if there is no then we move inside to while loop. In this while loop we iterate backing array(called table) untill current index becomes equal to length or new Entry at index++ is found. If new Entry at new bucket is found this while loop breaks due to condition - (next = t[index++]) == null.

To know java collections profoundly and be confidently please read my tutorials
 
Steve Luke
Bartender
Posts: 4181
21
IntelliJ IDE Java Python
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
saurabh kuma wrote:In HashMap if we have say 50 buckets(which is capacity) and 20 elements linked to this buckets, then traversal time will be 50+20 ?

In a worst case scenario, that is about right. We know to traverse the table, you need to hit every bucket, so the traversal will be at minimum 50. In the worst case, all Entries will be in the same bucket, so after the first one in the bucket is touched by the bucket-traversal, you would have 19 additional operations, and you would get 50+19. In the best case scenario (well dispersed hashcodes) each of the 20 elements would be in its own bucket, and the traversal would be 50+0 additional traversal operations.
 
saurabh kuma
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Steve
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic