#### Generics : `57`

#### Implementing a Map : `56`

#### Hashing : `55`

#### Binary Search : `54`

#### Quicksort : `53`

#### Merge Sort : `52`

#### Sorting Algorithms : `51`

#### Practice with Recursion : `50`

#### Trees and Recursion : `49`

#### Trees : `48`

#### Recursion : `47`

#### Lists Review and Performance : `46`

#### Linked Lists : `45`

#### Algorithms and Lists : `44`

#### Lambda Expressions : `43`

#### Anonymous Classes : `42`

#### Practice with Interfaces : `41`

#### Implementing Interfaces : `40`

#### Using Interfaces : `39`

#### Working with Exceptions : `38`

#### Throwing Exceptions : `37`

#### Catching Exceptions : `36`

#### References and Polymorphism : `35`

#### References : `34`

#### Data Modeling 2 : `33`

#### Equality and Object Copying : `32`

#### Polymorphism : `31`

#### Inheritance : `30`

#### Data Modeling 1 : `29`

#### Static : `28`

#### Encapsulation : `27`

#### Constructors : `26`

#### Objects, Continued : `25`

#### Introduction to Objects : `24`

#### Compilation and Type Inference : `23`

#### Practice with Collections : `22`

#### Maps and Sets : `21`

#### Lists and Type Parameters : `20`

#### Imports and Libraries : `19`

#### Multidimensional Arrays : `18`

#### Practice with Strings : `17`

#### null : `16`

#### Algorithms and Strings : `15`

#### Strings : `14`

#### Functions and Algorithms : `13`

#### Practice with Functions : `12`

#### More About Functions : `11`

#### Errors and Debugging : `10`

#### Functions : `9`

#### Practice with Loops and Algorithms : `8`

#### Algorithms I : `7`

#### Loops : `6`

#### Arrays : `5`

#### Compound Conditionals : `4`

#### Conditional Expressions and Statements : `3`

#### Operations on Variables : `2`

#### Variables and Types : `1`

#### Hello, world! : `0`

# Implementing a Map

import java.util.Map;

import java.util.HashMap;

Map<String, String> map = new HashMap<>();

map.put("you", "are not alone");

System.out.println(map.get("you"));

System.out.println(map.get("am I alone?"));

map.put("am I alone?", "Nope.");

System.out.println(map.get("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.

Interactive Walkthrough

Click on an icon below to start!

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

Second, we’ll implement `put`

.
It’s hard to tell if the `Map`

is working yet, but we’ll add a size method to help.

Interactive Walkthrough

Click on an icon below to start!

Next we’ll implement `get`

and then be able to test out our `Map`

.

Interactive Walkthrough

Click on an icon below to start!

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

Interactive Walkthrough

Click on an icon below to start!

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

Create a public, non-final class named `Partitioner`

. Implement a public static method
`int partition(int[] values)`

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.