Before introducing hashing, let us review the map, which is a data structure that is implemented using hashing. Recall that a map is a container object that stores entries. Each entry contains two parts: a key and a value. The key also called a search key, is used to search for the corresponding value. For example, a dictionary can be stored in a map, in which the words are the keys and the definitions of the words are the values.

The Java Collections Framework defines the java.util.Map interface for modeling maps. Three concrete implementations are java.util.HashMap, java.util.LinkedHashMap, and java.util.TreeMap. java.util.HashMap is implemented using hashing, java. util.LinkedHashMap using LinkedList, and java.util.TreeMap using red–black trees.  You will learn the concept of hashing and use it to implement a hash map in this chapter.

If you know the index of an element in the array, you can retrieve the element using the index in O(1) time. So does that mean we can store the values in an array and use the key as the index to find the value? The answer is yes—if you can map a key to an index. The array that stores the values is called a hash table. The function that maps a key to an index in the hash table is called a hash function. a hash function obtains an index from a key and uses the index to retrieve the value for the key. Hashing is a technique that retrieves the value using the index obtained from the key without performing a search.

How do you design a hash function that produces an index from a key? Ideally, we would like to design a function that maps each search key to a different index in the hash table. Such a function is called a perfect hash function. However, it is difficult to find a perfect hash function. When two or more keys are mapped to the same hash value, we say a collision has occurred. Although there are ways to deal with collisions, which will be are discussed later in this chapter, it is better to avoid collisions in the first place. Thus, you should design a fast and easy-to-compute hash function that minimizes collisions.