Kotlinlearncs.online LogoJava

Implementing a Map

val map = mutableMapOf<String, String>()
map["you"] = "are not alone"
println(map["you"])
println(map["am I alone?"])
map["am I alone?"] = "Nope."
println(map["am I alone?"])

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
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
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.

// Map Implementation Part 1

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

set
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.

// Map Implementation Part 2

get
get

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

// Map Implementation Part 3

Performance Analysis
Performance Analysis

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

// Map Implementation Part 4

Cool Down Debugging Challenge
Cool Down Debugging Challenge

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

Create a method fun partition(value: IntArray?) that returns the input array partitioned using the first array value as the pivot. All values smaller than the pivot should precede it in the array, and all values larger than or equal to the pivot should follow it. Your method should return the index of the pivot value. If the array is null or empty you should return -1.

More Practice

Need more practice? Head over to the practice page.