Kotlin
Java

Implementing a Map
Kotlin

Created By: Geoffrey Challen
/ Updated: 2022-05-23

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.

Implementing a Map

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.

Map Class

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.

Show how to set up the Map implementation with an internal array and inner class for linking.

Before we continue, let's also examine what we're building visually to hopefully help us gain some intuition.

Show how a hash table works like a combination of an array and a list. This explanation should be language agnostic!

set

Second, we'll implement set. It's hard to tell if the Map is working yet, but we'll add a size method to help.

Implement set and a size method for testing.

get

Next we'll implement get and then be able to test out our Map.

Implement get and finish.

Performance Analysis

Finally we'll consider the performance of our map in several different dimensions.

Discuss the performance of the map and the tradeoff between space (array size) and time (linked list walk).

Cool Down Debugging Challenge

I bet you were wondering: Did we miss the debugging challenge? Nope!

More Practice

Need more practice? Head over to the practice page.