hashing and collision learning objective in this we will discuss another data structure known as hash table we will see what hash table is and why do we prefer hash tables over simple arrays we will also discuss hash functionscollisionsand the techniques to resolve collisions introduction in we discussed two search algorithmslinear search and binary search linear search has running time proportional to ( )while binary search takes time proportional to (log )where is the number of elements in the array binary search and binary search trees are efficient algorithms to search for an element but what if we want to perform the search operation in time proportional to ( )in other wordsis there way to search an array in constant timeirrespective of its sizethere are two solutions to this problem let us take an example to explain the first key array of employeesrecords solution in small company of employeeskey [ employee record with emp_id each employee is assigned an emp_id in the key [ employee record with emp_id range - to store the records in an arraykey [ employee record with emp_id each employee' emp_id acts as an index into the array where the employee' record will be stored as shown in fig in this casewe can directly access the key [ employee record with emp_id record of any employeeonce we know his key [ employee record with emp_id emp_idbecause the array index is the same as the emp_id number but practicallythis implementation is hardly feasible figure records of employees