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 是用位向量实现的,对于只有两种状态且需要进行集合运算的数据使用位向量进行表示、位运算进行处理,精简且高效。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐