aspose file tools*
The moose likes Beginning Java and the fly likes why we can't avoid hash collision in practice ? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "why we can Watch "why we can New topic
Author

why we can't avoid hash collision in practice ?

Edward Chen
Ranch Hand

Joined: Dec 23, 2003
Posts: 798
why we can't avoid hash collision in practice ? Hashmap use array of array to store value, the reason is hash key value collision. Then why we can't avoid it ? for me, I didn't see how difficult it is, we just use a primary key like in the db ...

Thanks.
Thakur Sachin Singh
Ranch Hand

Joined: Jun 15, 2010
Posts: 232

i also want to know.


SCJP 6- 91%, IBM DB2, IBM RAD Certified
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Well, sometimes you can avoid it, and sometimes you can't. What if the key is a String? How many different possible Strings are there that might go into a Map? Hint: it's a really, really big number. The hashCode() must be an int however. How many different possible ints are there? Hint: Integer.MAX_VALUE is a big number, but much much smaller than the previous big number. Therefore, out of all possible Strings, some Strings must have the same hashCode() - no matter how you choose to calculate hashCode(). This leads to the possibility of hash collisions.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Edward Chen wrote:Hashmap use array of array to store value

no, it uses Array.
Thakur Sachin Singh
Ranch Hand

Joined: Jun 15, 2010
Posts: 232

it is good information for us...but i want some more information about this.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14269
    
  21

Mike already explained the reason.

Let's have a look at String objects that consist of exactly 10 letters of the alphabet (A-Z). How many different strings are possible? The answer is: 26^10 = 141.167.095.653.376 different strings.

The hash code of an object is a 32-bit integer. So, how many different hash codes are possible? 2^32 = 4.294.967.296 different hash codes.

You see that there are many more possible strings than there are hash codes. Therefore, there must be different strings that have the same hash code.

Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Thakur Sachin Singh
Ranch Hand

Joined: Jun 15, 2010
Posts: 232

thanks for the information..its valuable for me
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: why we can't avoid hash collision in practice ?