Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

Section 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 6.19.1).
Table 6.19.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})\)
You have attempted of activities on this page.