Separate chaining

The idea behind separate chaining is simple: instead of holding just one object, allow elements in our hash table to hold more than one object.

Here we modify our hash table class to implement separate chaining in C++. I encourage you to give this a try on your own before watching the video.

Resources

• SeparateChaining.h
• SeparateChaining.pdf

Comprehension check

1. True or false? Separate chaining allows for storing more that one object at a given index in our hash table.
2. Separate chaining is but one among a number of collision ______________ policies.
3. If we have b buckets, and n objects to distribute among the buckets, each bucket will have, on average _______ objects.

Answers: u 梅 q / uo岽壥噉los菨晒 / 菨n晒蕠

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.