Java8集合框架——基础知识点汇总

前言

　　Java的集合框架比较基础，像 List、Map、Set 中大概10来个比较常见的集合类，建议多看几遍源码（这里主要是基于 Java 8），然后回过头再来看看各路博客总结的这些知识点，会有一种豁然开朗的感觉。本文的目录结构如下：

一、Java的基础集合分类和继承结构

　　Java的集合主要有 Set、List、Queue、Map 等。其中，Set、List、Queue 继承于 Collection，而 Map 的实现用于保存具有映射关系的数据（key-value），和 Collection 有一定的差别，它是另一个上层接口。

Collection 的继承结构：

Map 的继承结构：

二、基本特征：

　　List 、 Set 、 Map 这几类基础集合的基本特征如下：

集合类型

基本特征
List

1、有序集合（读取数据和存放数据的顺序一致）

2、元素可以重复，访问元素可以根据元素的索引来访问。
Set

1、无序集合（读取数据和存放数据的顺序不一致）

2、根据元素本身来访问元素和进行重复性判断，因此元素不可以重复，类似于数学上的集合概念。
Map

保存 Key-value 对形式的元素，访问时只能根据每项元素的 key 来访问其 value。

1、Set 和 Map 容器都有基于哈希存储(HashSet/HashMap)和排序树（红黑树）(TreeSet/TreeMap)的两种实现版本

2、基于哈希存储的版本理论存取时间复杂度为 O(1)（没有哈希冲突），

3、基于排序树版本的实现在插入或删除元素时会按照元素或元素的键（key）构成排序树从而达到排序和去重的效果，各类操作的时间复杂度为 O(logN)。

三、集合的几种实现：

　　集合的几种实现方式如下：

实现方式

说明

举例
数组

1、数组占用连续内存空间，根据索引查找（即读取）或修改指定索引的元素，速度较快；

2、指定索引处的增删元素较慢，因为需要移动指定索引处后面的元素。

  
列表

一般通过数组实现，但可以自动扩展，通过将旧元素复制到新的内存空间上进行扩容。

ArrayList
链表

1、充分利用了内存，存储空间是不连续的，内部存储上/下一个节点的信息

2、读慢改快：因存储空间不连续，所以寻址麻烦，顺序遍历，查找速度慢，但是找到元素后增删快，

只需要修改节点链接信息，无需挪动其他的元素。

LinkedList
哈希表 链表哈希表综合了前两者的优点，一个哈希表，一般内部由数组和链表(或者红黑树)组成 HashMap

四、集合常见的实现类和源码浅析：

　　常见的集合实现类和相关的源码实现浅析：

集合类型 常见的实现类 说明 源码实现浅析参考
List ArrayList

1、内部是数组实现，查询快（通过数组索引），指定索引处增删慢（需要移动后续的元素）；

2、对插入的元素不进行判断，元素可为空，还可以重复；

3、元素读取和存放同序，即按照存放的顺序进行读取；

4、轻量级，相关操作都没有进行同步或者加锁，因此线程不安全，

     可以用 Collections 配合 ArrayList 实现线程同步。

 Java8集合框架——ArrayList源码分析
LinkedList 链表实现，增删快（前提是要找到指定的结点），查询慢（需要顺序遍历）。 Java8集合框架——LinkedList源码分析
Vector

1、其实现和 ArrayList 类似

2、区别在于：方法中使用了 synchronized 进行同步，重量级操作，但是线程安全

  
Map HashMap

1、键值对，key 不能重复（相同的 key，其旧的 value 会被覆盖），但是 value 可以重复；

2、整体实现是数组+链表（or 红黑树）；

3、允许 null 的键或值；

4、轻量级，相关操作都没有进行同步或者加锁，因此线程不安全；

5、可配合 Collections 工具类使用实现线程安全，或者建议直接使用 ConcurrentHashMap。

Hashtable

（弃用）

 线程安全的，其线程安全是通过 Sychronize 实现，而且不允许 null 的键或值  
Properties key 和 value 都是 String 类型，用来读配置文件  
TreeMap

1、对 key 排好序的 Map；

2、key 要实现 Comparable 接口或 TreeMap 的构造器中传入 Comparator，用于比较排序；

3、内部以 red-black（红-黑）树数据结构实现，插入，删除和查找的时间复杂度都是 O(log n)；

4、实现了SortedMap接口

  
LinkedHashMap

1、HashMap 的子类，对 HashMap 进行了扩展，维护着一个运行于所有元素的双向链表。

2、存储的数据是有序的，保存了记录（或访问）的插入顺序（双向链表的记录）。

 Java8集合框架——LinkedHashMap源码分析
Set HashSet

1、存放重复的元素时，只会保留一个。

2、一般需要重写 hashCode() 方法，采用恰当的方式分配散列码。

3、内部实现是使用 HashMap，元素为 key，value 都是同个 Object 对象。

而value是同一个 Object，即 private static final Object PRESENT = new Object(); 。

 Java8集合框架——HashSet源码分析
TreeSet

1、SortedSet 的实现类，实现排序，因此添加到 TreeSet 的元素必须是可排序的(元素自身可排序

或者提供Comparator 进行排序)，它总是平衡的，保证了插入、删除、查询的性能为 log(n)。

2、内部实现是 TreeMap

  
LinkedHashSet

1、与 HashSet 的不同之外在于，维护着一个运行于所有元素的双向链接。

2、存储的数据是有序的（通过双向链表维持有序性）

3、扩展自 HashSet，但是其底层使用 LinkedHashMap，元素为 key，而value是同一个 Object，

即 private static final Object PRESENT = new Object(); 原理和 LinkedHashMap 类似。

  Java8集合框架——LinkedHashSet源码分析
Queue

PriorityQueue

1、一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。

2、在创建的时候，可以提供一个负责给元素排序的比较器。

3、PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。

4、PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。

  

关于 Collection 的几点简单/补充说明： 

  1. Collection 是最基本的集合接口。所有实现 Collection 接口的类都需要提供两个标准的构造函数
    • 无参数的构造函数：用于创建一个空的 Collection
    • 有一个 Collection 参数的构造函数：用于创建一个新的 Collection，这个新的 Collection 与传入的 Collection 有相同的元素，即允许用户复制一个 Collection。
  2. 可以使用 iterator() 或者 foreach 循环对 Collection 的元素进行遍历
  3. Collection 接口派生的两个接口是 List 和 Set
    • Set 接口
      • Set 表示数学意义上的集合，不予许有重复的元素，即不会存在元素 e1 和 e2，使得 e1.equals(e2)。常见操作是对象的添加、删除，但不支持随机访问。
    • List 接口
      • 允许有重复项，且元素有顺序(索引)，可以根据索引对元素进行访问。
      • List 接口提供了4种对列表元素进行定位（索引）访问方法：索引、迭代器 Iterator、特殊迭代器 ListIterator、foreach、for 循环。
      • List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。

Collections.synchronizedCollection(Collection<T> c) 方法去处理原本非同步的类，在不丢失性能的前提下，实现同步。Java1.5提供了 ConcurrentHashMap，适用于高并发的线程安全实现。

注：ConcurrentHashMap：线程安全，是通过 Lock 的方式实现的，并且锁分离。ConcurrentHashMap 内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的 HasMap，它们有自己的锁，只要多个修改操作发生在不同的段上，它们就可以并发进行。大体可以看出这也是 ConcurrentHashMap 名称的由来。

五、Collection、Collections、Arrays的区别

　　Collection 、 Collections 、 Arrays 三者的区别和相关说明如下：

Collection 集合类的上级接口，继承于他的接口主要有 Set、List。Set 里的元素是不能重复的，equals() 方法来区分重复与否。  
Collections 针对集合类的一个工具类，提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 Java8集合框架——集合工具类Collections内部方法浅析
Arrays 包含用来操作数组（比如排序和搜索）的各种方法 Java8集合框架——集合工具类Arrays内部方法浅析

六、其他待补充

以下这几点的内容待研究和补充。。。。

1、集合迭代 Iterator

2、Iterator 的 fail-fast 和 fail-safe

  1. 每次我们尝试获取下一个元素的时候，Iterator 的 fail-fast 属性检查当前集合结构里的任何改动（使用内部属性 modCount，修改计数器）。如果发现任何改动，它抛出 ConcurrentModificationException。Collection 中所有 Iterator 的实现都是按fail-fast 来设计的（ConcurrentHashMap 和CopyOnWriteArrayList 这类并发集合类除外）。
  2. Iterator 的 fail-fast 属性与当前的集合共同起作用，因此它不会受到集合中任何改动的影响。java.util 包中的所有集合类都被设计为 fail-fast 的，而 java.util.concurrent 中的集合类都为 fail-safe 的。fail-fast 迭代器抛出 ConcurrentModificationException，而 fail-safe 迭代器从不抛出 ConcurrentModificationException。
  3. 在 Java fail fast 迭代器中，迭代 objects 集合有时会出现并发修改异常，出现这种情况有2个原因：①如果一个线程正在迭代一个集合，而另一个线程同时试图修改这个集合；②遍历过程中，试图去修改集合。注：在遍历过程中调用 remove() 方法不会引起 ConcurrentModificationException。
  4. fail-fast（快速失败）：快速失败机制在遍历一个集合时，如果集合内容被修改，会抛出 ConcurrentModificationException 异常。
  5. fail-safe（安全失败）：安全失败机制对集合的任何修改都会在一个复制的集合上进行，因此不会抛出异常。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wpbxin/p/9033468.html