UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 14.5 Free with a free account
Sorted Maps: Keeping Key-Value Pairs in Order
Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.5 · lesson 60 of 8710 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Separate Chaining: Linked Buckets →← Open Addressing: Linear and Quadratic ProbingNext lesson: Separate Chaining: Linked Buckets →
In this lesson
Ordered map queries with sorted arrays, skip lists and TreeMap.
- Use sorted map operations such as floorKey, ceilingKey, lowerKey and subMap
- Implement a sorted array map with binary search and explain its insertion cost
- Trace search and insertion in a skip list and explain its expected cost
- Choose between a hash table, a sorted array, a skip list and TreeMap
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,409 words). Read along, or search it.
Opening Question
Coat Checks Versus Phone Books
A coat check works like a hash table. Hand over ticket forty-seven, and the attendant fetches your coat at once, without looking at any other coat. But ask which ticket comes right after forty-seven, or for every coat from forty to sixty, and there's no good way to answer. The coats were never arranged by number. A phone book is different. Its entries are in order, so finding the first name after Sharma is easy. Many programs need that second kind of lookup.
Definition
First, Last, Floor, Ceiling and Ranges
A sorted map is a map whose keys have a natural order, and which answers questions using that order. Take an appointment book, with times written as numbers: nine hundred means nine o'clock. First key gives the smallest key, nine hundred, and last key the largest, sixteen thirty. Floor key of twelve hundred is the largest key at or below it: eleven hundred, the latest appointment before noon. Ceiling key is the smallest at or above: thirteen thirty. And a range query returns every entry between two limits. From ten hundred to fourteen hundred: Ben, Cy and Dee.
Strict Versions
Lower, Higher, Head and Tail
Floor and ceiling allow an exact match: floor key of eleven hundred is eleven hundred itself. Lower key and higher key are the strict versions: lower key of eleven hundred is ten fifteen. When nothing qualifies, the answer is null. Nothing lies at or below eight hundred, so floor key of eight hundred is null, and code must be ready for that. Head map takes the keys below a limit, and tail map the keys from a limit upward: one-sided versions of the range query.
Sorted Array Map
Binary Search Over Parallel Arrays
The simplest sorted map keeps two parallel arrays: keys in increasing order, and the matching values at the same positions. Because the keys are sorted, binary search finds any key in order log n steps. When the key is absent, the search returns a negative number that encodes where it would go: minus the insertion point, minus one. That makes floor and ceiling easy. The insertion point is the first slot with a larger key, so the ceiling sits there, and the floor sits just before it. A range query is binary search to the first key in range, then reading forward until a key passes the upper limit. The keys in range form one unbroken block.
Weakness
Insertion Shifts Every Later Entry
Adding a key is where this design struggles. Binary search finds the right slot quickly, but every entry after it must move one place right to make room. Insert twelve hundred into the book: three entries shift. Finding the slot was the cheap part. Build tables from random keys and count every entry moved. Doubling n multiplies the total by about four each time: roughly n squared over four, so order n per insertion. So a sorted array is excellent when the data changes rarely, and poor when keys come and go constantly.
Quick Check
Searching for an Absent Thirty-Five
Quick check. A sorted array holds ten, twenty, thirty, forty and fifty. Binary search looks for thirty-five, which isn't there. Using the same rule as Java's arrays binary search, what number does it return? Pause, and decide. It's b, minus four. Thirty-five would go at index three, before forty. Minus three, minus one, is minus four. The extra minus one is there, so that a key belonging at index zero still gives a negative answer. Option c, plain three, would wrongly claim the key was found.
Skip Lists
Express Lanes Built by Coin Flips
A linked list makes insertion easy, since nothing shifts, but it can't use binary search. Reaching the middle means walking there link by link. A skip list fixes that with express lanes. Think of a subway line: local trains stop everywhere, express trains at only a few stations. Level one holds every key in order. When a key is inserted, coins are flipped: heads, and it also joins level two. Heads again, level three, and so on. So about half the keys sit on level two, a quarter on level three: each higher level is an express lane with about half as many stops.
Search Walkthrough
Finding the Floor of Seventy-Five
To search, start at the top left. Move right while the next key isn't larger than the target. When it is too large, or there's none, drop down a level. Search for the floor of seventy-five in this ten-key list. On level three, step to forty. The next key, eighty, is too large: drop. On level two, eighty is still too large: drop again. On level one, walk fifty, sixty, seventy, and stop, because eighty is too large. The floor is seventy. Seven keys examined, where walking level one from the left would have looked at eight. A small saving with ten keys, but it grows fast.
Insertion and Cost
Linking In Without Shifting
Insertion needs no shifting at all. A search records, on every level, the last node before the new key. The new key's height comes from the coin flips, and it's linked in at each of its levels by changing a few pointers. How fast is it? Averaged over two thousand searches, a skip list of a hundred thousand random keys examined about thirty keys per search. Scanning examined about fifty thousand, and binary search about sixteen. So the skip list examines about twice as many keys as binary search, but grows the same slow way: each tenfold increase adds only about five. And it costs about two links per key.
Expected Time
Unlucky Shapes Become Rare
The search takes expected order log n time. Expected matters: the coin flips could, in principle, build an unlucky shape, but that becomes extremely unlikely as the list grows. Inserting and removing are also expected order log n, with no shifting. Java's concurrent skip list map is built on this idea, for use by many threads at once.
Why Not Hashing
Hash Tables Scatter Neighbors
Why not a hash table? A good hash function spreads keys evenly, and makes no promise that nearby keys land in nearby slots. Take a range query for keys between thirty and sixty. In a sorted array, thirty-eight, forty-four and fifty-nine sit side by side. In a hash table using key mod eleven, they sit in slots five, zero and four, mixed in with keys that don't match, and nothing says where the next larger key is. So every slot must be examined, and the same is true of first key, last key, floor and ceiling. Over a hundred thousand keys, a hash map examined all hundred thousand. The sorted array examined sixty-two.
Quick Check
Latest Appointment Before Half Past One
Quick check, back to the appointment book: nine hundred, ten fifteen, eleven hundred, thirteen thirty, fifteen hundred, sixteen thirty. You need the latest appointment that starts before half past one. Which call gives it? Pause, and decide. It's b. Lower key is strict, so it skips thirteen thirty itself and returns eleven hundred. Floor key allows an exact match, and thirteen thirty is in the book, so it would return thirteen thirty. Ceiling key looks upward, and returns thirteen thirty too.
Java Library
TreeMap Supplies Every Operation
In practice, Java's TreeMap supplies every operation in this lesson: first and last key, floor, ceiling, lower and higher, the range views, and poll first entry, which removes the smallest. Inside, it's a balanced search tree, which keeps its shape in check, so every operation takes order log n time in the worst case: no shifting, and no randomness.
Decision Guide
Picking a Sorted Map Design
So which one? Exact lookups only, with no questions about order: a hash table. Built once, then queried often by floor or range: a sorted array. Frequent inserts and removals plus ordered queries: a TreeMap. Many threads updating one sorted map: the skip list map. And watch for three mistakes: expecting a HashMap to iterate in sorted order, mixing up floor and ceiling, and storing a null floor result in an int, which throws a null pointer exception.
Key Takeaways
Ordered Queries and Their Costs
To recap. A sorted map adds first key, last key, floor, ceiling and range queries to the usual map operations. A sorted array answers each in order log n, but pays order n shifting for every insertion or removal. A skip list adds random express lanes, for expected order log n with no shifting. A hash table scatters neighboring keys, so ordered queries need a full scan. And TreeMap gives all of it with guaranteed order log n.
Think About It
Next Departure Lookups
Here's something to think about. A transit app keeps departure times in a sorted map. Almost every request asks for the next departure at or after a given time, and a few departures are added each day. Compare a HashMap, a sorted array and a TreeMap for this job. Which would you pick, and what would change your mind?
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
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 UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks 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 Sorted Maps: Keeping Key-Value Pairs in Order
What is the difference between floorKey and lowerKey in Java's TreeMap?
What does Arrays.binarySearch return when the key is not found?
What is a skip list?
Why can't a hash table answer range queries efficiently?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
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.
3 credits · NCCRSEnroll →