前面的一些文章主要分析了 Java 集合框架(Java Collections Framework, JCF)中常用的类和接口,本文打算做个整体的小结。
JCF 主要包括 Collection 接口系列和 Map 接口系列,它们的继承结构分别如下:
Collection 接口继承结构:
Map 接口继承结构:
PS: 其中一些类暂未进行分析,有些是因为使用较少(Stack 等),有些打算后面在并发包(java.util.concurrent, JUC)源码分析的时候再进行分析(BlockingQueue、ConcurrentHashMap 等)。
Collection 接口又包括 List、Set 和 Queue 三个子接口,它们的主要特点如下:
1. List: 列表,有序、可重复;
2. Set: 集合(数学中的集合概念),无序、不重复;
3. Queue: 队列,先进先出(First In First Out, FIFO)。
前面分析常用类的小结如下:
ArrayList
1. 「可以自动扩容的数组」,默认初始化容量为 10,默认每次扩容为原容量的 1.5 倍;
2. 扩容时会创建一个新的数组,并将之前的元素拷贝到新数组中(因此,若要将数量已知的元素放入 ArrayList,在初始化时指定长度可以避免多次扩容);
3. 线程不安全,不适合在多线程场景下使用。
Vector
1. 与 ArrayList 类似,Vector 也可以认为是「可变数组」;
2. 扩容原理与 ArrayList 基本一致,只是新容量计算方式略有不同:指定增长容量时,新容量为旧容量 + 增长容量;否则扩容为旧容量的 2 倍;
3. 线程安全,实现方式简单(使用 synchronized);
4. 当前使用较少。
LinkedList
1. 双向链表、双端队列、栈;
2. 线程不安全,内存空间不连续。
至于 HashSet 和 TreeSet,它们的实现分别是基于 HashMap 和 TreeMap,因此不再进行分析。
Map 是以键-值对(Entry)形式存储元素的,HashMap 最为常用,常用类的小结如下:
TreeMap
1. TreeMap 实现了 Map 接口, 内部节点类型为 Entry;
2. 基于红黑树实现,具有红黑树的特点;
3. 有序,根据 Entry 的 key 排序;
4. 查找、插入、删除操作的时间复杂度均为 O(logn) 。
HashMap
1. HashMap 是散列表的实现,它使用“链表法”处理散列冲突用,并在 JDK 1.8 引入红黑树进一步优化;
2. 内部结构为「数组 + 链表 + 红黑树」;
3. 默认初始化容量为 16,负载因子为 0.75,扩容的阈值为 16 * 0.75 = 12;
4. 当容器中元素的容量大于阈值时,HashMap 会自动扩容为原先的 2 倍。
LinkedHashMap
1. 继承自 HashMap,其结构可以理解为「双链表 + 散列表」;
2. 可以维护两种顺序:插入顺序或访问顺序;
3. 可以方便的实现 LRU 缓存;
4. 线程不安全。
Hashtable
1. 散列表的实现,处理散列冲突使用的是链表法,内部结构可以理解为「数组 + 链表」;
2. 默认初始化容量为 11,默认负载因子为 0.75;
3. 线程安全,使用 synchronized 关键字, 并发效率低 ;
4. 若无需保证线程安全,推荐使用 HashMap;若需要线程安全的高并发场景,推荐使用 ConcurrentHashMap。
本文对前面分析的一些集合类做个简单小结,集合类的代码分析暂告一段落,接下来打算分析并发包下常用的类和接口。
有关集合框架可参考官方文档的介绍:
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html
Stay hungry, stay foolish.
原文 http://mp.weixin.qq.com/s?__biz=MzU4NzYyMDE4MQ==&mid=2247483889&idx=1&sn=f943b3fa443c7f0a1eb751c85d643222