集合容器概述

什么是集合？

顾名思义，集合就是用于存储数据的容器。

集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

码老湿，可以说下集合框架的三大块内容具体指的是什么吗？

接口

面向接口编程，抽象出集合类型，使得我们可以在操作集合的时候不必关心具体实现，达到「多态」。

就好比密码箱，我们只关心能打开箱子，存放东西，并且关闭箱子，至于怎么加密咱们不关心。

接口实现

每种集合的具体实现，是重用性很高的数据结构。

算法

集合提供了数据存放以及查找、排序等功能，集合有很多种，也就是算法通常也是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。

事实上，算法是可复用的函数。它减少了程序设计的辛劳。

集合框架通过提供有用的数据结构和算法使你能集中注意力于你的程序的重要部分上，而不是为了让程序能正常运转而将注意力于低层设计上。

集合的特点

对象封装数据，多个对象需要用集合存储；

对象的个数可以确定使用数组更高效，不确定个数的情况下可以使用集合，因为集合是可变长度。

集合与数组的区别

数组是固定长度的；集合可变长度的。

数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

由于有多种集合容器，因为每一个容器的自身特点不同，其实原理在于每个容器的内部数据结构不同。

集合容器在不断向上抽取过程中，出现了集合体系。在使用一个体系的原则：参阅顶层内容。建立底层对象。

集合框架有哪些优势

容量自动增长扩容；

提供高性能的数据结构和算法；

可以方便地扩展或改写集合，提高代码复用性和可操作性。

通过使用JDK自带的集合类，可以降低代码维护和学习新API成本。

有哪些常用的集合类

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue三种子接口。

我们比较常用的是Set、List，Map接口不是 collection的子接口。

Collection集合主要有List和Set两大接口

List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。

Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。

Map没有继承于 Collection 接口，从 Map 集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

集合的底层数据结构

Collection

List

ArrayList：Object 数组；

Vector：Object 数组；

LinkedList：双向循环链表；

2.Set

HashSet：唯一，无序。基于 HashMap 实现，底层采用 HashMap 保存数据。
它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。
如果我们没有重写这两个方法，将会使用这个方法的默认实现。

LinkedHashSet： LinkedHashSet 继承与 HashSet，底层使用 LinkedHashMap 来保存所有元素。

TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树。)

Map

HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中。LinkedHashMap支持两种顺序插入顺序、访问顺序。

插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序

访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。

HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

TreeMap：红黑树（自平衡的排序二叉树）

集合的 fail-fast 快速失败机制

Java 集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。

原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。

集合在被遍历期间如果内容发生变化，就会改变modCount的值。

每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

解决办法：

在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。

使用CopyOnWriteArrayList来替换ArrayList

Collection 接口

List 接口

Itertator 是什么

Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。

迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
  String obj = it. next();
  System. out. println(obj);
}

如何边遍历边移除 Collection 中的元素？

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();
}

一种最常见的错误代码如下：

for(Integer i : list){
   list.remove(i)
}

运行以上错误代码会报 ConcurrentModificationException 异常。

如何实现数组和 List 之间的转换？

数组转 List：使用 Arrays. asList(array) 进行转换。

List 转数组：使用 List 自带的 toArray() 方法。

ArrayList 和 LinkedList 的区别是什么？

数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。

随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。

增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

为什么 ArrayList 的 elementData 加上 transient 修饰？

ArrayList 中的数组定义如下：

private transient Object[] elementData;

ArrayList 的定义：

public class ArrayList<E> extends AbstractList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。

transient 的作用是说不希望 elementData 数组被序列化。

每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小。

介绍下CopyOnWriteArrayList？

CopyOnWriteArrayList是ArrayList的线程安全版本，也是大名鼎鼎的copy-on-write（COW，写时复制）的一种实现。

在读操作时不加锁，跟ArrayList类似；在写操作时，复制出一个新的数组，在新数组上进行操作，操作完了，将底层数组指针指向新数组。

适合使用在读多写少的场景。例如add(Ee)方法的操作流程如下：使用ReentrantLock加锁，拿到原数组的length，使用Arrays.copyOf方法从原数组复制一个新的数组（length+1），将要添加的元素放到新数组的下标length位置，最后将底层数组指针指向新数组。

List、Set、Map三者的区别?

List（对付顺序的好帮手）：存储的对象是可重复的、有序的。

Set（注重独一无二的性质）：存储的对象是不可重复的、无序的。

Map（用Key来搜索的专业户）:存储键值对（key-value），不能包含重复的键（key），每个键只能映射到一个值。

Set 接口

说一下 HashSet 的实现原理？

HashSet底层原理完全就是包装了一下HashMap

HashSet的唯一性保证是依赖与hashCode()和equals()两个方法，所以存入对象的时候一定要自己重写这两个方法来设置去重的规则。

HashSet 中的元素都存放在 HashMap 的 key 上面，而value 中的值都是统一的一个 private static final Object PRESENT = new Object();

hashCode（）与equals（）的相关规定：

如果两个对象相等，则 hashcode 一定也是相同的

两个对象相等，对两个 equals 方法返回 true

两个对象有相同的 hashcode 值，它们也不一定是相等的

综上，equals方法被覆盖过，则hashCode方法也必须被覆盖

hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别

== 是判断两个变量或实例是不是指向同一个内存空间 equals 是判断两个变量或实例所指向的内存空间的值是不是相同

== 是指对内存地址进行比较 equals() 是对字符串的内容进行比较

==指引用是否相同， equals() 指的是值是否相同。

Queue

BlockingQueue是什么？

Java.util.concurrent.BlockingQueue 是一个队列，在进行检索或移除一个元素的时候，线程会等待队列变为非空；

当在添加一个元素时，线程会等待队列中的可用空间。

BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。

Java提供了几种 BlockingQueue 的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什么区别？

相同点：都是返回第一个元素，并在队列中删除返回的对象。

不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。

面霸篇：Java 集合容器大满贯（卷二）（一）