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

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