• Post Reply Bookmark Topic Watch Topic
  • New Topic

choosing hashcode  RSS feed

 
M Mehta
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am wondering what is the best implementation of a hashcode. Should I try to get a unique hascode for every distinct object? or can there be same hascodes for more than one distinct objects.

Why I have this doubt is, suppose a hashcode is implemented to get unique for every distinct object, and we try to place these objects in a HashSet, every object will be placed in a different bucket. So it will end up in a leanier search. and if there are multiple objects mapped to same hascode, more than one objects will be there in a single bucket. What is the best approach then?

I hope I have made my question clear.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
M Mehta wrote:I am wondering what is the best implementation of a hashcode. Should I try to get a unique hascode for every distinct object? or can there be same hascodes for more than one distinct objects.


In the general case, it is impossible to guarantee that hashcodes will be unique for each object. It's possible to do it for certain classes when there are appropriate constraints around and knowledge of the variables that make up its state, but it's not something we strive for in most cases.

There is no single "best" implementation, since what's best depends on the domain of your objects' states, both what's possible and what will actually come up at runtime. A good general-purpose approach can be found here.

Why I have this doubt is, suppose a hashcode is implemented to get unique for every distinct object, and we try to place these objects in a HashSet, every object will be placed in a different bucket. So it will end up in a leanier search
.

No, if the hashcode is unique for each object, that does not guarantee taht each object will get its own bucket. To guarantee that, we'd have to have 2^32 buckets.

Aside from that, you seem to have it backwards. Finding a bucket is NOT a linear search. Finding an object in a bucket is a linear search. So if we have a hashcode that provides a good distribution, with objects spread out across as many buckets as possible, and few entries in each bucket, you will have fast lookups, with very little linear searching. The worst possible hashcode that still provides correct behavior is one that simply returns a constant--the same value for every object. In this case, we will have a single bucket, with every object in it, and every lookup will be a linear search of that one bucket.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!