ConceptSystems & CS
Hash function
A function that maps any object (or hashable object) to an integer.
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.
Function3Hash table2Integer2Asymmetric algorithms1Cryptographic mechanisms1Digital signatures1Mutable vs immutable objects1Object1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
7Each in their own terms, from the easiest level.
Ana Bell
A function that takes an immutable object as input and converts it into a numeric integer value.Erik Demaine
A function that maps a giant universe of keys to a reasonably small table.Andy Pavlo
A function that computes an offset into an array for a given key to find the desired value.James Mickens
A function that is difficult to invert, used to store password representations rather than cleartext passwords.Christof Paar
Auxiliary functions used in cryptography in conjunction with other mechanisms like digital signatures.David J. Malan
An algorithm that takes an input and produces a fixed-size integer, which is used as an index in a hash table.Srini Devadas
A hash function maps arbitrary strings of data to fixed-length outputs in a deterministic, public, and random manner.
Lectures that assume it
25The first 12 are shown.
- Approximate counting
- Independence
- Cryptography: Encryption
- Table Doubling, Karp-Rabin
- Open Addressing, Cryptographic Hashing
- Randomization: Universal & Perfect Hashing
- Hacking the Xbox One
- Sorting & Aggregation Algorithms
- Query Cost Models: Statistics
- Razborov Smolensky Lower Bounds for AC0[p]
- SHA-1 Hash Function
- Nondeterministic Parallel Programming
Connections
41The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures33
- Hashing with Chaining, Simple Uniform Hashing & Universal Families
- Static & Dynamic Hash Tables (Linear Probe, Robin Hood, Cuckoo, Extendible)
- User Authentication
- Hash Functions
- Dictionaries
- Data Structures
Show 27 moreShow fewer
- Cryptography: Hash Functions
- List Access, Hashing, Simulations, and Course Wrap-Up
- Approximate counting
- Independence
- Cryptography: Encryption
- Table Doubling, Karp-Rabin
- Open Addressing, Cryptographic Hashing
- Randomization: Universal & Perfect Hashing
- Hacking the Xbox One
- Sorting & Aggregation Algorithms
- Query Cost Models: Statistics
- Razborov Smolensky Lower Bounds for AC0[p]
- SHA-1 Hash Function
- Nondeterministic Parallel Programming
- Introduction to Hash-based Post-quantum Cryptography (PQC)
- Message Authentication Codes (MAC) and HMAC
- Speculative Parallelism & Leiserchess
- Fundamentals of Sequence Search and Alignment
- Join Algorithms
- Fork Consistency, Certificate Transparency
- Parallel Hash Join Algorithms
- Yellowbrick Data Warehouse System
- SHA-3 Hash Function
- Apache Doris: Real-Time Analytics and Search Database for AI Agents
- Post-Quantum Cryptography: Merkle Signature Schemes
- BLEND: Fuzzy Seed Matching for Fast & Accurate Read Mapping
- Hash All The Things / Get All The Sig(s): Automatic Function Detection for Reverse Engineers