Hash Table

What is Hashing:  Hashing is a technique that can be used to find elements in a data structure quickly without making a linear search through elements. Hashing give rise to hash table that can be used o implement sets and maps.A hash function is a function that computes an integer value, the hash code from an object. The Object class has a hashCode method that other classes need to redefine. The call computes hashCode of object x.
       int h = x.hashCode();

The two or more distinct objects can have same hash code this is what we call Collision. The String class defines a hash function for strings that does a good job of producing different integer values for different strings.A hash code is used as an  array index into a hash table. In its implementation we can say you should make an array and insert each object at the location of its hash code.HashCodes  often make search simpler and easier.Its all about computing hashCode and check whether array position with that hash code is already there or not.So we can say that it saves times in search of complete array.

Drawback of HashCode Approach: It is not possible to allocate an array that is large enough to hold all possible integer index positions.So in this case we need an array of some reasonable size and then reduce hashCode to fall inside the array.

It can also be possible that two objects have same hashCode,to store multiple objects in the same array position , use short node sequences for all elements with same hash code. These node sequences ar known as bucket. Hope you are not confused till here .

In more brief i can say A hash table can be implemented as an array of buckets - sequences of node that hold elements with same hash code.

 Check yourself - 1) Write the algorithm for finding an object x in a hash table.

Few points to learn here for hash table are:
1) If there are no or only a few collisions , then adding , locating and removing hash table elements takes constant or O(1) time.
2) For reducing the chances of collisions , you should make hash table somewhat larger than the number of elements that you expect to insert.
3) According to some researchers hash table size should be chosen to be a prime number to minimize the number of  collisions.
4) As long as there are few collisions, an element can also be added or removed in constant or O(1) time