容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。
Collection
List:有先后顺序,数值不唯一
ArrayList
- 基于数组实现List接口。
- 由于基于数组实现,连续内存,所以擅长于顺序访问和随机下标访问,速度最快,时间复杂度是O(1)。
- 用会自动扩增容量的Array([],最高效,但是容量固定但不可动态改变)。
- 数组扩容是对ArrayList效率影响比较大的一个因素。每当执行Add、AddRange、Insert、InsertRange等添加元素的方法,都会检查内部数组的容量是否不够了,如果不够,它就会以当前容量的两倍来重新构建一个数组,将旧元素Copy到新数组中,然后丢弃旧数组,在这个临界点的扩容操作,应该来说是比较影响效率的。
- 按内容查找逐个遍历,速度较慢,时间复杂度是,时间复杂度是O(N)。
- 增、删操作导致元素大量移动,非常耗时,时间复杂度是O(N)。
LinkedList
- 基于头尾相连的双向链表实现,只能顺序或逆序访问,但是可以快速地在链表中间插入和删除元素,时间复杂度是O(1)。
- 随机访问速度较慢,时间复杂度是O(N)。
- 用作栈、队列和双向队列。
Set:无先后顺序,数值唯一
HashSet
- 底层使用HashTable实现。
- 添加快、内容查询快、删除快,都是O(1)。
- 无先后顺序,无大小顺序,也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
LinkedHashSet
- 具备HashSet优点,但是添加、删除会比HashSet慢一点
- 内部使用双向链表维护元素的插入先后顺序。
TreeSet
- 红黑树(有序的自平衡二叉树)
- 有大小顺序
- 查询内容O(logN)比List的O(N)快,比HashSet的O(1)慢
EnumSet
- 以位向量的形式存储,对象占用内存很小,而且运行效率很好。尤其是进行批量操作(如调用containsAll()和retainAll()方法)时,如果其参数也是EnumSet集合,则该批量操作的执行速度也非常快。
Set整理思路
- HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作),因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时,才应该使用TreeSet,否则都应该使用HashSet
- 对于普通的插入、删除操作,LinkedHashSet比HashSet要略慢一点,这是由维护链表所带来的开销造成的。不过,因为有了链表的存在,遍历LinkedHashSet会更快
- EnumSet是所有Set实现类中性能最好的,但它只能保存同一个枚举类的枚举值作为集合元素
- HashSet、TreeSet、EnumSet都是"线程不安全"的,通常可以通过Collections工具类的synchronizedSortedSet方法来"包装"该Set集合。
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
Queue
LinkedList
- 实现双向列表队列
PriorityQueue
- 基于堆结构实现,实现了优先级队列
- 队首元素优先级最高
- 默认按照元素比较多顺序排序,此时要实现comparable接口
- 也可以传入Compartor自定义排序对象,此时不实现comparable接口
- 可以实现
Map
HashTable
- 与HashMap类似,但是是线程安全的
- 现在可以使用 ConcurrentHashMap 来支持线程安全,并且 ConcurrentHashMap 的效率会更高,因为 ConcurrentHashMap 引入了分段锁。
LinkedHashTable
- 使用双向链表来维护元素的顺序,顺序为插入顺序或者最近最少使用(LRU)顺序。
HashMap
- 基于哈希表实现
TreeMap
- 基于红黑树实现(有序的自平衡二叉树)
Map整理思路
- HashMap和Hashtable的效率大致相同,因为它们的实现机制几乎完全一样。但HashMap通常比Hashtable要快一点,因为Hashtable需要额外的线程同步控制
- TreeMap通常比HashMap、Hashtable要慢(尤其是在插入、删除key-value对时更慢),因为TreeMap底层采用红黑树来管理key-value对
- 使用TreeMap的一个好处就是: TreeMap中的key-value对总是处于有序状态,无须专门进行排序操作
如何记录每一个容器的结构和所属体系呢?
看名字!后缀名就是该集合所属的体系。前缀名就是该集合的数据结构。
看到array:就要想到数组,就要想到查询块,有下标。
看到link:就要想到链表,就要想到增删快,就要想到add,get,remove+first last的方法。
看到hash:就要想到哈希表,就要想到唯一性,就要想到元素需要覆盖hashCode方法和equals方法。
看到tree:就要想到二叉树,就要想到排序,就要想到两个接口Comparator,Comparable。
而且通常这些常用的集合容器都是不同步的。