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)$

You have attempted 1 of 1 activities on this page