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 6.19 Summary of Map ADT Implementations

Over the past two chapters we have looked at several data structures that can be used to implement the map abstract data type: a binary search on a list, a hash table, a binary search tree, and a balanced binary search tree. To conclude this section, let’s summarize the performance of each data structure for the key operations defined by the map ADT (see Table 6.19.1).

Table 6.19.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})\)