DS Summary

$ \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} $

Section 6.6 Summary

Maps and sets implemented with lists and sequential search result in $O(n)$ performance. They are not typically implemented this way as a result.
🔗

🔗
Maps and sets implemented with hash tables, under usual circumstances, can provide approximately constant time ($O(1)$) performance. Hash tables are a popular approach for implementing maps and sets.
🔗

🔗
Hashing is not well suited for maps or sets where range queries are common, because such operations would typically require $O(n)$ time. Trees can be a better implementation choice than hashing for situations where range queries are expected to be common. We will study trees in future chapters.
🔗

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next