1.9.3 Hash Functions and Maps

 A hash function takes data as its input, peforms a numeric operation on the data, and returns a n umberic value. This numeric value can then be used as an index into a table (typically an array) to quickly retrieve the data. Whereas searching for a data item through a list of size n can require up to O(n) compareisons, using a hash function for retrieving data from a table can be as good as O(1), depending on implementation details. Because of this performance, hash function are used extensively in operating systems.

On potential difficulty with hash functions is that two unique inputs can result in the same output value-that is, they can link to the same table location. We can accommodate this hash collision by hav ing a linked list at the table location that contains all of the items with the same hash value. Of course, the more collisions there are, the less efficient the hash functions is.

One use of hash function is to implement a hash map, which associates (or maps)[key:value] pairs using a hash function. Once the mapping is established, we can apply the ahsh function to the key to obtain the value from the hash map(Figure 1.2.1). For example, suppose that a use name is mapped to a password. Password authentication then processds as follows: a user enters which is then used to retrieve the password. The retrieved password is then compared with the password entered by the user for authentication.