Data Structures and Algorithms Using Python

In the previous chapter we have discussed three different searching techniques. Linear search works on both ordered and unordered data but time complexity is O(n). Binary search works on only ordered data but time complexity is O(log2n) which is much faster than linear search. Interpolation search generally works faster than binary search and its time complexity is O(log2(log2n)) when elements are evenly distributed. But there is another application where, irrespective of the size of the array/list, a search operation can be performed with time complexity O(1), i.e. in constant time. This is possible due to hashing. In this chapter we will discuss this.

14.1 Definitions and Concept

Hashing is a procedure by which we can store or retrieve data in constant time, i.e. with time complexity O(1). To achieve O(1) time complexity we may follow a simple process. Suppose we have to store the data of students whose roll numbers range from 1 to 60. For this purpose we may take an array/list and store the data of each student at the corresponding index position which matches with the roll number. In this situation, to access a student, if we know his/her roll number, we can directly access his/her data. For example, if we want to read the data of the student whose roll number is 27, we may directly access the 27th index position of the array/list. But the problem is that in real life key values are not always as simple. You may find that in a certain university someone's roll number may be 21152122027. This does not imply that it is a sequential number, nor that this number of students are admitted in a year in that university. It may be a nomenclature of a key value where the first two digits may denote the year of registration, the next three digits are the college code, the next two digits may indicate stream, and so on. This is true for not only roll numbers but also any other key value. Thus it is clear that the number of digits does not indicate the total number of elements. In the above example hardly 10,000 or 20,000 students may take admission in that university in a year.