Next up are maps. Conceptually, you can think of Maps kind of like a dictionary, not to be confused with a Dictionary ADT (Abstract Data Type). With a dictionary, you have the word you want to lookup, the ‘key’, and you have the definition, the ‘value’. Unlike a dictionary, in a Map, each key, or word, has to be unique. You have a word, and you go to the starting letter and then meticulously search through that letter for your word. A map data structure works exactly the same way.
Like a dictionary, a map is divided into sections, buckets. Whatever you add to a map, it is inserted into a bucket. Which bucket? Well, that’s what the hash is for. Every key is passed through hashing method, or function. IE. A mathematical operation which returns a value. This value is then used to enter the key-value pair into the corresponding bucket.
Sounds neat, right? Well, sorta. First, maps are really good for looking stuff up. Since they use hashes, looking for a key is pretty fast. Theoretically, it could take O(n) but usually not. How, you ask? Imagine if all the objects you want to enter wind up in the same bucket. Then you would have to search thru that bucket in a linear fashion, which we know takes O(n).
Use the example in the image as a reference. There are 6 objects. When you create a map and start adding elements, each element’s key is hashed. This hash is then used to determine which bucket to enter the object into. Thus, insertion is O(1) since, once we have the hash, it’s a simple matter of assigning it to a bucket.
Searching is just as simple. When searching for a key, that same hashing function is used and the appropriate bucket where the object is.
This is all fine and dandy. Maps seem like the second coming of code. But what are the drawbacks? First, if you have less objects than buckets, you have wasted space. Second, if there are more objects than buckets, when hashing, it is possible, and allowed, to have separate objects that return the same hash code. Collision handling is for another post.
