Wrapping Up

Monte Carlo algorithms have the ability to greatly boost the speed of operations that might otherwise take a really long time. Of course, they come at the cost of some accuracy. But if you’ll get the correct result with high probability, it can sometimes be a worthwhile trade-off. Ultimately, how much you need perfect accuracy will depend on your specific application.

In the next chapter, we’re going to look at another randomization topic known as randomized hashing. With it, we’ll take our understanding of hash tables to the next level. (Eventually, in Chapter 13, we’ll combine the concepts of Monte Carlo algorithms and randomized hashing to produce an astounding data structure known as a Bloom Filter.)

Ready to dive deeper into how hash tables work and how randomization helps them become more efficient? Well, turn the page.