Maps: Pairing Unique Keys With Their Values, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.1 Free with a free account

Maps: Pairing Unique Keys With Their Values

Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.1 · lesson 56 of 878 min · free with a free account

← Sorting With Priority Queues: Heap SortNext lesson: Hash Functions: Spreading Keys Evenly Across Slots →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Map rules, Java Map methods and why list-based maps are slow.

  • State the rules of a map: unique keys, repeatable values and lookup by key
  • Predict the return values of put, get, getOrDefault, containsKey and remove
  • Analyze why a list-based map costs order n for every operation
  • Compare sorted lists and direct-index arrays as alternatives to hashing

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,169 words). Read along, or search it.

Opening Question

Lookups by Identifier

Much of everyday computing is a lookup. Given a product code, what's in stock? Given a username, which profile belongs to it? Given a word, how many times has it appeared? Given a student ID, what's the record? Each time, you hold an identifier and want the information that goes with it. You don't care where in some list it happens to sit.

Definition

Three Rules of a Map

A structure built for this job is a map. It holds entries, and each entry pairs a key with a value. Three rules define it. Keys are unique: putting an existing key replaces the old value. Values may repeat: here, pen and tape both have twelve. And you look things up by key, never by value. The core operations are put, get, remove and contains key, with size and is empty as helpers.

Java Example

What Put, Get and Remove Return

Java offers the map as the Map interface, implemented by HashMap, LinkedHashMap and TreeMap. Two keys are the same when equals says so. Watch what put returns. For a new key, it returns null. For an existing key, it returns the old value it just replaced: twelve. Get returns fifteen for pen, and null for the missing cap. Get or default lets you name a replacement answer instead, here zero. Contains key answers true or false. Remove returns the value it deleted, zero, and a second remove returns null. One entry is left.

Common Trap

Null Values Versus Missing Keys

There's one trap. A HashMap may hold null as a value. After putting x with null, get x and get y both return null. Yet contains key says true for x, and false for y. Whenever null could be a real value, ask contains key to tell missing from present but empty.

Quick Check

Tracing Puts, Removes and Gets

Quick check. An empty HashMap gets put a one, put b two, put a three, then remove a, get a, get or default a nine, and size. The program prints every result on one line. What does it print? Pause and predict. It prints null, null, one, three, null, nine, one. The first two puts add new keys, so they return null. The third put replaces a's value and returns the old one, one. Remove a returns three, so get a then finds nothing, and get or default gives nine. Only b is left, so the size is one. The second option forgets that put returns the replaced value, and the third treats put as returning the new one.

Application

Counting Words in a Map

A map makes word counting short. For each word, get or default returns zero the first time it's seen, so put stores one. A linked hash map keeps the order of first appearance, so the counts print as to two, be two, or one, not one.

Simple Design

A Map Stored as a List

How does a map find the entry for a key quickly? To see why that's hard, here's the plainest possible map: its entries sit in a list. Each entry is a small record holding a key and a value. Every operation starts with the same helper, find, which walks the list from the front until it meets the key. Put replaces the entry if the key exists, and adds one otherwise. Get, contains key and remove all lean on find too. And remove shifts the later entries left. This version also counts every key comparison, so we can measure it.

Cost Analysis

Every Operation Is Order n

Start with four entries: pen, ink, pad and tape. Getting tape takes four checks, because it's fourth. Getting the absent cap also takes four: every entry was checked. Putting cap takes four too. Adding at the end is cheap, but keys are unique, so the map must first check that cap isn't already there. Putting pen takes one check, since pen is first. Removing ink takes two, and then the later entries shift left. As the map grows, the pattern is exact. An absent key costs n checks. A present key costs n plus one, over two, on average, and n at worst. So every operation on a list-based map is order n. Doubling the entries doubles the work.

Measured Results

List Map Versus HashMap Timings

In time, measured on one machine for a thousand lookups: the list-based map took about ten times longer for every tenfold increase in size. It climbed from a hundred fifty-five microseconds at a hundred entries to about a fifth of a second at a hundred thousand. Java's HashMap barely changed: ninety-nine microseconds at a hundred thousand entries, over two thousand times faster. Something in its design avoids checking the entries one by one.

Quick Check

Looking Up an Absent Key

Quick check. A list-based map holds fifty thousand entries. About how many key checks does a lookup need, for a key that isn't in the map? Pause, and decide. Fifty thousand. The search must check every entry before it can give up. About twenty-five thousand is the average for a key that is present. And about sixteen is what binary search on a sorted list would need, which this map can't do.

Rescue Attempts

Sorted Lists and Direct Indexing

Can the list be rescued? Attempt one: keep it sorted by key, and use binary search, which halves the range at every step. Measured on sorted arrays, a search took nine comparisons on average among a thousand keys, and nineteen among a million. A huge improvement for get. But the price moves to put. A new key needs a gap at its position: in a sorted list of a thousand, an insertion moved about five hundred entries on average. And the keys must be of a kind that can be put in order. Attempt two: use the key as an array index. Key three goes in slot three, and every operation is one step. But the array needs a slot for every possible key. Nine-digit student IDs would need a billion slots, about four gigabytes, almost all empty. And words have no slot number at all.

Wish List

The Case for Hashing

Side by side: the unsorted list is order n for everything. The sorted list gets order log n lookups, but order n puts and removes. The array indexed by the key is one step for everything, but needs a slot for every possible key. So the wish list is clear: the one-step speed of an array index, for any kind of key, using space in proportion to the entries actually stored. That idea is called hashing. Hashing computes a slot number straight from the key itself.

Key Takeaways

Unique Keys and Costly Lists

To sum up. A map stores entries, each pairing a unique key with a value. Putting an existing key replaces its value. In Java, put returns the old value, get returns null for a missing key, and contains key tells missing from a stored null. A list-based map is order n for every operation, even adding a new key, because uniqueness must be checked. A sorted list speeds up get but slows put. An array index is fast, but needs a slot for every possible key.

Think About It

Skipping the Uniqueness Check

Something to think about. Suppose a program promises never to add the same key twice, so put could simply add at the end. How fast would put become? What would get still cost? And what risk would the program be taking?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Maps: Pairing Unique Keys With Their Values

What is a map data structure?
A map stores entries, each pairing a unique key with a value, and looks values up by key. Putting an existing key replaces its old value, while different keys may share the same value. The core operations are put, get, remove and containsKey, plus size and isEmpty. In Java, Map is an interface implemented by classes such as HashMap, LinkedHashMap and TreeMap.
What does put return in a Java HashMap?
put returns the value previously stored for the key, or null if the key was new. For example, after map.put("a", 1), calling map.put("a", 3) returns 1 and stores 3. In the same way, remove returns the value it deleted, and get returns null for a missing key. A null return from put can also mean the key previously held null, since HashMap allows null values.
How do you tell a missing key from a null value in a Java HashMap?
Use containsKey. A HashMap may store null as a value, so get returns null both for a key mapped to null and for an absent key. After map.put("x", null), both map.get("x") and map.get("y") return null, but map.containsKey("x") is true and map.containsKey("y") is false. Note that getOrDefault also returns the stored null for x, not the default.
Why is a map stored as an unsorted list slow?
Every operation must walk the list to find the key, so each one is O(n). A lookup for an absent key checks all n entries, and a present key takes about (n + 1) / 2 checks on average. Even put is O(n), because keys must be unique and the map has to confirm the key is not already there before adding it. Doubling the entries roughly doubles the work.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →