Sign inSign in
ConceptSystems & CS

Hash table

A data structure that uses a hash function to map keys to values, implemented as an array of linked lists.
as David J. Malan defines itHarvard UniversityThe wording closest to all 5 definitions
Watch it explained

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

4

Each in their own terms, from the easiest level.

  • Erik Demaine

    MIT · Introductory

    A dictionary data structure that stores arbitrary keys and values with constant time operations with high probability.
    • 26:38Hashing with Chaining, Simple Uniform Hashing & Universal Families
    • 28:18Models of Computation, Random Access Machine & Document Distance
  • Ana Bell

    MIT · Introductory

    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.
    • 12:27List Access, Hashing, Simulations, and Course Wrap-Up
  • Andy Pavlo

    Carnegie Mellon University · Undergraduate

    A hash table implements an unordered associative array that maps keys to values.
    • 9:30Static & Dynamic Hash Tables (Linear Probe, Robin Hood, Cuckoo, Extendible)

Lectures that assume it

27

The first 12 are shown.

Connections

39

The lectures that define it or assume it, and the concepts next to it.

Concepts7

Show 1 more

Lectures32

Show 26 more

4 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.