转载

JDK集合框架小结

前面的一些文章主要分析了 Java 集合框架(Java Collections Framework, JCF)中常用的类和接口,本文打算做个整体的小结。

JCF 主要包括 Collection 接口系列和 Map 接口系列,它们的继承结构分别如下:

Collection 接口继承结构:

JDK集合框架小结

Map 接口继承结构:

JDK集合框架小结

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.

JDK集合框架小结

原文  http://mp.weixin.qq.com/s?__biz=MzU4NzYyMDE4MQ==&mid=2247483889&idx=1&sn=f943b3fa443c7f0a1eb751c85d643222
正文到此结束
Loading...