Skip to main content
Engineering LibreTexts

10.4: Exercise 8

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    In this exercise, you will finish off the implementation of MyBetterMap. In the repository for this book, you’ll find the source files for this exercise:

    • contains our solution to the previous exercise, which we will build on in this exercise.
    • contains the code from the previous chapter with some methods you will fill in.
    • contains the outline of a hash table that grows when needed, which you will complete.
    • contains the unit tests for MyLinearMap.
    • contains the unit tests for MyBetterMap.
    • contains the unit tests for MyHashMap.
    • contains code for measuring and plotting run time versus problem size.
    • contains code that profiles the Map.put method.

    As usual, you should run ant build to compile the source files. Then run ant MyBetterMapTest. Several tests should fail, because you have some work to do!

    Review the implementation of put and get from the previous chapter. Then fill in the body of containsKey.


    Use chooseMap.

    Run ant MyBetterMapTest again and confirm that testContainsKey passes.

    Fill in the body of containsValue.


    Don’t use chooseMap.

    Run ant MyBetterMapTest again and confirm that testContainsValue passes. Notice that we have to do more work to find a value than to find a key.

    Like put and get, this implementation of containsKey is linear, because it has to search one of the embedded sub-maps. In the next chapter, we’ll see how we can improve this implementation even more.

    This page titled 10.4: Exercise 8 is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?