• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

HashMap, Load Facor, Rehash Operation

 
Ranch Hand
Posts: 213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The 4th paragraph of the HashMap in Java documentation is as follows


As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.--


What is meant by "decrease the space overhead but increase the lookup time"

Then

If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur



What does the above sentence mean
Initial capacity is the number of empty elements at time of creation, If that is so maximum number of entries is the initial capacity.Is that correct?How is it assured that a rehash will not ever occur?

Regards Varuna
 
Marshal
Posts: 79179
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What it means is that you start with an initial capacity of 16, and a load factor of 0.75f, so rehashing occurs when you reach 12. If you only intend to store 10 key-value pairs in this Map, then it will never re-hash. If you store 13 pairs, then it will re-hash once and if you store 25 pairs it will re-hash twice. So to store 25 pairs without re-hashing you would need an initial capacity of 64.

I don't know whether re-hashing occurs after 11, or before 12, or after 12. You could work that out by going through the code: find a file called src.zip in your Java installation folder and unzip it.

If you set your load factor lower, eg 0.5f you will get rehashing at 8, so there will be more empty space. If you set your load factor at 1.0f you won't get rehashing until 16, but there will be more chance of two pairs with the same hashCode % 16, so they will land in the same "bucket" and look-up will be slower.
 
Varuna Seneviratna
Ranch Hand
Posts: 213
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So what I gather is "a rehash will not ever occur" is not correct is it?What ever the initial capacity is when ever the load factor is reached it will rehash.I am saying this with the assumption that if the number of entries that will have to be made can not be predetermined

but there will be more chance of two pairs with the same hashCode % 16, so they will land in the same "bucket" and look-up will be slower



I am not able to understand this.What is HashCode?Is it the Key?When entries are made up to 16(16th one also added) with the load factor 1.0f.Another 16 of empty elements will be added and the total number of elements will be 32, is it?

In the HashMap method list I couldn't find a method to get the number of total number entries possible. The size() returns only the number of entries already made.Is there a way to get the total number of possible entries?

By saying that if empty space increases lookup time will be slower, does this mean that when an search has to be carried out using a given Key all the elements even the empty ones will be looked up?

Regards Varuna
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hashing theory is actually something that you should have learned (or will learn) in your data structure class (Or algorithms depending on the school). So, you should review the course work (or pickup the book in advanced) from that class.

Trying to learn based on an implementation (even a Java implementation, that is highly used) is not as good as learning the theory directly.

Henry
 
Campbell Ritchie
Marshal
Posts: 79179
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Varuna Seneviratna wrote:"a rehash will not ever occur" . . .

Please explain what you think that statement means. It looks correct to me, but I think I can only explain more if I know what you understand by it.
 
Campbell Ritchie
Marshal
Posts: 79179
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Original thread in JiG(A)
 
To do a great right, do a little wrong - shakepeare. twisted little ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic