Why we use Hash Code in HashTable instead of an Index?

Question

• How that integer hash is generated by the GetHashCode() function? Is it a random value which is not unique?

• In string, it is overridden to make sure that there exists only one hash code for a particular string. How to do that?

• How searching for specific key in a hash table is speeded up using hash code?

• What are the advantages of using hash code over using an index directly in the collection (like in arrays)?

Can someone help?

Answer 1

Answering each one of your questions directly:

How that integer hash is generated by the GetHashCode() function? Is it a random value which is not unique?

An integer hash is generated by whatever method is appropriate for the object. The generation method is not random but must follow consistent rules, ensuring that a hash generated for one particular object will equal the hash generated for an equivalent object. As an example, a hash function for an integer would be to simply return that integer.

In string, it is overridden to make sure that there exists only one hash code for a particular string. How to do that?

There are many ways this can be done. Here's an example I'm thinking of on the spot:

int hash = 0;
for(int i = 0; i < theString.Length; ++i)
{
    hash ^= theString[i];
}

This is a valid hash algorithm, because the same sequence of characters will always produce the same hash number. It's not a good hash algorithm (an extreme understatement), because many strings will produce the same hash. A valid hash algorithm doesn't have to guarantee uniqueness. A good hash algorithm will make a chance of two differing objects producing the same number extremely unlikely.

How searching for specific key in a hash table is speeded up using hash code? What are the advantages of using hash code over using an index directly in the collection (like in arrays)?

A hash code is typically used in hash tables. A hash table is an array, but each entry in the array is a "bucket" of items, not just one item. If you have an object and you want to know which bucket it belongs in, calculate

 hash_value MOD hash_table_size. 

Then you simply have to compare the object with every item in the bucket. So a hash table lookup will most likely have a search time of O(1), as opposed to O(log(N)) for a sorted list or O(N) for an unsorted list.