Chapter 27.2, Problem 27.2.1CP

Explanation of Solution

Hash Function:

• Consider the case of searching an array for a given value. If the array is not sorted, then the process takes more time to search an element.
• Whereas, if the array is sorted, by using binary search the worst case runtime complexity can be reduced to $\text{O}\left(\text{log n}\right)$ .
• The searching process can be made even faster if the index of the value is known.
• Therefore, the function that tells the index value has to be used to reduce the search to just one probe, giving a constant runtime $\text{O}\left(\text{1}\right)$ .
• Such a function is called as a hash function.
• A hash function is a function that generates an address in the table when a key is given.

Example:

Consider an example of a book call number. Each book in the library will be having a unique call number, which tells where the book is placed in the library