Getting acquainted with hash tables

Suppose we want to store a collection of numbers, for instance, a phone number, and let's say we have approximately 1,000,000 numbers. In previous chapters, we also discussed several data structures, and here we can consider using one of them. We can use an array or a list, but we have to provide a million slots of data in the array. If we need to add some phone numbers again, we have to resize the array. Also, the operation of searching will be costly, since we have to use a linear search algorithm with time complexity O(N), where the time consumption will increase if we add data to the list. Indeed, we can use a binary search algorithm with O(log N) time complexity if we manage to sort the elements of the list containing the bunch of phone numbers; however, the insert operation will be costly, since we have to maintain the sorted list.

Another data structure we can choose is the balanced binary search tree. It can give us a moderate time complexity, since...