DS Summary of Map ADT Implementations

$ \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 8.9 Summary of Map ADT Implementations

Over the past few chapters we have looked at several approaches that can be used to implement the map abstract data type: a hash table, a binary search tree, and a balanced binary search tree. To conclude this section, let’s summarize the worst case performance of each data structure for the key operations defined by the map ADT (see Table 8.9.1), and compare it with a baseline of just keeping the data in a sorted list, and using binary search to find what we’re looking for.

🔗

Table 8.9.1. Comparing the Performance of Different Map Implementations

🔗

operation	Sorted List	Hash Table	Binary Search Tree	AVL Tree
`put`	$O(n)$	$O(1)$	$O(n)$	$O(\log_2{n})$
`get`	$O(\log_2{n})$	$O(1)$	$O(n)$	$O(\log_2{n})$
`in`	$O(\log_2{n})$	$O(1)$	$O(n)$	$O(\log_2{n})$
`del`	$O(n)$	$O(1)$	$O(n)$	$O(\log_2{n})$

You have attempted of activities on this page.

🔗

Prev Top Next

operation	Sorted List	Hash Table	Binary Search Tree	AVL Tree
`put`	\(O(n)\)	\(O(1)\)	\(O(n)\)	\(O(\log_2{n})\)
`get`	\(O(\log_2{n})\)	\(O(1)\)	\(O(n)\)	\(O(\log_2{n})\)
`in`	\(O(\log_2{n})\)	\(O(1)\)	\(O(n)\)	\(O(\log_2{n})\)
`del`	\(O(n)\)	\(O(1)\)	\(O(n)\)	\(O(\log_2{n})\)