ConceptSystems & CS
Hash table
A data structure that uses a hash function to map keys to values, implemented as an array of linked lists.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Array4Hash function3Dictionaries2Arrays and lists1Associative array1Constant time complexity1Data structure1Hashing1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
4Each in their own terms, from the easiest level.
Erik Demaine
A dictionary data structure that stores arbitrary keys and values with constant time operations with high probability.Ana Bell
A data structure like a long list where indices are looked up using a hash function, allowing for constant time lookups in the average case.Andy Pavlo
A hash table implements an unordered associative array that maps keys to values.
Lectures that assume it
27The first 12 are shown.
- Tuning a TSP Algorithm
- Integer Models
- Two-Phase Locking Concurrency Control
- Table Doubling, Karp-Rabin
- Open Addressing, Cryptographic Hashing
- Randomization: Universal & Perfect Hashing
- Dictionaries
- Dynamic Connectivity Lower Bound
- Divide & Conquer: Van Emde Boas Trees
- Buffer Pool Managers, LRU-K Eviction & Direct I/O
- Data Formats & Encoding Part 1
- B+Tree Indexes
Connections
39The lectures that define it or assume it, and the concepts next to it.
Concepts7
Show 1 moreShow fewer
Lectures32
- Hashing with Chaining, Simple Uniform Hashing & Universal Families
- Static & Dynamic Hash Tables (Linear Probe, Robin Hood, Cuckoo, Extendible)
- Models of Computation, Random Access Machine & Document Distance
- Data Structures
- List Access, Hashing, Simulations, and Course Wrap-Up
- Tuning a TSP Algorithm
Show 26 moreShow fewer
- Integer Models
- Two-Phase Locking Concurrency Control
- Table Doubling, Karp-Rabin
- Open Addressing, Cryptographic Hashing
- Randomization: Universal & Perfect Hashing
- Dictionaries
- Dynamic Connectivity Lower Bound
- Divide & Conquer: Van Emde Boas Trees
- Buffer Pool Managers, LRU-K Eviction & Direct I/O
- Data Formats & Encoding Part 1
- B+Tree Indexes
- Index Concurrency Control
- EXODUS + Volcano Query Optimizer Generators
- Query Cost Models: More Cardinality Estimation
- Speculative Parallelism & Leiserchess
- Multi-Way Join Algorithms / Worst-Case Optimal Joins
- Fundamentals of Sequence Search and Alignment
- Data Formats & Encoding Part 2
- Join Algorithms
- Parallel Hash Join Algorithms
- BLEND: Fuzzy Seed Matching for Fast & Accurate Read Mapping
- SingleStore Database Overview
- Leiserchess Codewalk
- SneakySnake: Fast Pre-Alignment Filtering on CPUs, GPUs & FPGAs
- GRIM-Filter: In-Memory Seed Location Filtering in 3D-Stacked DRAM
- Cybersecurity