Java-L08: 集合框架
2019-04-09 本文已影响0人
WenxuanLi
李文轩 2019-03-19
声明：这是本人学习极客时间的Java核心36讲的笔记，有侵权请联系我。
Java的集合框架，此处不包括 Map 和 java.util.concurrent 下的线程安全容器
Vector, ArrayList, LinkedList 有何区别？
-
这三个类都实现了集合框架里的
List，即有序集合。具体功能都有相似的地方，比如，提供按照位置进行定位、添加或者删除的操作，都提供迭代器以遍历其内容。 -
不同在于具体设计、行为、性能和性能安全等。
- Vector
- 线程安全的动态数组
- 内部是用对象数组来保存数据
- 可自动增加容量，每次提高一倍
- ArrayList
- 动态数组
- 不是线程安全的，性能高很多
- 可自动增加容量，每次增加50%
- LinkedList
- 双向链表
- 不是线程安全的
- 不需要扩容，size=capacity
- Vector
-
应用场景分析
-
Vector和ArrayList作为动态数组，都很适合需要大量随机访问的场合。但是除了对尾部数据的操作，大部分（除尾部以外所有元素）操作性能都很差。 -
LinkedList的节点插入与删除的性能都很好，可是随机访问性能较差。 -
读写机制：
-
ArrayList在插入元素时，若超过当前数组预定义的最大值时，数组需要扩容；扩容过程需要调用底层System.ArrayCopy()方法进行数组复制。在删除元素时并不会减小容量（若需要，可调用trimToSize()方法）。在查找元素时要遍历数组，对于非null的元素采取equals()的方式寻找。 -
LinkedList在插入元素时，先创建一个Entry对象，并更新此元素和前后元素的引用。查找元素时要遍历链表。删除元素时，要遍历链表，找到元素，并更新前后元素的引用。 -
Vector与ArrayList仅在插入元素时有不同。默认下，Vector初创时是一个容量为10的数组，capacityIncrement为0。当需要扩容时，先检查capacityIncrement；若此值大于0，数组大小将扩容到size+capacityIncremnet；若小于等于0（默认值），将扩大到原先的两部。
-
-
Java的集合框架（Collection）
- Map并没有出现在Java的
Collection里 -
java.util.concurrent这里也先不涉及
三大类集合
- List，有序集合，提供了方便访问、插入、删除
- Set，不允许重复元素，即不存在两个对象
equals返回true。 - Queue/Deque，Java提供的标准队列结构的实现。支持 FIFO 和 LIFO 等特定行为。
Set
-
TreeSet 支持自然顺序访问；添加、删除、包含等操作要相对低效 (log(n)时间)。
-
HashSet 利用哈希算法；若哈希散列正常，可以提供常数时间的添加、删除、包含等操作；但不保证有序。
-
LinkedHashSet 在内部构建了一个记录插入顺序但双向链表，从而提供了按照插入顺序遍历的能力；也保证了常数时间的添加、删除、包含等操作；操作性能略低于HashSet，因为要维护链表。
-
遍历元素时，
HashSet性能受自身容量影响。LinkedHashSet由于内部链表，遍历性能与元素数量有关。
线程安全问题
-
其实集合框架也支持并发编程的场景
-
实现方式就是每个基本方法（get、set、add）都添加
synchronized -
都符合迭代时
fail-fast行为，当发生意外当并发修改时，尽早抛出ConcurrentModificationException异常。 -
Collection 的工具类
static <T> List<T> synchronizedList(List<T> list)
- 运用
List list = Collections.synchronizedList(new ArrayList());
排序
- 对于原始数据类型，现在所使用的是 双轴快速排序（
Dual-Pivot QuickSort），是一种改进的快速排序算法 - 对于对象数据类型，目前是TimSort，思想上是一种归并和二分插入排序（binarySort）结合的优化排序算法。
- 可有调用
parallelSort方法，充分利用多核处理器的能力，底层实现基于fork-join框架
