What is a hash function in java?

Mohit Deshpande picture Mohit Deshpande · Jun 18, 2010 · Viewed 22.4k times · Source

I have check out this Wikipedia page on it, but I still don't understand it. Can someone please help my dim-witted mind to understand the concepts of hashing, hashtable/hashmap, and hash functions? Some examples would really help.

Answer

polygenelubricants picture polygenelubricants · Jun 18, 2010

The Wikipedia article will have a lot of technical information, but a simplistic view of hashing is something like the following.

Imagine that there's a magical function that can give a number to any object. Given the same object, it always return the same number.

Immediately now you have a quick way to test if two objects are the same: ask this function for their numbers and compare. If they're different, then they're not the same.

But what if they have the same number? Could two different objects have the same number?

Yes, this is possible in most scenario. Let's say that the function can only give numbers between 1..10, for example, and there are 100 different objects. Then of course some different objects must have the same number. This is what is called a "collision". A "collision" makes our quick equality test not as useful, so as much as possible we want to minimize its happening. A good magical function is one that would try to minimize the number of "collision".

So what else can you do with this number? Well, you can use it to index an array. Given an object, you can put it at the index given by the number from this magical function. This array is essentially what a hashtable is; this magical function is a hash function.