List、Map、Set、Queue的区别与关系

r囧r小猫 2022-05-16 11:36 149阅读 0赞

List、Set、Queue 都继承自 Collection 接口，而 Map 则不是（继承自 Object），所以容器类有两个根接口，分别是 Collection 和 Map，Collection 表示单个元素的集合，Map 表示键值对的集合。

List 的主要特点就是有序性和元素可空性，他维护了元素的特定顺序，其主要实现类有 ArrayList 和 LinkList。ArrayList 底层由数组实现，允许元素随机访问，但是向 ArrayList 列表中间插入删除元素需要移位复制速度略慢；LinkList 底层由双向链表实现，适合频繁向列表中插入删除元素，随机访问需要遍历所以速度略慢，适合当做堆栈、队列、双向队列使用。

Set 的主要特性就是唯一性，存入 Set 的每个元素都必须唯一，加入 Set 的元素都必须确保对象的唯一性，Set 不保证维护元素的有序性，其主要实现类有 HashSet、LinkHashSet、TreeSet。HashSet 是为快速查找元素而设计，存入 HashSet 的元素必须定义 hashCode 方法，其实质可以理解为是 HashMap 的包装类，所以 HashSet 的值还具备可 null 性；LinkHashSet 具备 HashSet 的查找速度且通过链表保证了元素的插入顺序（实质为 HashSet 的子类），迭代时是有序的，同理存入 LinkHashSet 的元素必须定义 hashCode 方法；TreeSet 实质是 TreeMap 的包装类，所以 TreeSet 的值不备可 null 性，其保证了元素的有序性，底层为红黑树结构，存入 TreeSet 的元素必须实现 Comparable 接口；不过特别注意 EnumSet 的实现和 EnumMap 没有一点关系。

Queue 的主要特性就是队列，其主要的实现类有 LinkedList、PriorityQueue。LinkedList 保证了按照元素的插入顺序进行操作；PriorityQueue 按照优先级进行插入抽取操作，元素可以通过实现 Comparable 接口来保证优先顺序。Deque 是 Queue 的子接口，表示更为通用的双端队列，有明确的在头或尾进行查看、添加和删除的方法，ArrayDeque 基于循环数组实现，效率更高一些。

Map 自立门户，但是也提供了嫁接到 Collection 相关方法，其主要特性就是维护键值对关联和查找特性，其主要实现类有 HashTable、HashMap、LinkedHashMap、TreeMap。HashTab 类似 HashMap，但是不允许键为 null 和值为 null，比 HashMap 慢，因为为同步操作；HashMap 是基于散列列表的实现，其键和值都可以为 null；LinkedHashMap 类似 HashMap，其键和值都可以为 null，其有序性为插入顺序或者最近最少使用的次序（LRU 算法的核心就是这个），之所以能有序，是因为每个元素还加入到了一个双向链表中；TreeMap 是基于红黑树算法实现的，查看键值对时会被排序，存入的元素必须实现 Comparable 接口，但是不允许键为 null，值可以为 null；如果键为枚举类型可以使用专门的实现类 EnumMap，它使用效率更高的数组实现。

从数据结构角度看集合的区别有如下：

动态数组：ArrayList 内部是动态数组，HashMap 内部的链表数组也是动态扩展的，ArrayDeque 和 PriorityQueue 内部也都是动态扩展的数组。

链表：LinkedList 是用双向链表实现的，HashMap 中映射到同一个链表数组的键值对是通过单向链表链接起来的，LinkedHashMap 中每个元素还加入到了一个双向链表中以维护插入或访问顺序。

哈希表：HashMap 是用哈希表实现的，HashSet, LinkedHashSet 和 LinkedHashMap 基于 HashMap，内部当然也是哈希表。

排序二叉树：TreeMap 是用红黑树(基于排序二叉树)实现的，TreeSet 内部使用 TreeMap，当然也是红黑树，红黑树能保持元素的顺序且综合性能很高。

堆：PriorityQueue 是用堆实现的，堆逻辑上是树，物理上是动态数组，堆可以高效地解决一些其他数据结构难以解决的问题。

循环数组：ArrayDeque 是用循环数组实现的，通过对头尾变量的维护，实现了高效的队列操作。

位向量：EnumSet 是用位向量实现的，对于只有两种状态且需要进行集合运算的数据使用位向量进行表示、位运算进行处理，精简且高效。