As we journey down the lane of data structures, you may or may not have noticed a pattern for how we access data. Since the underlying data storage we have used have been arrays, we have had to rely heavily on using numeric type indexing to retrieve values. Even though in stacks and queues we were only interested items at the top or front, indirectly we were still using some sort of indexing to get those item values. Also when we did traversals in our data structure, it was based on indexing. While this has served us well, sometimes you want to put more meaning into how you retrieve values. Asking for items[0], doesn’t really give a clear definition of what is being asked for. In this and the next post, we will be talking about accessing data based on meaningful keys/names. Think of a real world dictionary for example. Every word in a dictionary has a meaning. You can think of a word as a key, and the meaning as a value. So in essence you are using one unique word to look up a meaning. A key mapped to a value ( key/value pairs). Notice that dictionaries do not have duplicate keys. If you need the meaning for a word, for e.g engineer, you will not find the key twice. You may however find multiple meanings under that key word. Lets think of another scenario where you might want to use a dictionary. What if you wanted a data structure where you could find a state name based on abbreviation? Like NY (key) for New York (value), or CA for California. We are not using an index here. We might access it like this instead state[“NY”]. We are using a unique identifier to refer to a particular state. This is when we use the dictionary data structure. Dictionaries are also referred to as maps, and may be the preferred word to use depending on the programming language. Dictionaries, associative arrays, maps, … they all mean the same thing! We will be referring to them as maps from now on.
We have another data structure that is similar to maps, called sets. A set is a collection of unique elements. The order doesn’t matter (thus unordered collection). You will sometimes hear the elements of a set being referred to as members. So if you ever need to create a collection of unique elements (where each member occurs only once), a set is the way to go. As you can see, sets are very important as the need to create such collections is something that comes up regularly when developing applications. One reason to use sets its due to limitations of arrays not being able to store unique items. You can have an array filled with same values. What if you didn’t want this? This is when you use sets. Sets store unique values of any type!
Javascript as a language is growing. And beginning ES2015 you will find implementations of Maps and Sets. So know when to use them. These data structures are however not native to ES5 versions of javascript and below. This should not prevent you from using such data structures however. You will learn how to create your own ES5 implementation so you can use them today. Since Maps and Sets exist in ES2015 and beyond, we will use the native implementation when we look at code samples instead of creating a new class. Lets write some code!
Dictionary / Map implementation
Since Ecmascript 6 and above has an implementation of a Map, lets take a look at some of its methods. Head over to MDN and look at some of these methods. Over on the left panel on the MDN site you will see some method names. These are methods that help you work with the map data structure. Lets define some of the ones we will be writing in this post.
get: Returns a value based on a key.
set: Adds a new item to our map/dictionary
has: Returns a boolean of whether a key exists
delete: Removes a value from the dictionary based on a key value.
clear: Removes all the items from the map/dictionary.
size: Returns the total number of items in the map/dictionary.
keys: Returns an array of all the keys that are found in the map/dictionary
values: Returns an array of all the values that are found in the map/dictionary
sort: Sorts the entire map alphabetically
There are other methods, like entries, forEach, etc on the MDN page that we will not be covering here. We will only focus on the main operations. Notice even that we will have a sort functionality for our map, where the Map definition on MDN doesn’t have one. This is the great thing about knowing how to implement your own data structures; you can always extend functionality when necessary.
The Map Class (ES5)
Lets write a our basic ES5 Map class
See the Pen pwqjYd by kofi (@scriptonian) on CodePen.
Notice anything different in this class? Every class we have created so far used an array as its underlying data storage. Not for a Map however! We are using an object this time. The javascript object is designed to work similar to a Map. JavaScript is designed on a simple object-based paradigm. An object is a collection of properties, and a property is an association between a name (or key) and a value. Sounds similar to a Map doesn’t it? That means that you could actually implement a Map using javascript objects, however creating your own Map class makes it more specific and focused than using an object which may have functionality you might not like. For example, if you use an object as a map, its keys are always converted to a string. You can read about this pitfall here. Lets take a little deeper into this
See the Pen Objects as Maps – Issues by kofi (@scriptonian) on CodePen.
Javascript developers are first exposed to Map through Objects. You want to have a data structure that has key/value pairs? Then use an Object is what we are told. However as you can see from the code above, keys are converted to strings when we use Objects as maps. So we don’t really have true map functionality. Hence the reason ES6 supports it natively. There are many reasons you want to use maps, but they come in especially handy when you to set key value pairs at run-time (dynamically). When all keys and values are of the same type you may want to use a Map. When keys and values are of different types, then perhaps an Object is best. Lets move on.
We want to create a Map data structure that makes it easier for working with key value pair collections of data. For example instead of write a for loop to perform some operation, having a method in our class implementation makes it run that for loop in the background (with a method by simply calling it), than having to write it over and over again.
Map operations
Now that we have our class shell completed, lets add the helper methods. The first thing we should do is write functions that enable end users of our Map to set and get items on our data structures.
get and set
Lets take a look at our get and set methods
See the Pen Map / Dictionary – get and set by kofi (@scriptonian) on CodePen.
In our Map definition, set adds a new item to the collection (the items object) by taking a key and value as function parameters. We write the key into the object and assign it a value. When we want to get a value for a key, we call the get method, which returns the value of the key you pass to it. Lets test our class by creating our own Russian translation dictionary / map.
See the Pen ES5 Map – Testing Get and Set by kofi (@scriptonian) on CodePen.
We create a collection of key/value pairs called russianwords. The key is the Russian word and the value is the meaning. We set four words in our map. To test our data structure we call the get method passing it the word we would like to translate. We ask to get “hi” in Russian (which is privyet). Pretty neat huh. Lets add more methods.
has and delete
What if you wanted to find out if a key exists in your collection? Perhaps you dont necessarily want the value of key, you simply want to see if it exists (based on that information, perform some action). The has operation returns true or false whether a key exists. Delete does exactly what the word means…it deletes an item in the collection, based on a key passed to it. Lets implement them
See the Pen ES5 Map – has & delete by kofi (@scriptonian) on CodePen.
The first is the has method. This function takes and key and returns a true or false whether the key exists in the items object. We use the hasOwnProperty method to do this check. We could have used the javascript in as well. The delete function first checks to see if the collection has the key, if it does it deletes it and returns true. If not returns false. We return a boolean here just in case the caller of the function would like to know if the operation was successful or now. Lets write the remaining helper methods.
clear, size, keys, values & sort
Lets complete our map class. We have 5 remaining helper methods. Lets implement and talk about what they are doing
See the Pen ES5 Map – clear, size, keys, values & sort by kofi (@scriptonian) on CodePen.
OK lets go over these methods in order of difficulty and see what each one is doing. Clear is super easy. When called we set the items object to empty. In the size method we use Object.keys to find all the keys within an object. To learn more about this or about objects in general, read my post on Javascript Objects. Since Object.keys returns and array-like object we are able to get the length property which represents the size. Next we have keys and values. Sometimes you may want to know every key or every value that you have in your collection. So we create these methods so they can return an array of what is needed. Since we are working with objects we use a for in loop to enumerate the object to return the values at the end of the function call. Sorting is a special one. Since we don’t have a native implementation for sorting object key/pair values in javascript, so we have to come up with a creative way of doing it. Arrays have sort functionality (we know that), so we can use that knowledge to our advantage. We create an array of keys using Object.keys (from the items object) and we sort that result instead. When we get the sorted keys, we can loop through that, and for each key find the associated value in the items array. I did not return the results in this method, but you can do that if you like (i highly suggest you do). I am only outputting the display to the console. Lets create an application that uses Maps as a data structure.
Solving problems with Maps
So now we know how to use maps. But how does that relate to the real world? Lets come up with a fictitious example. You are given two pieces of data separately. Lets just say they are arrays. The first array contains 10 phrases, and the other contains its meaning. It would be nice to have one Map that defines phrase and meaning instead of having them separate. Lets take a look at this sample code. You can find this example in the git repo (phrase-map.html).
See the Pen Javascript Phrase Map by kofi (@scriptonian) on CodePen.
Nothing fancy going on here. We get our words and meanings data from somewhere (backend database, external api, array etc). Then we create a phraseMap that will be used to store the words/meanings collection. Then we use an iterator to loop through the array. On each iteration we dynamically set the key/value pairs in the phraseBook Map. When we console log we see all our data now exists neatly in our Map. We also call sort to sort the data. Lets move on to sets!
Set implementation
Earlier on, i mentioned what a set is. Its an unordered collection of unique data. Just like the Map implementation, Set is also a part of the new Ecmascript standard. It was introduced in ES2015 and you can find its implementation here. You will see the implementation is very similar to maps (method names are identical). We will try to simulate the same for our ES5 implementation. Here again we will be using an object as the underlying data storage instead of an array. The reason why we do this for sets is because we want to take the advantage of a feature of objects which prevent duplication of keys.
Like the Map, here are some of the methods we will implement for our Set
add: Adds a new member to our set.
has: Returns a boolean of whether a member exists.
delete: Removes a member from the set.
clear: Removes all the members from the set.
size: Returns the total number of member in the set.
values: Returns an array of all the values that are found in the set.
other set operations
There are other set operations you need to be aware of. Remember in high school or college you learned about sets? Look at this link as a refresher. We had operations like these
union: This is take two sets and combining them
subset: whether a given set is part of another set
intersection: a set that contains members of two different sets.
difference: given two sets, return a new set with all the member that exist in the first set but do no exist in the other. For example difference of {7,8,9,10} and {9,10,11,12} is the set {7,8,11,12}.
These operations come in handy when working with multiple set collections and we want to perform actions based on the 2 sets you have. Lets implement our Set class.
The Set Class ( ES5 )
By now you should be getting a hang of writing classes in javascript. I am going to define the shell here with all the methods we will be implementing.
See the Pen ES5 Set Class – Shell by kofi (@scriptonian) on CodePen.
Nothing we haven’t seen before. I have defined all our methods here so we can see the big pictures. All that’s left is to write some code. We will do this in 2 parts. The first part will be the basic methods. The second would be the “other set operations” that we talked about.
add, has, delete, clear, size and values
Lets see how to implement these. They are very similar to that of a Map
See the Pen ES5 Set – add, has, delete, clear, size and values by kofi (@scriptonian) on CodePen.
Lets go over these methods. First we write a has function that simply checks to see if a member exists in our object. The add function uses this has method to first check if a member exists before adding the new member to the collection. It also returns true or false based on success/failure on the operation. Delete does the same. It uses the has method to see if a member exists. If it does, it deletes it and returns true. If not it returns false. The clear and size method remove all members and return the total number of members in the collection respectively. Finally we have the values methods. In it we create a temporary array and push the key properties of the object into it (then we return the array to the caller). That’s it. Lets complete our set.
union, subset, intersection & difference
Lets first take a look at the union method. A Union combines two sets to form a new set. Given an initial set (Set A for example), it takes in another set(Set B) as a parameter, then iterates Set B checking to see if its members exist in Set A. If it does, its discarded (since we only want unique items), if it doesn’t exist then its made part of the new set (Set C).
Lets translate this to code
See the Pen ES5 Set – union by kofi (@scriptonian) on CodePen.
Not to go too much into details, we create a unionSet to hold the combined unique members. Since we are combining two sets we create firstSetKeys and secondSetKeys variables to hold the members in those sets. Next we iterate both sets and pass only the unique members to our new unionSet and return it. Lets test our union function
See the Pen ES5 Set – union ( Testing Union ) by kofi (@scriptonian) on CodePen.
In our testing example, we created 2 sets (numbers and otherNumbers). Then we called numbers.union(otherNumbers) to add combine otherNumbers to numbers. Our final result is a union of the two sets. Lets move to the next method (subset).
A set is a subset of another set, if all of it members exists in other set. So here is how we are going to code our subset. Knowing all the members that exist in one set, we can see if these member exist in another set. If they are all true then its a subset. Even if one comes back and false, its not a subset. Lets code this.
See the Pen ES5 Set – subset by kofi (@scriptonian) on CodePen.
Simple right? Lets say SetA = {2,4,6} and SetB= {2,4,6,8}. SetA is a subset of SetB, because all members on SetA exists in SetB. In the code, we take all the members in the current (SetA) and second set(SetB). Then we use the every array helper class. This method checks to see if every member of SetA exists in our primary set(SetB). They must all be true for this to work. Even if one false is return, then whole thing fails. Let us test our subset function
See the Pen ES5 Set – subset ( Testing ) by kofi (@scriptonian) on CodePen.
I used the examples from earlier. We create 3 sets in our test (setA, odd and setB). We add members in all sets and then put our subset method to a test. As you can tell, things are working as expected. Try create your own sets and check to see if they are subsets of other sets Lets move on to intersection.
I remember particularly loving the mathematical idea of intersection in high school. Given two sets, their intersection are elements that are common between the two. Given SetC ={7,8,9} and SetD={9,10,11}. The intersection between the two sets is {9}. Because 9 is common between both of them. Lets write this function and test it out.
See the Pen ES5 Set – intersection by kofi (@scriptonian) on CodePen.
Thing are beginning to look pretty similar by now. Since we are working with two sets of data, we get their values (which is an array representing all the members). We loop through the first set and for each key we check to see if it exists in the other set. If it does, we add it to a brand new set and return that. Here is our test code
See the Pen ES5 Set – intersection ( Testing ) by kofi (@scriptonian) on CodePen.
In our test, we use the setC and setD examples from earlier. Our result is [“9”] because that is the element that is common between the two sets. Lets wrap up our set class by writing the last method: difference.
Difference is also quite simple. Given two sets, we return a new set consisting of items in the first, that DON’T exist in the second. Given setX={5,6,7,8} and setY={6,7,9}, the difference would be setZ={5,8}. 5 and 8 are the only members that are in setX that are not in setY. Its a tricky one sometimes, so find way of understand what difference means.
Let code our difference function.
See the Pen ES5 Set – difference by kofi (@scriptonian) on CodePen.
And our test code for difference
See the Pen ES5 Set – difference ( Testing ) by kofi (@scriptonian) on CodePen.
The difference method is very similar to intersection. The only difference is when we run our forEach we check to see if indexOf is equal to -1 (non existence) before adding to our new set. And there you have it, you can now implement a Set class in ES5. Let get into ES2015 and beyond.
Maps and Sets in ES2015
You have now learned how to implement Maps and Sets that will work on just about any browser. Since most browsers understand ES5 this should not be an issue using them today. Wouldn’t it be nice to be able to NOT import a javascript file into your project just to have access to some of the features we have talked about? Well, the javascript language has this inbuilt beginning ES2015. The only problem with this is that not all browsers support ES2015 features. This can be an issue. These days we have things called transpilers that take ES2015 and convert that to ES5 so that it can be ran in browsers we have today. But using transpilers can be a daunting thing to implement (even though i advise you learn them, babel or traceur). If you are already writing ES2015 code, then all this is baked into the language, and you should be using them. You shouldn’t be writing functions that have the same behaviors as Sets, for e.g, when the Set data structure is already available to you. But most developers don’t even know this. This is why its great to understand data structures. In this section we will talk about some of the difference between what we have been coding, and the Map and Set class you find in ES2015. Since ES2015 has a lot of new features, there are lots of things available that make working with Maps and Sets even more easier.
Starting off with maps, one of the first things you will notice when working with ES2015 and above is that calling the values and keys methods on the map does not return an array. It returns an iterator. Even though the idea of iterators can be used to get the data you need, you will have to learn how to use them in ES2015 and above to be able to access them. In ES5 a simple array does the job for us. Another thing we get from using for..of to iterate maps. Lets take a look at an example
See the Pen ES2015 – Map iteration by kofi (@scriptonian) on CodePen.
We used the for..of to iterate our map. In the iteration we use template literals to output the key/value pairs. Lets take a look at Sets. We will start this off with an example.
See the Pen ES2015 – Set iteration by kofi (@scriptonian) on CodePen.
We see Sets looks just like Maps. We can use the add operator to add new members when using ES2015 and above. We are also able to iterate through sets using for..of. Another interesting thing we can do when working with sets is using object destructuring to get values out of the set. We also see that calling values returns and SetIterator and not an array. Apart from that you would use Maps and Sets just about the same way you would use them in our ES5 implementation. Though i must say ES2015 and above gives you a lot more flexibility, since there are a lot of additions to the language. You are able to compose your maps and sets in more elegant ways.
WeakMap and WeakSets
Now in ES2015 and above, there is an idea of WeakMaps and WeakSets. These are derived from the Maps and Sets we have already looked at already(with subtle differences). When you create a WeakMap or a WeakSet (which you do like a regular Map or Set data structure), you can only pass an object as a key to the constructor. Using a primitive type like a string, boolean, etc will result in an error.
So why only an object you might wonder. What makes using only objects as keys so special that we have WeakMap and a WeakSet data structures? Here is why: The Weak in WeakMap or WeakSet means it holds a weak reference to the members or elements in the map or set (member objects). This makes it very memory efficient! It allows objects to be garbage collected when necessary (because objects are reference types). When objects (keys) are no longer being used or referenced, they can be discarded from memory.
Another thing you need to know about WeakMap and WeakSet is that they are not enumerable. This means that you cannot loop through the entries. The reason for this is due to the unpredictability. Since there are object references which can be removed from the application to improve performance at anytime (garbage collection), it might not be a good idea after all. For this reason you cannot enumerate over these “Weak” data structures. You cannot also get the size (because things keep changing dynamically). You can however get key values by using the get method. You can also use the has and delete methods. lets take a look at some samples.
See the Pen WeakMap and WeakSet – Examples by kofi (@scriptonian) on CodePen.
Ok! This brings us to the end of our Map (which is sometimes referred to as Dictionaries in Javascript) and Set Data Structure. We looked at how to implement them in ES5 and well as using them ES2015 and above. I hope you have enjoyed this post as much as i enjoyed writing it. Do let me know if anything is missing and i will do my best to fill in the void. Thanks for reading. Feel free to reach out on twitter as well ( @scriptonian ) if you have any questions.