let us assume that the same company uses five-digit emp_id as the primary key in this casekey values will range from to if we want to use the same technique as abovewe need an array of size , of which only elements will be used this is illustrated in fig key array of employeesrecords key employee record with emp_id [ key employee record with emp_id [nkey [ employee record with emp_id key [ employee record with emp_id figure records of employees with five-digit emp_id it is impractical to waste so much storage space just to ensure that each employee' record is in unique and predictable location whether we use two-digit primary key (emp_idor five-digit keythere are just employees in the company thuswe will be using only locations in the array thereforein order to keep the array size down to the size that we will actually be using ( elements)another good option is to use just the last two digits of the key to identify each employee for examplethe employee with emp_id will be stored in the element of the array with index similarlythe employee with emp_id will have his record stored in the array at the th location in the second solutionthe elements are not stored according to the value of the key so in this casewe need way to convert five-digit key number to two-digit array index we need function which will do the transformation in this casewe will use the term hash table for an array and the function that will carry out the transformation will be called hash function hash tables hash table is data structure in which keys are mapped to array positions by hash function in the example discussed here we will use hash function that extracts the last two digits of the key thereforewe map the keys to array locations or array indices value stored in hash table can be searched in ( time by using hash function which generates an address from the key (by producing the index of the array where the value is storedfigure shows direct correspondence between the keys and the indices of the array this concept is useful when the total universe of keys is small and when most of the keys are actually used from the whole set of keys this is equivalent to our first examplewhere there are keys for employees howeverwhen the set of keys that are actually used is smaller than the universe of keys ( ) hash table consumes less storage space the storage requirement for hash table is ( )where is the number of keys actually used in hash tablean element with key is stored at index (kand not it means hash function is used to calculate the index at which the element with key will be stored this process of mapping the keys to appropriate locations (or indicesin hash table is called hashing figure shows hash table in which each key from the set is mapped to locations generated by using hash function note that keys and point to the same memory location this is known as collision that iswhen two or more keys map to the same memory locationa collision