• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

why we can't avoid hash collision in practice ?

 
Edward Chen
Ranch Hand
Posts: 798
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 248
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i also want to know.
 
Mike Simmons
Ranch Hand
Posts: 3040
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Edward Chen wrote:Hashmap use array of array to store value

no, it uses Array.
 
Thakur Sachin Singh
Ranch Hand
Posts: 248
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
it is good information for us...but i want some more information about this.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15216
36
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Thakur Sachin Singh
Ranch Hand
Posts: 248
Hibernate Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for the information..its valuable for me
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic