Last Updated: Sep 03, 2026

Do not post your project on a public Github repository.

Overview

All the programming projects this semester will be written on the BusTub database management system. This system is written in C++. To make sure that you have the necessary C++ background, you must complete a simple programming assignment to assess your knowledge of basic C++ features. You will not be given a grade for this project, but you must complete the project with a perfect score before being allowed to proceed in the course. Any student unable to complete this assignment before the deadline will be asked to drop the course.

All of the code in this programming assignment must be written in C++. The projects will be specifically written for C++17, but we have found that it is generally sufficient to know C++11. If you have not used C++ before, here are some resources to help:

15-445 Bootcamp, which contains several small examples to get you familiar with C++11 features.
Learncpp is a useful resource that includes quizzes to test your knowledge.
cppreference has more detailed documentation of language internals.
A Tour of C++ and Effective Modern C++ are also digitally available from the CMU library.

If you are using VSCode, we recommend you to install CMake Tools, C/C++ Extension Pack and clangd. After that, follow this tutorial to learn how to use the visual debugger in VSCode: Debug a C++ project in VS Code.

If you are using CLion, we recommend you to follow this tutorial: CLion Debugger Fundamentals.

If you prefer to use gdb for debugging, there are many tutorials available to teach you how to use gdb. Here are some that we have found useful:

This is a single-person project that will be completed individually (i.e. no groups, no coding agents).

Release Date: Aug 24, 2026
Due Date: Sep 06, 2026 @ 11:59pm

Project Specification

Consider the following scenario: you are building an in-memory registry for a popular web service that must quickly determine whether a request identifier has already been seen. The service receives a large stream of requests from many worker threads, so the registry must support fast insertion and lookup without using more memory than necessary. This is where a Robin Hood hash set comes in!

Robin Hood hashing is an open-addressing technique for hash tables. Each key has a home bucket, and collisions are resolved by probing successive buckets, wrapping around at the end of the table. When a newly inserted key has probed farther than the key currently occupying a bucket, it displaces that key and lets the displaced key continue probing. This distributes probe distances more evenly, reducing long lookup sequences. Robin Hood hashing is useful for memory-efficient in-memory indexes and other high-throughput membership-tracking workloads.

Your table is fixed-capacity: it must not resize. Deleted entries should become tombstones so that lookups continue through them, while later insertions may reuse their buckets. All table operations must be safe when called concurrently.

Parameters

The Robin Hood hash set is configured with the following parameters:

capacity – Number of buckets in the fixed-size table. Each key's home bucket is hash(key) % capacity; a larger capacity leaves more empty buckets and generally reduces collisions. Capacity must be nonzero.
hasher – A hash function that maps a key to a hash value. Use the supplied hasher to determine each key's home bucket; do not assume that keys themselves are hashable or that their hash values are unique. The starter code supplies deterministic defaults for the supported key types, so you do not need to implement a hash function.
key_equal – An equality predicate used to determine whether two keys represent the same set element. Use it when checking for duplicates or locating a key during lookup and deletion.

Tombstones

In open-addressed hash tables, deleting a key cannot simply make its bucket empty: doing so could cause a later lookup to stop before reaching a key displaced by the deleted entry. Instead, deletion leaves a tombstone, a special marker indicating that the bucket was previously occupied but no longer contains a live key. Lookups must probe past tombstones, while insertions can reuse their buckets.

Each bucket is in exactly one of three logical states: empty, occupied, or tombstone. An empty bucket has never been occupied since the table was created or last cleared; a lookup may stop at an empty bucket because its key cannot appear later in that probe sequence. An occupied bucket contains a live key. A tombstone contains no live key but must not terminate a lookup: continue probing through tombstones until you find the key, reach an empty bucket, or have examined every bucket in the fixed-capacity table.

For example, in a table of capacity 8, keys 6, 14, and 22 all have home bucket 6 and may occupy buckets 6, 7, and 0, respectively. After removing 14, bucket 7 becomes a tombstone. A lookup for 22 must continue past that tombstone and wrap around to bucket 0. A later insertion of the colliding key 30 may reuse the tombstone at bucket 7.

Robin Hood Hashing Walkthrough

Consider a table with capacity 4. Each key's home bucket is hash(key) % 4; for this example, assume the hash of each integer is the integer itself. This is only to make the walkthrough easy to follow: your implementation must use the supplied hash function. We write each entry as key (probe distance), where probe distance is the number of buckets between the key's home bucket and its current bucket.

First, insert 0. Its home bucket is 0, which is empty:

Bucket:  0      1      2      3
         0 (0)  empty  empty  empty

Next, insert 4. Its home bucket is also 0, so it probes to bucket 1 and is stored with probe distance 1:

Bucket:  0      1      2      3
         0 (0)  4 (1)  empty  empty

Now insert 1. Its home bucket is 1, but bucket 1 is occupied by 4, which has already probed farther than 1 has. Therefore, 1 continues to bucket 2:

Bucket:  0      1      2      3
         0 (0)  4 (1)  1 (1)  empty

Finally, insert 8, whose home bucket is 0. It probes past 0 and 4; when it reaches bucket 2, it has probe distance 2, while 1 has probe distance 1. Under the Robin Hood rule, 8 displaces 1, and 1 continues probing to bucket 3:

Bucket:  0      1      2      3
         0 (0)  4 (1)  8 (2)  1 (2)

This displacement gives the key with the longer probe sequence (8) the earlier bucket. Robin Hood hashing uses this rule to distribute probe distances more evenly and reduce long lookup sequences.

Resources

Instructions

You will have to complete the following task for this project:

Task #1

Implement a basic Robin Hood hash set data structure supporting insertion, deletion, and lookup.

In src/include/primer/robin_hood_hash_set.h and src/primer/robin_hood_hash_set.cpp, implement the following functions:

RobinHoodHashSet(capacity, hasher, key_equal): construct a table with a nonzero fixed capacity. A capacity of zero must throw std::invalid_argument.
RobinHoodHashSet(&&other) and operator=(&&other): move the table's contents. After a move, the moved-from table must remain valid, have Capacity() == 0 and Size() == 0, and safely support Clear().
Insert(key): insert a key using Robin Hood open addressing. Return true for a successful insert, including an insertion of a key already present; inserting a duplicate must not increase Size(). Return false only when the table is full and the key is not already present.
Remove(key): mark an existing key deleted and return true; return false when the key is absent. Preserve tombstones so lookups can probe past deleted entries.
Contains(key): report whether a live key is present.
Clear(): remove all entries and tombstones while retaining the table's capacity.
GetBucket(key), Size(), Capacity() / BucketCount(), LoadFactor(), and MaxProbeDistance(): provide the observable table state defined by the starter interface. GetBucket returns Capacity() when the key is absent. LoadFactor() is Size() / Capacity() (and is 0.0 for a moved-from table); MaxProbeDistance() considers only occupied buckets.

Feel free to design your helper functions to assist with the implementation.

Important Information

Use the supplied Hash and KeyEqual template parameters. Map a hash value to its home bucket with hash(key) % capacity, and advance probes circularly.
The test suite includes parallel tests. Your implementation must be thread-safe for Insert(key), Remove(key), and Contains(key), including scenarios where these operations overlap on the same hash set. It must avoid data races, deadlock, and livelock while preserving a coherent table state.
You may notice the last test compares the performance of your implementation for Insert(item) against one that is strictly sequential. You could only pass this test if the relative speedup of your implementation is larger than 1.2. We expect you NOT to use only a single global latch to guard the whole data structure. If you do so, the contention ratio will be effectively around 1.0. There are many ways to do this. As a hint, try thinking of ways to break down the latch granularity or, even better, not to use a latch at all. If you find this difficult to reason about, try passing other tests with a global latch first before attempting to optimize for this one.

Setting Up Your Project Repository

If the below git concepts (e.g., repository, merge, pull, fork) do not make sense to you, please spend some time learning git first.

The course staff will create and manage your own PRIVATE repository and your own development branch. See Piazza for details. If you have previously forked the repository through the GitHub UI (by clicking Fork), PLEASE DO NOT PUSH ANY CODE TO YOUR PUBLIC FORKED REPOSITORY! Make sure your repository is PRIVATE before you git push any of your code.

If the instructor makes any changes to the code, you can merge the changes to your code by keeping your private repository connected to the CMU-DB master repository. Execute the following commands to add a remote source:

$ git remote add public https://github.com/cmu-db/bustub.git

You can then pull down the latest changes as needed during the semester:

$ git fetch public
$ git merge public/master

Setting Up Your Development Environment

First install the packages that BusTub requires:

# Linux
$ sudo build_support/packages.sh
# macOS
$ build_support/packages.sh

See the README for additional information on how to setup different OS environments.

To build the system from the commandline, execute the following commands:

$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Debug ..
$ make -j`nproc`

We recommend always configuring CMake in debug mode. This will enable you to output debug messages and check for memory leaks (more on this in below sections).

Testing

You can test the individual components of this assignment using our testing framework. We use GTest for unit test cases. You can disable tests in GTest by adding a DISABLED_ prefix to the test name. To run the tests from the command-line:

$ cd build
$ make -j$(nproc) robin_hood_hash_set_test
$ ./test/robin_hood_hash_set_test

In this project, there are no hidden tests. In the future, the provided tests in the starter code are only a subset of the all the tests that we will use to evaluate and grade your project. You should write additional test cases on your own to check the complete functionality of your implementation.

Make sure that you remove the DISABLED_ prefix from the test names otherwise they will not run!

Formatting

Your code must follow the Google C++ Style Guide. We use Clang to automatically check the quality of your source code. Your project grade will be zero if your submission fails any of these checks.

Execute the following commands to check your syntax. The format target will automatically correct your code. The check-lint and check-clang-tidy targets will print errors that you must manually fix to conform to our style guide.

$ make format
$ make check-lint
$ make check-clang-tidy-p0

Memory Leaks

For this project, we use LLVM Address Sanitizer (ASAN) and Leak Sanitizer (LSAN) to check for memory errors. To enable ASAN and LSAN, configure CMake in debug mode and run tests as you normally would. If there is memory error, you will see a memory error report. Note that macOS only supports address sanitizer without leak sanitizer.

In some cases, address sanitizer might affect the usability of the debugger. In this case, you might need to disable all sanitizers by configuring the CMake project with:

$ cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..

Development Hints

You can use BUSTUB_ASSERT for assertions in debug mode. Note that the statements within BUSTUB_ASSERT will NOT be executed in release mode. If you have something to assert in all cases, use BUSTUB_ENSURE instead.

We will test your implementation in release mode. To compile your solution in release mode,

$ mkdir build_rel && cd build_rel
$ cmake -DCMAKE_BUILD_TYPE=Release ..

Post all of your questions about this project on Piazza. Do not email the TAs directly with questions.

TAs will not look into your code or help you debug in this project.

Grading Rubric

In order to pass this project, you must ensure your code follows the following guidelines:

Does the submission successfully execute all of the test cases and produce the correct answer?
Does the submission execute without any memory leaks?
Does the submission follow the code formatting and style policies?

Note that we will use additional test cases to grade your submission that are more complex than the sample test cases that we provide you in future projects.

Late Policy

There are no late days for this project.

Submission

You will submit your implementation to Gradescope:

https://www.gradescope.com/courses/1345516

Run this command in build directory and it will create a zip archive called project0-submission.zip that you can submit to Gradescope.

$ make submit-p0

Although you are allowed submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Most students submit their projects near the deadline, and thus Gradescope will take longer to process the requests. You may not get feedback in a timely manner to help you debug problems. Furthermore, the output from Gradescope is unlikely to be as informative as the output from a debugger (like gdb), provided you invest some time in learning to use it.

CMU students should use the Gradescope course code announced on Piazza.

Collaboration Policy

Every student must work individually on this assignment.
Students are allowed to discuss high-level details about the project with others.
Students are not allowed to copy the contents of a white-board after a group meeting with other students.
Students are not allowed to copy solutions from another person.
Students may not use coding agents to complete any part of the project.

WARNING: All of the code for this project must be your own. You may not copy source code from other students or other sources that you find on the web. Plagiarism will not be tolerated. See CMU's Policy on Academic Integrity for additional information.

Project #0 - C++ Primer Last Updated: Sep 03, 2026