Java-L08: 集合框架

李文轩 2019-03-19
声明：这是本人学习极客时间的Java核心36讲的笔记，有侵权请联系我。

---

Java的集合框架，此处不包括 Map 和 java.util.concurrent 下的线程安全容器

Vector, ArrayList, LinkedList 有何区别？

• 这三个类都实现了集合框架里的List，即有序集合。具体功能都有相似的地方，比如，提供按照位置进行定位、添加或者删除的操作，都提供迭代器以遍历其内容。

• 不同在于具体设计、行为、性能和性能安全等。

  • Vector
    • 线程安全的动态数组
    • 内部是用对象数组来保存数据
    • 可自动增加容量，每次提高一倍
  • ArrayList
    • 动态数组
    • 不是线程安全的，性能高很多
    • 可自动增加容量，每次增加50%
  • LinkedList
    • 双向链表
    • 不是线程安全的
    • 不需要扩容，size=capacity

• 应用场景分析

  • 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框架