• 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

Regarding HashMap

 
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


when we search for an element or remove an element from a HashMap , does it
depend on the size of the HashMap.
 
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

Simran Dass wrote:

when we search for an element or remove an element from a HashMap , does it
depend on the size of the HashMap.



Does what "depend on the size of the HashMap"?

Henry
 
Sheriff
Posts: 9707
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Simran Dass wrote: when we search for an element or remove an element from a HashMap , does it depend on the size of the HashMap.


Does what depend upon the size of the HashMap??

[Wow, Henry and I posted the same thing at an interval of 25 seconds ]
 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Does searching an element in a hasmap depend on the hashmap's size ?

Does removing an element from a hasmap depend on the hashmap's size ?

 
Ranch Hand
Posts: 317
Eclipse IDE
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If the elements you are putting into the HasMap are good enough to implement the equals - hashmap contract then it can make the process fast. But if there are too much elements in the same bucket then again it could lead to a little delay.

Map uses hashcode to crate a groups(or buckets) of different elements. Elements with same hascode will be kept in same group so there could be multiple elements in same group. At the time of searching, first the hasmap of the element will be calculated, matching hashcodee group will be searched, and the element will be compared with each of the element of the searched group.

So in this way we can say that operation really don't depend on the size of the hashmap but the hashcode implementation of the elements being added to the hashmap.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Simran Dass wrote:Does searching an element in a hasmap depend on the hashmap's size ?
Does removing an element from a hasmap depend on the hashmap's size ?


What do you mean?

Did you want to ask about the speed, i.e. if searching or removing an element takes longer if the HashMap contains more elements? (If that's what you mean then why didn't you say so?). Obviously yes, if the HashMap contains more elements, then searching for an element or removing an element takes longer. It doesn't scale linearly though (if the HashMap contains twice as much elements, it does not mean that searching for an element takes twice as long).
 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Jesper , Its written in books(Schildt) that -

" in a HashMap the time for basic operations like adding,removing etc. remain
constant even for large sets of data "


THIS IS what is CONFUSING me. I have exam next week and so even more confused
than before. If asked - "Does searching an element in a hashmap depend on its
size" - TRue or False . What shoild be my answer
 
Ranch Hand
Posts: 320
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm going to jump in here and try this... I think that the correct question is "when we search for an element or remove an element from a HashMap , does the time to locate an element depend on the size of the HashMap."

The answer is yes but it is going to depend largely on the hashing method that you define. The secret to hash based storage is that it is a "two part" scheme. A hashing algorithm is supposed to use calculation of some sort to divide all of the possible values into a number of coarse units... .often called hash buckets. Then, in each hash bucket... a more linear search is used.

If the hash algorithm chosen is reasonably effective then the object being stored will be somewhat evenly divided between the buckets and no ONE bucket will have an unreasonably long linear search. That is the "time smoothing" effect that is desired in large searches.

If the hash algorithm is not so good then you may have unevenly populated hash buckets which means some buckets will have many things in them (longer linear search) and some buckets will have not much... maybe even none (very short linear search... in the case of not much).

The better the hash.... the more evenly the buckets are filled... the more uniform the response time.

The worse the hash... the more UNevenly the buckets are filled.... and the response time will be irregular.

Does that answer your question?

 
Simran Dass
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Yes Bob , Thankyou so much.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic