Implementing MapsMethods in the Map<x> ClassAn Illustrative Mapping ApplicationThe PostalLookup ProgramImplementation Strategies for MapsThe Idea of HashingHash CodesThe Bucket Hashing StrategySimulating Bucket HashingAchieving O(1) PerformanceThe map.h InterfaceSlide 12Slide 13Slide 14Slide 15Slide 16Hash Table mappriv.h FileThe mapimpl.cpp ImplementationSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25The EndImplementing MapsEric RobertsCS 106BMay 6, 2009Methods in the Map<x> Classmap.size()Returns the number of key/value pairs in the map.map.isEmpty()Returns true if the map is empty. map.put(key, value) or map[key] = value;Makes an association between key and value, discarding any existing one.map.get(key) or map[key]Returns the most recent value associated with key.map.containsKey(key)Returns true if there is a value associated with key.map.remove(key)Removes key from the map along with its associated value, if any.map.clear()Removes all key/value pairs from the map.An Illustrative Mapping Application•Suppose that you want to write a program that displays the name of a state given its two-letter postal abbreviation.•This program is an ideal application for the Map class because what you need is a map between two-letter codes and state names. Each two-letter code uniquely identifies a particular state and therefore serves as a key for a Map; the state names are the corresponding values.•To implement this program in C++, you need to perform the following steps, which are illustrated on the following slide:Create a Map<string> containing all 50 key/value pairs.1.Read in the two-letter abbreviation to translate.2.Call get on the Map to find the state name.3.Print out the name of the state.4.The PostalLookup Program skip simulationint main() { Map<String> stateMap; InitStateMap(stateMap); while (true) { cout << "Enter two-letter state abbreviation: "; string code = GetLine(); if (code == "") break; if (stateMap.containsKey(code)) { cout << code << " is " << stateMap.get(code) << endl; } else { cout << code << " is not a known state abbreviation" << endl; } }}code stateMapEnter two-letter state abbreviation:PostalLookup HIHI is HawaiiEnter two-letter state abbreviation: WIWI is WisconsinEnter two-letter state abbreviation: VEVE is not a known state abbreviationEnter two-letter state abbreviation:AL=AlabamaAK=AlaskaAZ=ArizonaFL=FloridaGA=GeorgiaHI=HawaiiWI=WisconsinWY=Wyoming. . .. . .HIWIVEvoid InitStateMap(Map<String> & map) { map.put("AL", "Alabama"); map.put("AK", "Alaska"); map.put("AZ", "Arizona"); map.put("FL", "Florida"); map.put("GA", "Georgia"); map.put("HI", "Hawaii"); map.put("WI", "Wisconsin"); map.put("WY", "Wyoming");}map. . .. . .int main() { Map<String> stateMap; InitStateMap(stateMap); while (true) { cout << "Enter two-letter state abbreviation: "; string code = GetLine(); if (code == "") break; if (stateMap.containsKey(code)) { cout << code << " is " << stateMap.get(code) << endl; } else { cout << code << " is not a known state abbreviation" << endl; } }}stateMapImplementation Strategies for MapsThere are several strategies you might choose to implement the map operations get and put. Those strategies include:Linear search in parallel arrays. Keep the two-character codes in one array and the state names in a second, making sure that the index numbers of the code and its corresponding state name always match. Such structures are called parallel arrays. You can use linear search to find the two-letter code and then take the state name from that position in the other array. This strategy takes O(N) time. 1.Binary search in parallel arrays. If you keep the arrays sorted by the two-character code, you can use binary search to find the key. Using this strategy improves the performance to O(log N). 2.Table lookup in a grid. In this specific example, you could store the state names in a 26 x 26 Grid<string> in which the first and second indices correspond to the two letters in the code. Because you can now find any code in a single step, this strategy is O(1), although this performance comes at a cost in memory space.3.The Idea of Hashing•The third strategy on the preceding slide shows that one can make the get and put operations run very quickly, even to the point that the cost of finding a key is independent of the number of keys in the table. This O(1) performance is possible only if you know where to look for a particular key.•To get a sense of how you might achieve this goal in practice, it helps to think about how you find a word in a dictionary. You certainly don’t start at the beginning at look at every word, but you probably don’t use binary search either. Most dictionaries have thumb tabs that indicate where each letter appear. Words starting with A are in the A section, and so on.•The Map class uses a strategy called hashing, which is conceptually similar to the thumb tabs in a dictionary. The critical idea is that you can improve performance enormously if you use the key to figure out where to look.Hash Codes•To make it possible for the Map class to know where to look for a particular key string, the implementation defines a hash method that returns an integer associated with each key. As you will see in a subsequent slide, this hash code value tells the Map implementation where it should look for a particular key, dramatically reducing the search time.•In general, clients of the Map class have no reason to know the actual value of the integer returned as a hash code for a key. The important things to remember are:Every string has a hash code, even if you don’t know what it is.1.The hash code for any particular string is always the same.2.If two strings are equal (i.e., they contain the same characters), they have the same hash code. 3.The Bucket Hashing Strategy•One common strategy for implementing a map is to use the hash code for each key to select an index into an array that will contain all the keys with that hash code. Each element of that array is conventionally called a bucket.•In practice, the array of buckets is smaller than the number of hash codes, making it necessary to convert the