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

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 of activities on this page