# 6.17. 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})$$
Next Section - 6.18. Summary