We've seen how to use maps. Now let's explore how to implement one.
They may seem mysterious, but as we create our own map we'll see one way that they can work, and understand more about the inherent performance tradeoffs.
Maps are incredibly useful. But they are also straightforward to implement!
Let's create our own simple
Map implementation, one step at a time.
We'll use an approach called a hash table, and wind up with something that is an interesting hybrid between an array and a linked list.
First, let's set up our
Map class and stub out the methods that we'll need to implement.
We'll also create a few helper inner classes that we will use along the way.
Before we continue, let's also examine what we're building visually to hopefully help us gain some intuition.
Second, we'll implement
It's hard to tell if the
Map is working yet, but we'll add a size method to help.
Next we'll implement
get and then be able to test out our
Finally we'll consider the performance of our map in several different dimensions.