Sign inSign in
ConceptSystems & CS

Cuckoo hashing

A hashing technique that uses multiple hash functions and multiple tables, evicting and re-hashing elements on collisions to ensure O(1)O(1) lookups.
as Andy Pavlo defines itCarnegie Mellon UniversityThe wording closest to all 3 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.

Hash function3Hash table2Collision1Collision resolution1Hash collisions1Hashing1

Lecturers

2

Each in their own terms, from the easiest level.

  • Andy Pavlo

    Carnegie Mellon University · Undergraduate

    A hashing technique using multiple hash functions and locations, evicting and rehashing elements on collision to maintain O(1)O(1) lookups.
    • 39:50Static & Dynamic Hash Tables (Linear Probe, Robin Hood, Cuckoo, Extendible)
  • Erik Demaine

    MIT · Graduate

    A hashing scheme that uses two tables and two hash functions to guarantee O(1)O(1) worst-case lookup time with two probes.

Connections

6

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

Concepts3

2 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.