HASHING

   Hashing finds the location of an element in a data structure without any comparisons.In contrast to the other comparison based searching techniques,like linear and binary search,hashing uses a mathematical function to determine the location of an elements.

   Hash Table: The hash table data structure is an array of some fixed size,containing the keys.A key is a value associated with each record.

    Hash Function: It accepts a value known as key as input and generates an output known as hash key. The hash function generates hash keys and stores elements corresponding to each hash key in the hash table. 

EXAMPLE

                 Hash(95)= 92 mod 10 =2

              

                Key value 92 is placed in location 2.

• Hashing is used for faster access of elements and record from the collection of tables and files.
• Hashing is applied where the array size is large and time taken for searching an element is more.

Collision:

• Two different records are indicated to be stored at the same position in the hash table.this situation is termed as collision.
• several collision resolution techniques are used to overcome this problem.These techniques are:

                        1.Separate chaining 

                        2.Open addressing

                        3.Rehashing

                        4. Extendible hashing                                                           

                        

BINARY SEARCH

• Binary search is simpler and faster than the linear search.
• For an given array of n elements, the basic idea of  binary search is that for a given elements,we 'probe' the middle element of an array.

                     

• We continue in either lower or upper segment of the array depending on the outcome of the probe until we reached the required element.

EXAMPLE:

        Binary search (A,20,0,6)⇨Target 20.

• Element 20 is in the position 6.

Efficiency:

• Best case:O(n)
• worst case:O(log2n)      

Advantages: 

• It requires lesser number of iterations.
• It is a lot faster  than linear search.

Disadvantages:

• Unlike linear search ,it requires the list to be sorted before search can be performed.
• In comparison to linear search, the binary search  technique may seem to be a little difficult to implement.