Real Applications Built on Hashing, Explained

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

Real Applications Built on Hashing

Data Structures and Algorithms · Chapter 14: Maps and HashingSection 14.7 · lesson 62 of 879 min · free with a free account

← Separate Chaining: Linked BucketsNext lesson: Binary Search Trees: Smaller Keys Left, Larger Keys Right →

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

Counting, deduplicating, indexing, grouping and memoizing with hash maps.

  • Count items and detect duplicates with HashMap and HashSet
  • Build symbol tables and indexes that replace repeated linear searches
  • Group values by a computed signature such as sorted letters
  • Apply memoization and judge when a method is safe to memoize

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,307 words). Read along, or search it.

Opening Question

Six Programs Built on One Ability

A hash map finds the entry for a key in constant time on average. That one ability, a fast answer to have I seen this key, and what goes with it, powers a huge range of everyday programs. Here are six of them: counting words, spotting duplicates, a symbol table, an index over records, grouping, and remembering answers. Each one is solved the plain way, by scanning, and then with a map.

Application

Counting Words With a Map

To count how often each word appears, keep a map from word to count. For every word, get or default returns its count so far, or zero, and put stores one more. For this sentence, the appears three times and fox twice. A linked hash map keeps the order of first appearance. Merge does the same job in a single call: it adds one to the count, or starts it at one. Both maps come out equal.

Measured Results

List Map Versus Hash Map Counting

For a text of N words, that's N map operations, so with a hash map the work grows in step with N. A list-based map must scan its distinct words every time. Counting a hundred thousand words, measured on one machine, it went from about twenty-one milliseconds with a hundred distinct words to over two seconds with ten thousand. The hash map took about the same few milliseconds every time.

Application

Spotting the First Duplicate

Does a collection hold the same item twice? A set answers directly. Its add method returns true for a new item, and false if it was already there. So the first add that returns false marks the first duplicate. For three, eight, five, eight, two, three, that's eight. The alternative compares every pair. With a thousand distinct items, that's four hundred ninety-nine thousand, five hundred pairs, against a thousand adds. Ten times more items means a hundred times more pairs, but only ten times more adds.

Application

A Symbol Table for an Interpreter

A compiler or interpreter must remember every name a program defines. That record is a symbol table: a map from a name to what it stands for. This tiny interpreter runs lines like y equals x plus three. For each line, it looks up the names it uses, and puts the name it defines. Running x equals five, y equals x plus three, and z equals y plus x leaves x five, y eight, and z thirteen. Running w equals q plus one, with no q defined, stops with undefined variable q. Contains key caught the missing name, before a null could cause a crash.

Application

Indexing Records by a Key Field

Suppose a program holds many student records, and often needs the one with a given ID. Scanning the list each time is slow. Instead, build an index: a map from ID to record, filled once. Afterwards, each lookup is one map step. An index can use any field as its key, if the key is unique. When it isn't, like a student's major, each key maps to a list of records: Biology to Leo, CS to Ava and Mei, Math to Raj and Zoe.

Trade-Off

When an Index Pays Off

Is the index worth it? Measured on one machine with a hundred thousand records: a scan costs about point one five milliseconds per lookup, and building the index about six point six milliseconds. That's the price of about forty-five scans. After that, every lookup is almost free. For a handful of lookups, the scan wins. For thousands, the index wins by a wide margin. An index comes with one duty: keep it in step. When a record is added, removed, or has its key changed, every index must be updated, or it will quietly return stale answers.

Quick Check

First Value Whose Add Fails

Quick check. This loop adds four, nine, two, nine and four to a set, and prints the first value whose add returns false. What does it print? Pause and predict. Nine. The adds return true for four, nine and two, then false for the second nine, so the loop stops there. Four does repeat, but its second copy comes later. The first false marks the first repeat to arrive, not the first value that will ever repeat.

Under the Hood

A Set Is a Map in Disguise

In fact, a set is a map in disguise. Store each element as a key, with any fixed placeholder value, and the map's unique keys become the set's no-duplicates rule. Adding is a put. Put returns the old value, which is null exactly when the key was new: true, true, then false for apple again. Contains is contains key, and remove is a map remove, so pear is removed once, then not found. Java's HashSet is built exactly this way, around a HashMap, and gives the same answers.

Application

Grouping Anagrams by Signature

Grouping gathers items that share some property, with a map whose values are lists. Choose a signature, a key computed from each item, so items that belong together share it. Anagrams use the same letters, so their sorted letters make a perfect signature. Cat, act and tac all sort to a c t. Compute if absent starts a list the first time a signature appears. Nine words fall into four groups. Comparing every pair of words instead would take thirty-six comparisons for nine words, and four hundred ninety-nine thousand, five hundred for a thousand.

Application

Memoizing Fibonacci

A recursive Fibonacci method repeats the same subproblems many times. Memoization removes the repetition: keep a map from arguments to answers, and check it before computing anything. The method barely changes. One line looks up an earlier answer, and one line records a new one. The effect is dramatic. Fib of thirty makes over two and a half million calls without the memo, and fifty-nine with it. With the memo, fib of n makes two n minus one calls and stores n minus one entries, so time and memory both grow in proportion to n.

Quick Check

Asking for Fib of Six Again

Quick check. The memoized fib has already computed fib of six once. Then it's asked for fib of six again. How many calls does the second request make? Pause, and decide. One call. Six is already in the map, so the method returns the stored answer at once, with no recursive calls. The map doesn't grow either. Eleven is what the first request made, two n minus one. And twenty-five is what plain recursion makes, every single time.

Application

Grid Paths With Two-Argument Keys

A map has one key, but many methods take two or more arguments. Combine them into a single key. This method counts the routes across a grid from one corner to the opposite one, moving only right or down. The rows and columns still to cross are joined into a text key, like three comma five. For a fourteen by fourteen grid, plain recursion makes about eighty million calls. The memo makes three hundred ninety-three, and stores a hundred ninety-six entries. For an r by r grid, the memo version makes two r squared plus one calls, and stores r squared entries.

Limits

When Memoization Fits

Memoization isn't free, and it doesn't suit every method. The method must always give the same answer for the same arguments, with no hidden input like the time of day. The same subproblems must really come up more than once. And the arguments must form a key, with memory for one entry per distinct set of them. Note that the recursion still goes as deep as before, so the stack space is unchanged.

Key Takeaways

Six Uses of Fast Lookup

To sum up. Counting is one map update per item. A set finds the first duplicate in one pass, instead of comparing every pair. A symbol table maps names to values, and an index maps a key field to a record, if it's kept in step. A set is a map with placeholder values, and grouping maps a computed signature to a list. Memoization stores answers by their arguments, turning exponential repetition into linear work, at the price of memory.

Think About It

Memoizing a Method With Hidden Inputs

Something to think about. A memoized method also reads the current time, or a value that other parts of the program keep changing. What would go wrong, and why?

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 Real Applications Built on Hashing

How do you count word frequencies with a HashMap in Java?
Use the word as the key and its count as the value, adding one each time the word appears. The clearest single call is counts.merge(w, 1, Integer::sum), which stores 1 for a new word and otherwise adds 1 to the old count. An equivalent form is counts.put(w, counts.getOrDefault(w, 0) + 1). Each update takes expected O(1) time, so counting n words takes about O(n).
How do you find the first duplicate in a list using a HashSet?
Add each value to a HashSet in order and stop at the first value whose add returns false, because add reports whether the value was new. For the values 3, 8, 5, 8, 2, 3, the adds succeed for 3, 8 and 5 and fail on the second 8, so the answer is 8. This takes expected O(n) time, while comparing every pair of 1,000 values needs up to 499,500 comparisons.
How do you group anagrams using a hash map?
Give each word a signature that all its anagrams share, such as its letters in sorted order, and use that signature as the map key. In Java: char[] c = w.toCharArray(); Arrays.sort(c); groups.computeIfAbsent(new String(c), k -> new ArrayList<>()).add(w); where groups is a Map<String, List<String>>. The words listen, silent and enlist all have the signature eilnst, so they share one list.
What is memoization and when should you use it?
Memoization stores each result in a map keyed by the method's arguments and returns the stored answer when the same arguments appear again. It turns a recursive Fibonacci method from more than 2.5 million calls for fib(30) into 59, since fib(n) then makes 2n - 1 calls. Use it when subproblems repeat and the result depends only on the arguments, with no hidden inputs such as the clock or changing fields.

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 →