Implementing a Map : 04/26/2024
map-reduce-filter : 04/25/2024
Generics : 04/24/2024
Hashing : 04/23/2024
Binary Search : 04/22/2024
MP3: Course Ratings : 04/19/2024
Quicksort : 04/18/2024
Merge Sort : 04/17/2024
Sorting Algorithms : 04/16/2024
MP Debugging Part 1 : 04/15/2024
MP2: Course Activity : 04/12/2024
Practice with Recursion : 04/11/2024
MP Debugging Part 0 : 04/10/2024
MP2: API Client : 04/09/2024
MP2: API Server : 04/08/2024
Trees and Recursion : 04/05/2024
Trees : 04/04/2024
Recursion : 04/03/2024
MP1: Filtering and Search : 04/02/2024
MP1: Loading and Sorting : 04/01/2024
Lists Review and Performance : 03/29/2024
Linked Lists : 03/28/2024
Algorithms and Lists : 03/27/2024
Continuing MP0 : 03/26/2024
Getting Started with MP0 : 03/25/2024
Lambda Expressions : 03/22/2024
Anonymous Classes : 03/21/2024
Practice with Interfaces : 03/20/2024
Implementing Interfaces : 03/19/2024
Using Interfaces : 03/18/2024
Working with Exceptions : 03/08/2024
Throwing Exceptions : 03/07/2024
Catching Exceptions : 03/06/2024
References and Polymorphism : 03/05/2024
References : 03/04/2024
Data Modeling 2 : 03/01/2024
Equality and Object Copying : 02/29/2024
Polymorphism : 02/28/2024
Inheritance : 02/27/2024
Data Modeling 1 : 02/26/2024
Companion Objects : 02/23/2024
Encapsulation : 02/22/2024
Constructors : 02/21/2024
Objects, Continued : 02/20/2024
Introduction to Objects : 02/19/2024
Compilation and Immutability : 02/16/2024
Practice with Collections : 02/15/2024
Maps and Sets : 02/14/2024
Lists and Type Parameters : 02/13/2024
Imports and Libraries : 02/12/2024
Multidimensional Arrays : 02/09/2024
Practice with Strings : 02/08/2024
null : 02/07/2024
Algorithms and Strings : 02/06/2024
Strings : 02/05/2024
Functions and Algorithms : 02/02/2024
Practice with Functions : 02/01/2024
More About Functions : 01/31/2024
Errors and Debugging : 01/30/2024
Functions : 01/29/2024
Practice with Loops and Algorithms : 01/26/2024
Algorithms : 01/25/2024
Loops : 01/24/2024
Arrays : 01/23/2024
Compound Conditionals : 01/22/2024
Conditional Expressions and Statements : 01/19/2024
Operations on Variables : 01/18/2024
Variables and Types : 01/17/2024
Welcome to CS 124 : 01/16/2024
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.
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 set
.
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 Map
.
Finally we’ll consider the performance of our map in several different dimensions.
I bet you were wondering: Did we miss the debugging challenge?
Nope!
More Practice
Need more practice? Head over to the practice page.