Hash Tables — Simple English

69 lessons · Data Structures & Algorithms · Simple English · Beginner Friendly

01 Understanding the Problem: Why We Need a Better Way to Store MappingsFree Understanding the Problem Before learning about a hash table, it helps to first see a problem that programmers run into … 02 Hash Tables: Fast Key-Value StorageFree Hash Tables: Fast Key-Value Storage Imagine you want to store pairs of information that belong together — like a person'… 03 Defining a Hash FunctionFree Defining a Hash Function A hash function sits at the heart of every hash table. Before we look at how a hash table works… 04 What Makes a Hash Function Good🔒 What Makes a Hash Function Good A hash function is a small machine that takes some input (called a key) and turns it int… 05 Easy Examples of Hash Functions🔒 Easy Examples of Hash Functions A hash function is just a rule that takes some input (called the key) and turns it into … 06 How a Hash Table Works on the Inside🔒 How a Hash Table Works on the Inside A hash table is one of the most useful tools in programming. It lets you store some… 07 Hash Table Operations: Insert, Search, and Delete🔒 Hash Table Operations: Insert, Search, and Delete A hash table is a tool for storing key-value pairs — like a phone book… 08 Separate Chaining: Solving Hash Table Collisions with Chains🔒 Separate Chaining: Solving Hash Table Collisions with Chains A hash table stores data using a hash function. You give it… 09 The Building Blocks of a Separate Chaining Hash Table🔒 The Building Blocks of a Separate Chaining Hash Table A hash table is a tool that lets you store and find data very fast… 10 The Hash Table Class: Packaging Everything Into One Easy-to-Use Tool🔒 The Hash Table Class: Packaging Everything Into One Easy-to-Use Tool By now you have met all the separate pieces that ma… 11 Searching for a Key in a Hash Table (Separate Chaining)🔒 Searching in a Hash Table with Separate Chaining A hash table stores data as key-value pairs. You give it a key, and it … 12 Insert Operation in a Hash Table (Separate Chaining)🔒 Inserting a Key-Value Pair Using Separate Chaining A hash table stores data as key-value pairs. The key is like a label,… 13 Deleting a Key from a Hash Table (Separate Chaining)🔒 Deleting a Key with Separate Chaining A hash table stores key-value pairs (also called records). We have already seen ho… 14 Designing a Hash Table with Separate Chaining🔒 What is a Hash Table? Imagine you have a row of numbered lockers. If someone tells you a name, you want to instantly fin… 15 Linear Probing: Storing Keys in One Shared Array🔒 Linear Probing: Storing Keys in One Shared Array Earlier we saw one way to build a hash table called separate chaining. … 16 The Building Blocks of a Linear Probing Hash Table🔒 The Building Blocks of a Linear Probing Hash Table A hash table is a tool that lets us store and find data very quickly.… 17 Putting It All Together: The Hash Table Class🔒 Putting It All Together: The Hash Table Class So far we have learned the separate pieces of a hash table: a hash functio… 18 Searching in a Hash Table That Uses Linear Probing🔒 Searching in a Hash Table That Uses Linear Probing A hash table lets you store and look up data very fast. Each piece of… 19 Insert Operation in a Hash Table (Linear Probing)🔒 Insert Operation in Linear Probing A hash table stores data as key-value pairs. Think of it like a row of numbered locke… 20 Deleting a Key in a Hash Table That Uses Linear Probing🔒 Deleting a Key with Linear Probing A hash table stores key-value pairs. The delete operation removes one of these pairs.… 21 Building a Hash Table with Linear Probing🔒 Building a Hash Table with Linear Probing A hash table is a tool for storing pairs of information. Each pair has a key (… 22 Quadratic Probing: A Smarter Way to Handle Hash Collisions🔒 Quadratic Probing: A Smarter Way to Handle Hash Collisions A hash table stores key-value pairs inside an array. To decid… 23 The Building Blocks of a Quadratic Probing Hash Table🔒 The Building Blocks of a Quadratic Probing Hash Table A hash table is a tool that lets us store and find data very quick… 24 Putting It All Together: The Hash Table Class🔒 Putting It All Together: The Hash Table Class So far you have learned the separate pieces of a hash table: the slots tha… 25 Searching in a Hash Table with Quadratic Probing🔒 Searching in a Hash Table with Quadratic Probing Searching is one of the most important things we do with a hash table. … 26 Insert Operation in a Hash Table Using Quadratic Probing🔒 Inserting into a Hash Table with Quadratic Probing A hash table stores data as key-value pairs. Think of the key as a la… 27 Deleting a Key from a Hash Table with Quadratic Probing🔒 Deleting a Key with Quadratic Probing When we store key–value pairs in a hash table, we sometimes need to remove one. Th… 28 Building a Hash Table with Quadratic Probing🔒 Building a Hash Table with Quadratic Probing A hash table is a tool that lets you store and find data very fast. You giv… 29 Double Hashing: A Smarter Way to Handle Collisions🔒 Double Hashing: A Smarter Way to Handle Collisions A hash table is a way to store key-value pairs so you can find them v… 30 Building Blocks of a Double Hashing Hash Table🔒 Building Blocks of a Double Hashing Hash Table A hash table is a tool that lets you store and find data very fast. Think… 31 The Hash Table Class: Wrapping It All Up🔒 The Hash Table Class: One Clean Package By now you have seen the separate pieces of a hash table — the slots that hold r… 32 Searching in a Hash Table That Uses Double Hashing🔒 Searching in a Hash Table That Uses Double Hashing A hash table stores pairs of a key and its value, like a label and th… 33 Insert Operation in Double Hashing🔒 Insert Operation in Double Hashing A hash table stores key-value pairs. Think of a key as a label (like key3) and the va… 34 Deleting a Key from a Hash Table with Double Hashing🔒 Deleting a Key from a Hash Table (Double Hashing) A hash table stores key–value pairs in a plain array. Double hashing i… 35 Building a Hash Table with Double Hashing🔒 Building a Hash Table with Double Hashing A hash table is a tool that stores pairs of information. Each pair has a key (… 36 The Counting Pattern: Using a Hash Map to Count Frequencies🔒 The Counting Pattern Many problems ask the same kind of question: how many times does each item appear? Maybe you have a… 37 The Counting Pattern: Finding the First Non-Repeating Character🔒 The Counting Pattern Some problems become much easier once you know how many times each item appears in your data. This … 38 Finding the First Non-Repeating Character in a String🔒 Finding the First Non-Repeating Character Imagine you have a word, and you want to find the first letter that appears on… 39 Constructibility Check: Can One String Be Built From Another's Letters?🔒 The Problem Imagine you have a small bag of letter tiles, like in a word game. The question is simple: can you spell one… 40 Anagram Checker: Are Two Words Made of the Same Letters?🔒 Checking if Two Strings Are Anagrams Imagine you have a set of letter tiles, like in the game Scrabble. You arrange them… 41 Build the Longest Palindrome From a String's Letters🔒 Build the Longest Palindrome From a String's Letters A palindrome is a word that reads the same forwards and backwards. … 42 Grouping Anagrams Together🔒 Grouping Anagrams Together What is an anagram? An anagram is a word made by rearranging the letters of another word. Bot… 43 The Pattern Generation Technique🔒 The Pattern Generation Technique What is a "pattern" in a sequence? Look at these two strings. They use completely diffe… 44 The Pattern Generation Technique: Solving Homomorphic Strings🔒 The Pattern Generation Technique Some problems become much easier once you stop looking at the exact characters in a seq… 45 Row Specific Words: Finding Words You Can Type on One Keyboard Row🔒 Row Specific Words Look down at a normal American keyboard. The letters are arranged in three rows. Our job in this prob… 46 Homomorphic Strings: Checking if One String Can Map to Another🔒 Homomorphic Strings Imagine you have a secret code. You decide that every time you see the letter a, you will write q in… 47 Pattern Matching: Checking if a String Follows a Pattern🔒 Pattern Matching Sometimes we want to check if a string of words follows a certain shape or "pattern." The pattern is gi… 48 Grouping Strings That Belong to the Same Shifting Sequence🔒 Grouping Strings That Belong to the Same Shifting Sequence Imagine you have a list of words, and each word can be "shift… 49 The Fixed-Sized Sliding Window Pattern🔒 The Fixed-Sized Sliding Window Pattern Imagine you have a long row of items — letters, numbers, anything — lined up one … 50 Spotting and Solving the Fixed-Size Sliding Window Pattern🔒 The Fixed-Size Sliding Window Pattern Imagine you are looking at a long street through a window of a moving train. At an… 51 Finding Duplicates Inside a Window of Size k🔒 Finding Duplicates Inside a Window of Size k Imagine you are looking at a long list of numbers, but you can only see k o… 52 Counting Distinct Numbers in Every Window of Size k🔒 Counting Distinct Numbers in Every Window of Size k Imagine you are looking at a long row of numbers, but you can only s… 53 Check if One String Contains a Permutation of Another🔒 The "Contains a Permutation" Problem This is a classic interview question. You are given two strings, s1 and s2. Your jo… 54 Anagram Finder: Locating All Anagrams of a Word Inside a String🔒 Anagram Finder This is a classic string problem. Before we solve it, let's make sure we understand the words used in the… 55 The Variable-Sized Sliding Window Pattern🔒 The Variable-Sized Sliding Window Pattern Imagine you are looking at a long list of items — let's say an array called ar… 56 The Variable-Sized Sliding Window Pattern🔒 The Variable-Sized Sliding Window Pattern Imagine you are reading a long line of letters and you want to find the longes… 57 Longest Substring With All Distinct Characters🔒 Longest Substring With All Distinct Characters Imagine you are given a word, and you want to find the longest stretch in… 58 Longest Substring with At Most K Distinct Characters🔒 Longest Substring with At Most K Distinct Characters Imagine you have a long word, and you are allowed to pick a continu… 59 Longest Substring of One Letter After k Changes🔒 The Problem: Make the Longest Run of the Same Letter Imagine you have a row of letters, like ABAB. Some are the same, so… 60 Longest Subarray With a Given Sum k🔒 Finding the Longest Subarray That Sums to k Let's learn a classic and very useful array problem. It looks simple at firs… 61 Twin in Proximity: Finding Equal Values That Are Close Together🔒 Twin in Proximity This is a classic array problem. Let's understand exactly what it asks, and then build a smart way to … 62 The Prefix Sum Pattern: Precomputing Running Totals🔒 The Prefix Sum Pattern Imagine you have a long list of numbers, and people keep asking you questions like "What is the t… 63 The Prefix Sum Pattern: Counting Zero-Sum Subarrays🔒 Spotting When Prefix Sums Will Help Some problems have a hidden structure that the prefix sum technique unlocks. The tec… 64 Finding the First Equilibrium Point in an Array🔒 The Equilibrium Point Problem Imagine you have a row of numbers and you want to find one special spot. This spot is spec… 65 Self-Excluded Array Product: Multiply Everything Except Yourself🔒 Self-Excluded Array Product Imagine you have a list of numbers. For each spot in the list, you want to find the product … 66 Finding the Longest Subarray with Equal 0s and 1s🔒 Finding the Longest Subarray with Equal 0s and 1s Imagine you have a row of light switches, where each switch is either … 67 Zero Sum Subarrays: Finding Every Range That Adds Up to 0🔒 Zero Sum Subarrays Imagine you have a row of numbers. A subarray is just a chunk of numbers that sit next to each other … 68 Designing an LRU Cache🔒 Designing an LRU Cache Imagine your desk has room for only a few books at a time. When you need a new book and your desk… 69 Designing a Randomised Set: insert, remove, and getRandom in O(1)🔒 Designing a Randomised Set Imagine you have a bag of numbers. You want to do three things with this bag, and you want ea…