Wrapping Up

Caching is truly a pivotal concept in computing. Whether you’ll be implementing your own caches or taking advantage of the memory caches within the memory hierarchy, knowing how caches work enables you to push the envelope of your code’s speed.

In the chapters that follow, we’re going to continue to explore the theme of randomization and specifically the concept of randomized data structures. Randomized data structures are data structures whose whole power stems from random numbers. The first such data structure we’ll discuss is the treap. But before we dive into the world of treaps, in the next chapter we’ll first contrast treaps with their nonrandomized counterparts—red-black trees, a classic must-know data structure.