6.19. Map ADT实现总结

6.19. Summary of Map ADT Implementations

中文英文

在过去的两章中，我们研究了几种可以用来实现映射抽象数据类型的数据结构：排序列表上的二叉搜索、哈希表、二叉搜索树以及平衡二叉搜索树。为了总结这一部分，让我们对比每种数据结构在映射抽象数据类型定义的关键操作中的性能（见 表 1）。

表 1: 不同映射实现的性能比较

操作	排序列表	哈希表	二叉搜索树	AVL 树
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)$

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

---

最后更新: 2024年9月13日
创建日期: 2024年9月9日