What is hashCode used for? Is it unique?

Question

After learning what it is all about, I thought to write a hopefully simpler explanation via analogy:

Summary: What is a hashcode?

• It's a fingerprint. We can use this finger print to identify people of interest.

Read below for more details:

Think of a Hashcode as us trying to To Uniquely Identify Someone

I am a detective, on the look out for a criminal. Let us call him Mr Cruel. (He was a notorious murderer when I was a kid -- he broke into a house kidnapped and murdered a poor girl, dumped her body and he's still out on the loose - but that's a separate matter). Mr Cruel has certain peculiar characteristics that I can use to uniquely identify him amongst a sea of people. We have 25 million people in Australia. One of them is Mr Cruel. How can we find him?

Bad ways of Identifying Mr Cruel

Apparently Mr Cruel has blue eyes. That's not much help because almost half the population in Australia also has blue eyes.

Good ways of Identifying Mr Cruel

What else can i use? I know: I will use a fingerprint!

Advantages:

• It is really really hard for two people to have the same finger print (not impossible, but extremely unlikely).
• Mr Cruel's fingerprint will never change.
• Every single part of Mr Cruel's entire being: his looks, hair colour, personality, eating habits etc must (ideally) be reflected in his fingerprint, such that if he has a brother (who is very similar but not the same) - then both should have different finger prints. I say "should" because we cannot guarantee 100% that two people in this world will have different fingerprints.
• But we can always guarantee that Mr Cruel will always have the same finger print - and that his fingerprint will NEVER change.

The above characteristics generally make for good hash functions.

So what's the deal with 'Collisions'?

So imagine if I get a lead and I find someone matching Mr Cruel's fingerprints. Does this mean I have found Mr Cruel?

........perhaps! I must take a closer look. If i am using SHA256 (a hashing function) and I am looking in a small town with only 5 people - then there is a very good chance I found him! But if I am using MD5 (another famous hashing function) and checking for fingerprints in a town with +2^1000 people, then it is a fairly good possibility that two entirely different people might have the same fingerprint.

So what is the benefit of all this anyways?

The only real benefit of hashcodes is if you want to put something in a hash table - and with hash tables you'd want to find objects quickly - and that's where the hash code comes in. They allow you to find things in hash tables really quickly. It's a hack that massively improves performance, but at a small expense of accuracy.

So let's imagine we have a hash table filled with people - 25 million suspects in Australia. Mr Cruel is somewhere in there..... How can we find him really quickly? We need to sort through them all: to find a potential match, or to otherwise acquit potential suspects. You don't want to consider each person's unique characteristics because that would take too much time. What would you use instead? You'd use a hashcode! A hashcode can tell you if two people are different. Whether Joe Bloggs is NOT Mr Cruel. If the prints don't match then you know it's definitely NOT Mr Cruel. But, if the finger prints do match then depending on the hash function you used, chances are already fairly good you found your man. But it's not 100%. The only way you can be certain is to investigate further: (i) did he/she have an opportunity/motive, (ii) witnesses etc etc.

When you are using computers if two objects have the same hash code value, then you again need to investigate further whether they are truly equal. e.g. You'd have to check whether the objects have e.g. the same height, same weight etc, if the integers are the same, or if the customer_id is a match, and then come to the conclusion whether they are the same. this is typically done perhaps by implementing an IComparer or IEquality interfaces.

Key Summary

So basically a hashcode is a finger print.

1. Two different people/objects can theoretically still have the same fingerprint. Or in other words. If you have two fingerprints that are the same.........then they need not both come from the same person/object.
2. Buuuuuut, the same person/object will always return the same fingerprint.
3. Which means that if two objects return different hash codes then you know for 100% certainty that those objects are different.

It takes a good 3 minutes to get your head around the above. Perhaps read it a few times till it makes sense. I hope this helps someone because it took a lot of grief for me to learn it all!

MSDN says:

A hash code is a numeric value that is used to identify an object during equality testing. It can also serve as an index for an object in a collection.

The GetHashCode method is suitable for use in hashing algorithms and data structures such as a hash table.

The default implementation of the GetHashCode method does not guarantee unique return values for different objects. Furthermore, the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value it returns will be the same between different versions of the .NET Framework. Consequently, the default implementation of this method must not be used as a unique object identifier for hashing purposes.

The GetHashCode method can be overridden by a derived type. Value types must override this method to provide a hash function that is appropriate for that type and to provide a useful distribution in a hash table. For uniqueness, the hash code must be based on the value of an instance field or property instead of a static field or property.

Objects used as a key in a Hashtable object must also override the GetHashCode method because those objects must generate their own hash code. If an object used as a key does not provide a useful implementation of GetHashCode, you can specify a hash code provider when the Hashtable object is constructed. Prior to the .NET Framework version 2.0, the hash code provider was based on the System.Collections.IHashCodeProvider interface. Starting with version 2.0, the hash code provider is based on the System.Collections.IEqualityComparer interface.

Basically, hash codes exist to make hashtables possible.
Two equal objects are guaranteed to have equal hashcodes.
Two unequal objects are not guaranteed to have unequal hashcodes (that's called a collision).

GetHashCode() is used to help support using the object as a key for hash tables. (A similar thing exists in Java etc). The goal is for every object to return a distinct hash code, but this often can't be absolutely guaranteed. It is required though that two logically equal objects return the same hash code.

A typical hash table implementation starts with the hashCode value, takes a modulus (thus constraining the value within a range) and uses it as an index to an array of "buckets".

It's not unique to WP7--it's present on all .Net objects. It sort of does what you describe, but I would not recommend it as a unique identifier in your apps, as it is not guaranteed to be unique.

Object.GetHashCode Method

This is from the msdn article here:

https://blogs.msdn.microsoft.com/tomarcher/2006/05/10/are-hash-codes-unique/

"While you will hear people state that hash codes generate a unique value for a given input, the fact is that, while difficult to accomplish, it is technically feasible to find two different data inputs that hash to the same value. However, the true determining factors regarding the effectiveness of a hash algorithm lie in the length of the generated hash code and the complexity of the data being hashed."

So just use a hash algorithm suitable to your data size and it will have unique hashcodes.