Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

8.18. 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 1).

**Table 1: Comparing the Performance of Different Map Implementations**¶
operation	Sorted Array	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})$

operation	Sorted Array	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})\)