• 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

hashing collision

 
Ranch Hand
Posts: 361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
I want to store objects in Hashmap. Now suppose that some of these objects have same hashvalue, leading to collision, and are stored in same 'bucket'. If I want to retrieve objects from the bucket, how can I do that.
 
Ranch Hand
Posts: 1183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It doesn't matter if there are more than one object in one 'bucket'.

This just goes down to speed. If you have 12 objects in your Collection and they are distributed in 4 buckets, It's not really going to affect the speed.
If you have 1000000 objects distributed in 4 buckets, that's going to be a problem.
You see that a unique hashCode becomes more and more important the bigger your Collection gets.

Note that hashCode and equals work together to differentiate objects.
hashCode is the lookup for the 'bucket', equals then identifies the object you are looking for.

That means, if there are 5000000 objects in one bucket, that equals to a probable number of 5000000 iterations until the object in question was found.
 
Bartender
Posts: 6663
5
MyEclipse IDE Firefox Browser Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A client to a HashMap implementation should not have to worry about the concept of the "bucket". It really should not matter if the objects are stored in the same bucket or different buckets. The universe of values and their related compression maps are of no interest to the clients and shouldn't be.

Also with linear probing or double hashing it is not necessary that objects reside on the same bucket even after colliding. But then again a client need not worry about this.
 
reply
    Bookmark Topic Watch Topic
  • New Topic